A model for solving the dynamic vehicle dispatching problem with customer uncertainty and time dependent link travel time
DOI:
https://doi.org/10.17533/udea.redin.13114Keywords:
dynamic vehicle routing, customer uncertainty, vehicle routing problem, heuristicsAbstract
In a real world case scenario, customer demands are requested at any time of the day requiring services that are not known in advance such as delivery or repairing equipment. This is called Dynamic Vehicle Routing (DVR) with customer uncertainty environment. The link travel time for the roadway network varies with time as trafÆ c Ø uctuates adding an additional component to the dynamic environment. This paper presents a model for solving the DVR problem while combining these two dynamic aspects (customer uncertainty and link travel time). The proposed model employs Greedy, Insertion, and Ant Colony Optimization algorithms. The Greedy algorithm is utilized for constructing new routes with existing customers, and the remaining two algorithms are employed for rerouting as new customer demands appear. A real world application is presented to simulate vehicle routing in a dynamic environment for the city of Taipei, Taiwan. The simulation shows that the model can successfully plan vehicle routes to satisfy all customer demands and help managers in the decision making process.
Downloads
References
D. Bertsimas, D. Simchi. “A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty”. Operations Research. Vol. 44. 1996. pp. 286-304. DOI: https://doi.org/10.1287/opre.44.2.286
R. Swihart, D. Papastavrou, A stochastic and dynamic model for the single-vehicle pick-up and delivery problem. European Journal of Operational Research. Vol. 114. 1999. pp. 447-464. DOI: https://doi.org/10.1016/S0377-2217(98)00260-4
G. Ghiani, G. Improta. “An Efficient Transformation of the Generalized Vehicle Routing Problemî. European Journal of Operational Research. Vol. 122. 2000. pp. 11-17. DOI: https://doi.org/10.1016/S0377-2217(99)00073-9
H. Lau, M. Sim, K. Teo. “Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles”. European Journal of Operational Research. Vol. 148. 2003. pp. 559-569. DOI: https://doi.org/10.1016/S0377-2217(02)00363-6
G. Giaglis, I. Minis, A. Tatarakis, V. Zeimpekis. “Minimizing Logistics Risk Through Real-Time Vehicle Routing and Mobile Technologies”. International Journal of Physical Distribution & Logistics Management. Vol. 34. 2004. pp.749-764. DOI: https://doi.org/10.1108/09600030410567504
A. Donati, R. Montemanni, N. Casagrande, A. Rizzoli, L. Gambardella. “Time Dependent Vehicle Routing Problem with a Multi Ant Colony System”. European Journal of Operational Research. Vol. 185. 2008. pp. 1174-1191. DOI: https://doi.org/10.1016/j.ejor.2006.06.047
A. Haghani, S. Jung. “A Dynamic Vehicle Routing Problem with Time-Dependent Travel Times”. Computers & Operations Research. Vol. 32. 2005. pp. 2959-2986. DOI: https://doi.org/10.1016/j.cor.2004.04.013
M. Khouadjia, B. Sarasola, E. Alba, L. Jourdan, E. Talbi. “A Comparative Study Between Dynamic Adapted PSO and VNS for the Vehicle Routing Problem with Dynamic Requests”. Applied Soft Computing. Vol. 12. 2012. pp. 1426-1439. DOI: https://doi.org/10.1016/j.asoc.2011.10.023
M. Gendreau, G. Laporte, R. Seguin. “Stochastic Vehicle Routing”. European Journal of Operational Research. Vol. 88. 1996. pp. 3-12. DOI: https://doi.org/10.1016/0377-2217(95)00050-X
D. Papastavrou. “A Stochastic and Dynamic Routing Policy Using Branching Processes with State Dependent Immigration”. European Journal of Operational Research. Vol. 95. 1996. pp. 167-177. DOI: https://doi.org/10.1016/0377-2217(95)00189-1
N. Secomandi. “Comparing Neuro-Dynamic Programming Algorithms for the Vehicle Routing Problem with Stochastic Demands”. Computers & Operations Research. Vol. 27. 2000. pp. 1201-1225. DOI: https://doi.org/10.1016/S0305-0548(99)00146-X
B. Moghaddam, R. Ruiz, S. Sadjadi. “Vehicle Routing Problem with Uncertain Demands: An Advanced Particle Swarm Algorithm”. Computers & Industrial Engineering. Vol. 62. 2012. pp. 306-317. DOI: https://doi.org/10.1016/j.cie.2011.10.001
L. Coslovich, R. Pesenti, W. Ukovich. “A Two-Phase Insertion Technique of Unexpected Customers for a Dynamic Dial-A-Ride Problem”. European Journal of Operational Research. Vol. 175. 2006. pp. 1605-1615, DOI: https://doi.org/10.1016/j.ejor.2005.02.038
T. Du, E. Li, D. Chou. “Dynamic Vehicle Routing for Online B2C Delivery”. Omega. Vol 33. 2005. pp. 33- 45. DOI: https://doi.org/10.1016/j.omega.2004.03.005
B. Fleischmann, M. Gietz, S. Gnutzmann. “TimeVarying Travel Times in Vehicle Routing”. Transportation Science. Vol. 38. 2004. pp. 160-173. DOI: https://doi.org/10.1287/trsc.1030.0062
S. Ichoua, M. Gendreau, J. Potvin. “Vehicle Dispatching with Time-Dependent Travel Times”. European Journal of Operational Research. Vol. 144. 2003. pp. 379-396. DOI: https://doi.org/10.1016/S0377-2217(02)00147-9
A. Kok, E. Hans, J. Schutten. “Vehicle Routing under Time-Dependent Travel Times: The Impact of Congestion Avoidance”. Computers & Operations Research. Vol. 39. 2012. pp. 910-918. DOI: https://doi.org/10.1016/j.cor.2011.05.027
J. Potvin, Y. Xu, I. Benyahia. “Vehicle Routing and Scheduling with Dynamic Travel Times”. Computers & Operations Research. Vol. 33. 2006. pp. 1129-1137. DOI: https://doi.org/10.1016/j.cor.2004.09.015
S. Lorini, J. Potvin, N. Zufferey. “Online Vehicle Routing and Scheduling with Dynamic Travel Times”. Computers & Operations Research. Vol. 38. 2011. pp. 1086-1090. DOI: https://doi.org/10.1016/j.cor.2010.10.019
B. Dean. “Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms”. Technical report. 1999. Available in: http://www.cs.clemson.edu/~bcdean/paper23.html. Last access: June 13, 2011.
K. Sung, M. Bell, M. Seong, S. Park. “Shortest Paths in a Network with Time-Dependent Flow Speeds”. European Journal of Operational Research. Vol. 121. 2000. pp. 32-39. DOI: https://doi.org/10.1016/S0377-2217(99)00035-1
M. Dorigo, M. Gambardella. “Ant Colonies for the Traveling Salesman Problem”. BioSystems Vol. 43. 1997. pp. 73-81. DOI: https://doi.org/10.1016/S0303-2647(97)01708-5
M. Dorigo, E. Bonabcau, G. Theraulaz. “Ant Algorithms and Stigmergy”. Future Generation Computer System. Vol. 16. 2000. pp. 851-871. DOI: https://doi.org/10.1016/S0167-739X(00)00042-X
M. Solimanpur, P. Vrat, R. Shankar. “Ant Colony Optimization Algorithm to the Inter-Cell Layout Problem in Cellular Manufacturing”. European Journal of Operational Research. Vol. 157. 2004. pp. 592-606. DOI: https://doi.org/10.1016/S0377-2217(03)00248-0
Y. Liang, E. Smith. “An Ant Colony Optimization Algorithm for the Redundancy Allocation Problem (RAP)”. IEEE Transactions on reliability. Vol. 53. 2004. pp. 417-423. DOI: https://doi.org/10.1109/TR.2004.832816
K. Doerner, M. Gronalt, R. Hartl, M. Reimann, C. Strauss, M. Stummer. Savings Ants for the Vehicle Routing Problem. S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, G. R. Raidl (editors). Application of Evolutionary Computing. Springer LNCS 2279. Berlin/Heidelberg, Germany. 2002. pp. 11-20. DOI: https://doi.org/10.1007/3-540-46004-7_2
E. Bell, R. McMullen. ìAnt Colony Optimization Techniques for the Vehicle Routing Problemî. Advanced Engineering Informatics. Vol. 18. 2004. pp. 41-48. DOI: https://doi.org/10.1016/j.aei.2004.07.001
C. Chen, C. Ting, P. Chang. “Applying a Hybrid Ant Colony System to the Vehicle Routing Problem”. Computational Science and Its Applications- ICCSA. Vol. 3483. 2005. pp. 417-426. DOI: https://doi.org/10.1007/11424925_45
S. Huang, P. Lin. “A Modified Ant Colony Optimization Algorithm for Multi-Item Inventory Routing Problems with Demand Uncertainty”. Transportation Research Part E. Vol. 46. 2010. pp. 598-611. DOI: https://doi.org/10.1016/j.tre.2010.01.006
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2018 Revista Facultad de Ingeniería
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Revista Facultad de Ingeniería, Universidad de Antioquia is licensed under the Creative Commons Attribution BY-NC-SA 4.0 license. https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en
You are free to:
Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material
Under the following terms:
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
NonCommercial — You may not use the material for commercial purposes.
ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
The material published in the journal can be distributed, copied and exhibited by third parties if the respective credits are given to the journal. No commercial benefit can be obtained and derivative works must be under the same license terms as the original work.
Twitter