Abstract
The Vehicle Routing Problem with Time Windows (VRPTW) involves scheduling and routing of a vehicle fleet to serve a given set of geographically distributed requests, subject to capacity and time constraints. This problem is encountered in a variety of industrial and service applications, ranging from logistics and transportation systems, to material handling systems in manufacturing. Due to the intrinsic complexity of the problem, heuristics are needed for analyzing and solving it under practical problem sizes. In this paper, a model of an Ant Colony System (ACS) is proposed to solve the VRPTW. The aim here is to investigate and analyze the performance of the foraging model of a single colony ACS to solve the VRPTW from an experimental point of view, with particular emphasis on different initial solution techniques and different visibility (desirability) functions. Finally, experimental analyses are performed to compare the proposed model to other metaheuristic techniques. The results show that the single colony ACS algorithm, despite its simple model, is quite competitive to other well know metaheuristic techniques.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bonabeau, E., Dorigo, M. and Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. New York: Oxford University Press (1999).
Bullnheimer, B., Hartl, R. and Strauss, C: Applying the Ant System to the Vehicle Routing Problem. In: Voss S., Martello S., Osman I.H., Roucairol C. (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer: Boston (1997).
Bullnheimer, B., Hartl, R. and Strauss, C.: An improved ant system algorithm for the vehicle routing problem. Paper presented at the Sixth Viennese workshop on Optimal Control, Dynamic Games, Nonlinear Dynamics and Adaptive Systems, Vienna (Austria), May 21–23, 1997, to appear in: Annals of Operations Research, Dawid, Feichtinger and Hartl (eds.): Nonlinear Economic Dynamics and Control, (1999).
Chiang, W. and Russell, R.: Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows, Annals of Oper. Res. 63, (1996), 1–29.
Chiang, W. and Russell, R.: A reactive tabu search metaheuristic for the vehicle routing problem with time windows, INFORMS J. on Computing 9, 4 (1997).
Cordeau, J.-F., Desrosiers, G., Solomon, M. and Soumis, F., “The VRP with Time Windows”, in The Vehicle Routing Problem, Chapter 7, Paolo Toth and Daniele Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, 157–193, 2002.
Desrochers, M., Lenstra, J., Savelsbergh, J. and Soumis, F.: Vehicle routing with time windows: Optimization and approximation, in: B.L. Golden and AA. Assad(eds.), Vehicle Routing: Methods and Studies, North-Holland, Amsterdam, (1988), 85–105.
Desrosiers, J. Dumas, Y., Solomon, M., Soumis, F., Time constrained routing and scheduling, in: M. Ball, T. Magnanti, M. Monma, G. Nemhauser (Eds.), Handbooks in Operations Research and Management Science, vol. 8: Network Routing, Netherlands, Amsterdam, (1995), 35–139.
Dorigo, M., Maniezzo V., and Colorni, A.: The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans. Sys. Man Cyb. B 26 (1996), 29–41.
Dorigo, M., Gambardella, L.: Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Trans. Evol. Comp. 1, No.1 (1997), 53–66.
Drop, M., Note on the complexity of the shortest path models for column generation in VRPTW, Operations Research 42, 5 (1994).
Taillard, E. Badeau, P. Gendreau, M., Guertin, F. and Potvin, J.: A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, Transportation Science 31, 2, (1997).
Gambardella, L., Taillard, E. and Agazzi, G.: MACS-VRPTW: A multiple Ant Colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization. McGraw-Hill (Also available as, Tech. Rep. IDSIA-06-99, IDSIA, Lugano, Switzerland), (1999).
Lenstra, J. and Rinnooy Kan, A.: Complexity of Vehicle Routing and Scheduling Problems, Networks 11, (1981), 221–227.
Solomon, M.: Algorithms for the vehicle Routing and Scheduling Problems with Time Window constraints, Operations research 35, (1987), 254–265.
Thangiah, S., Osman, I. and Sun, T.,:Hybrid Genetic Algorithm, Simulated Annealing, and Tabu Search Methods for Vehicle Routing Problems with Time Windows. Technical Report 27, Computer Science Department, Slippery Rock University (1994).
Tan, K.C., Lee, Q.L., Zhu, K.,Ou: Heuristic methods for vehicle routing problem with time windows, Artificial Intelligence in Engineering 15, Elsevier, (2001), 281–295.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ellabib, I., Basir, O.A., Calamai, P. (2002). An Experimental Study of a Simple Ant Colony System for the Vehicle Routing Problem with Time Windows. In: Dorigo, M., Di Caro, G., Sampels, M. (eds) Ant Algorithms. ANTS 2002. Lecture Notes in Computer Science, vol 2463. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45724-0_5
Download citation
DOI: https://doi.org/10.1007/3-540-45724-0_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44146-5
Online ISBN: 978-3-540-45724-4
eBook Packages: Springer Book Archive