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.
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
Guest Editor: Eleonora Papadimitriou, PhD
Editors: Dario Babić, PhD; Marko Matulin, PhD; Marko Ševrović, PhD.
The mission of our journal is to provide high quality communication of research results, which is crucial for the effectiveness of scientific research, the promotion of scientific information, new ideas, and original research in the field of traffic and transportation engineering.
1848-4069
0353-5320
Proud publisher
Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal
