Solving Practical Vehicle Routing Problem with Time Windows Using Metaheuristic Algorithms
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
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
