A Simulation-Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel Times
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....
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2013/127156 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850173936120102912 |
|---|---|
| author | Zheng Wang Lin Lin |
| author_facet | Zheng Wang Lin Lin |
| author_sort | Zheng Wang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-c878ce13aad84114b8e53a88e149a4c4 |
| institution | OA Journals |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-c878ce13aad84114b8e53a88e149a4c42025-08-20T02:19:45ZengWileyJournal of Applied Mathematics1110-757X1687-00422013-01-01201310.1155/2013/127156127156A Simulation-Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel TimesZheng Wang0Lin Lin1School of Software, Dalian University of Technology, Dalian, Liaoning 116620, ChinaSchool of Software, Dalian University of Technology, Dalian, Liaoning 116620, ChinaThis 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.http://dx.doi.org/10.1155/2013/127156 |
| spellingShingle | Zheng Wang Lin Lin A Simulation-Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel Times Journal of Applied Mathematics |
| title | A Simulation-Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel Times |
| title_full | A Simulation-Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel Times |
| title_fullStr | A Simulation-Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel Times |
| title_full_unstemmed | A Simulation-Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel Times |
| title_short | A Simulation-Based Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Travel Times |
| title_sort | simulation based algorithm for the capacitated vehicle routing problem with stochastic travel times |
| url | http://dx.doi.org/10.1155/2013/127156 |
| work_keys_str_mv | AT zhengwang asimulationbasedalgorithmforthecapacitatedvehicleroutingproblemwithstochastictraveltimes AT linlin asimulationbasedalgorithmforthecapacitatedvehicleroutingproblemwithstochastictraveltimes AT zhengwang simulationbasedalgorithmforthecapacitatedvehicleroutingproblemwithstochastictraveltimes AT linlin simulationbasedalgorithmforthecapacitatedvehicleroutingproblemwithstochastictraveltimes |