A model for solving the dynamic vehicle dispatching problem with customer uncertainty and time dependent link travel time

Authors

  • Shan-Huen Huang National Kaohsiung First University of Science and Technology (NKFUST)
  • Carola Alejandra Blazquez Universidad Andres Bello

Keywords:

Heuristics, dynamic vehicle routing, customer uncertainty, vehicle routing problem

Abstract


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.

|Abstract
= 17 veces | PDF (ESPAÑOL (ESPAÑA))
= 22 veces|

Downloads

Download data is not yet available.

References

D. Bertsimas, D. Simchi. “A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty”. Operations Research. Vol. 44. 1996. pp. 286-304.

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.

G. Ghiani, G. Improta. “An Efficient Transformation of the Generalized Vehicle Routing Problemî. European Journal of Operational Research. Vol. 122. 2000. pp. 11-17.

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.

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.

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.

A. Haghani, S. Jung. “A Dynamic Vehicle Routing Problem with Time-Dependent Travel Times”. Computers & Operations Research. Vol. 32. 2005. pp. 2959-2986.

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.

M. Gendreau, G. Laporte, R. Seguin. “Stochastic Vehicle Routing”. European Journal of Operational Research. Vol. 88. 1996. pp. 3-12.

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.

N. Secomandi. “Comparing Neuro-Dynamic Programming Algorithms for the Vehicle Routing Problem with Stochastic Demands”. Computers & Operations Research. Vol. 27. 2000. pp. 1201-1225.

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.

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,

T. Du, E. Li, D. Chou. “Dynamic Vehicle Routing for Online B2C Delivery”. Omega. Vol 33. 2005. pp. 33- 45.

B. Fleischmann, M. Gietz, S. Gnutzmann. “TimeVarying Travel Times in Vehicle Routing”. Transportation Science. Vol. 38. 2004. pp. 160-173.

S. Ichoua, M. Gendreau, J. Potvin. “Vehicle Dispatching with Time-Dependent Travel Times”. European Journal of Operational Research. Vol. 144. 2003. pp. 379-396.

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.

J. Potvin, Y. Xu, I. Benyahia. “Vehicle Routing and Scheduling with Dynamic Travel Times”. Computers & Operations Research. Vol. 33. 2006. pp. 1129-1137.

S. Lorini, J. Potvin, N. Zufferey. “Online Vehicle Routing and Scheduling with Dynamic Travel Times”. Computers & Operations Research. Vol. 38. 2011. pp. 1086-1090.

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.

M. Dorigo, M. Gambardella. “Ant Colonies for the Traveling Salesman Problem”. BioSystems Vol. 43. 1997. pp. 73-81.

M. Dorigo, E. Bonabcau, G. Theraulaz. “Ant Algorithms and Stigmergy”. Future Generation Computer System. Vol. 16. 2000. pp. 851-871.

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.

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.

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.

E. Bell, R. McMullen. ìAnt Colony Optimization Techniques for the Vehicle Routing Problemî. Advanced Engineering Informatics. Vol. 18. 2004. pp. 41-48.

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.

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.

Published

2012-10-04

How to Cite

Huang, S.-H., & Blazquez, C. A. (2012). A model for solving the dynamic vehicle dispatching problem with customer uncertainty and time dependent link travel time. Revista Facultad De Ingeniería Universidad De Antioquia, (64), 163–174. Retrieved from https://revistas.udea.edu.co/index.php/ingenieria/article/view/13114