Solving Practical Vehicle Routing Problem with Time Windows Using Metaheuristic Algorithms

  • Filip Taner
  • Ante Galić
  • Tonči Carić
Keywords: vehicle routing problem with time windows, simulated annealing, iterated local search, metaheuristcs,

Abstract

This paper addresses the Vehicle Routing Problem with Time Windows (VRPTW) and shows that implementing algorithms for solving various instances of VRPs can significantly reduce transportation costs that occur during the delivery process. Two metaheuristic algorithms were developed for solving VRPTW: Simulated Annealing and Iterated Local Search. Both algorithms generate initial feasible solution using constructive heuristics and use operators and various strategies for an iterative improvement. The algorithms were tested on Solomon’s benchmark problems and real world vehicle routing problems with time windows. In total, 44 real world problems were optimized in the case study using described algorithms. Obtained results showed that the same distribution task can be accomplished with savings up to 40% in the total travelled distance and that manually constructed routes are very ineffective.

References

Toth, P., Vigo, D.: Vehicle Routing Problem, SIAM Publishing, monographs on discrete mathematics and applications, Philadelphia, 2002

Bräysy, O., Gendreau, M.: Vehicle Routing Problem with Time Windows Part I: Route Construction and Local Search Algorithms, Transportation Science, Vol. 39, No. 1, 2005, pp. 104-118

Bräysy, O., Gendreau, M.: Vehicle Routing Problem with Time Windows, Part II, Metaheuristics, Transportation Science, Vol. 39, No. 1, 2005, pp. 119-139.

Golden, B., Raghavan, S., Wasil, E.: The Vehicle Routing Problem, Latest Advances and New Challenges, Springer, 2008.

Nagata, Y., Bräysy, O., Dullaert, W.: A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Computers and Operations Research, Vol. 37, 2010, pp. 724-737.

Cordeau, J.F., Desaulniers G., Desrosiers, J., Solomon, M., Soumis, F.: The VehicleRouting Problem with Time Windows. Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem,. SIAM Publishing, Philadelphia, 2002, pp. 157–193

Solomon, M.: Algorithms for the Vehicle Routing and Scheduling Problems with a Time Windows Constraints. Operations Research. Vol. 35, 1987, pp. 254–265

Carić, T., Galić A., Fosin, J., Gold, H., Reinholz, A.: A Modelling and Optimization Framework for Real-World Vehicle Routing Problems: Carić T., Gold H. (eds.) Vehicle Routing Problem, I-TECH, Vienna, 2008, pp. 15-34

Kirkpatrick, S., Gelatt, C.D., Vecchi, Jr. M.P.: Optimization by Simulated Annealing, Science, 220, 1983, pp. 671–680

Cerny, V.: A Thermodynamical Approach to the Travelling Salesman Problem: An Efficient Simulation Algorithm, Journal of Optimization Theory and Applications 45, 1985, pp. 41–51

Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H.: Equations of State Calculations by Fast Computing Machines. The Journals of Chemical Physics 21, 1953, pp. 1087–1092

Hoos, H.H., Stutzle, T.: Stochastic local search, foundations and applications, Elsevier, Morgran Kaufmann, 2005

Carić, T., Fosin, J., Galić, A., Gold, H., Reinholz, A.: Empirical Analysis of Two Different Metaheuristics for Real-World Vehicle Routing Problems, Bartz-Beielstein T. et al. (Eds.): Hybrid Metaheuristics 2007, Lecture Notes in Computer Science (LNCS), Springer-Verlag, Berlin Heidelberg 2007 4771, pp. 31–44

Solomon benchmark available from web page (last accessed on July 2011): http://www.sintef.no/Projectweb/TOP/Problems/VRPTW/Solomon-benchmark/

Homberger, J., Gehring, H.: A two-phase hybrid metaheuristic for the vehicle routing problem with time windows, European Journal of Operational Research, Vol. 162, No. 1, 2005 pp. 220–238

Le Bouthillier, A., Crainic, T.G.: Cooperative parallel method for vehicle routing problems with time windows. Computers and Operations Research, Vol. 32, No. 7, 2005, pp. 1685-1708

Pisinger, D., Röpke, S.: A general heuristic for vehicle routing problems. Technical Report, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark, 2005

Mester, D., Bräysy, O., Dullaert, W: A multi-parametric evolution strategies algorithm for vehicle routing problems. Expert Systems with Applications, Vol. 32, No. 2, 2007, pp. 508-517

How to Cite
1.
Taner F, Galić A, Carić T. Solving Practical Vehicle Routing Problem with Time Windows Using Metaheuristic Algorithms. PROMET [Internet]. 1 [cited 2019Aug.23];24(4):343-51. Available from: http://traffic.fpz.hr/index.php/PROMTT/article/view/443
Section
Older issues