International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN.  International E-Bulletin: Information/News regarding: Academics and Research

A two Phase Approach for solving Dynamic Capacitated Vehicle Routing Problem with Time Windows

Author Affiliations

  • 1Department of industrial management, Science and Research Branch, Islamic Azad University, Tehran, IRAN

Res. J. Recent Sci., Volume 4, Issue (3), Pages 34-40, March,2 (2015)

Abstract

In this paper, a two phase algorithm for solving the dynamic capacitated vehicle routing problems with soft time windows is proposed. In phase one an ant colony optimization algorithm is used to find solution for static data of problem. In second phase, an improved heuristic algorithm based on insertion heuristic is used to solve the problem in presence of dynamic arrivals of new customer orders. The proposed algorithm has been performed on the Solomon R and RC problems. The results are evaluated through a measure denoted as the value of information. Evaluating the solution by two factors (objective function and no. of vehivles) indicate that the results of the proposed algorithm are approximately equal to the solution of static problem for degree of dynamism of 10% in problem R1,R2,RC1 and appropriate for the other situation.

References

  1. Psaraftis H., Dynamic vehicle routing: status and prospects, Annals of Opertations Reasearch, 61, 143–164 (1995)
  2. Ghiani G., Guerriero F., Laporte G. and Musmanno R., Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies, European Journal of Operational Research, 151 (1), 1–11 (2003)
  3. Ichoua, S., Gendreau, M., Potvin J.Y., Diversion issues in real-time vehicle dispatching, Transportation Science,34 (4), 426–438 (2000)
  4. Attanasio A., Cordeau J.F., Ghiani G. and Laporte G., Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem, Parallel Computing, 30(3), 377–387, (2004)
  5. 5.Ichoua S., Gendreau M. and Potvin J.Y., Exploiting knowledge about future demands for real-time vehicle dispatching, Transportation Science, 40(2), 211–225 (2006)
  6. Kergosien Y., Lent Ch., Piton D. and Billaut J.C., A tabu search heuristic for the dynamic transportation of patients between care units, European Journal of Operational Research,214, 442–452 (2011)
  7. Nguyen P.K, Crainic T.G. and Toulouse M., Atabu search for Time-dependent Multi-zone Multi-trip Vehicle Routing Problem with Time Windows, European Journal of Operational Research,(2013)
  8. Haghani A. and Jung S., A dynamic vehicle routing problem with time-dependent travel times, Computers and Operations Research, 32(11), 2959 – 2986 (2005)
  9. Barkaoui M., Gendreau M., An adaptive evolutionary approach for real-time vehicle routing and dispatching, Computers and Operations Research, 40, 1766–1776 (2013)
  10. Malandraki C. and Daskin M., Time dependent vehicle routing problems: formulations, properties and heuristic algorithm, Transportation Science, 26(3), 185–200 (1992)
  11. Fleischmann B., Gietz M. and Gnutzmann S., Time-varying travel times in vehicle routing, Transportation Science, 38(2), 160–73 (2004)
  12. Chen B., Song S. and Chen X., Multi-Ant Colony System for Vehicle Routing Problem with Time-Dependent Travel Times, Proceedings of the IEEE International Conference on Automation and Logistics,18–21 (2007)
  13. Donati A.V., Montemanni R., Casagrande N., Rizzoli A.E. and Gambardella L. M., Time dependent vehicle routing problem with a multi ant colony system, European Journal of Operational Research,185, 1174–1191 (2008)
  14. Yang J., Jaillet P. and Mahmassani H., Realtime multi vehicle truckload pickup and delivery problems, Transportation Science, 38(2), 135–148 (2004)
  15. Bent R. and Van Hentenryck P., Scenariobased planning for partially dynamic vehicle routing with stochastic customers, Operations Research, 52(6) 977–987 (2004b)
  16. Dorigo M. and Gambardella L.M., Ant Colony System : A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, , 53–66 (1997)
  17. Solomon M.M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res, 35, 254–265 (1987)
  18. Solomon Benchmark Problems http://web.cba.neu.edu/_msolomon/problems.html, (2014)
  19. Mitrovic-Minic S. and Laporte G., Waiting strategies for the dynamic pickup and delivery problem with time windows, Transportation Research Part B: Methodological, 38(7), 635–655 (2004)