A Simulation‐Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel Times

Zheng Wang and Lin Lin

Journal of Applied Mathematics, 2013, vol. 2013, issue 1

Abstract: This paper presents a flexible solution methodology for the capacitated vehicle routing problem with stochastic travel times (CVRPSTT). One of the basic ideas of the methodology is to consider a vehicle working time lower than the actual maximum vehicle working time when designing CVRPSTT solutions. In this way, the working time surplus can be used to cope with unexpected congestions when necessary. Another important idea is to transform the CVRPSTT instance to a limited set of capacitated vehicle routing problems (CVRP), each of which is defined by a given percentage of the maximum vehicle working time. Thus, our approach can take advantage of any efficient heuristic that already exists for the CVRP. Based on the two key ideas, this paper presents a simulation‐based algorithm, in which Monte Carlo simulation is used to obtain estimates of the cost and the reliability of each solution, and the Clarke and Wright heuristic is improved to generate more reliable solutions. Finally, a number of numerical experiments are done in the paper with the purpose of analyzing the efficiency of the described methodology under different uncertainty scenarios.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2013/127156

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2013:y:2013:i:1:n:127156

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().