Abstract
This paper is concerned with a dynamic vehicle routing problem. The problem is dynamic in the sense that the time it will take to traverse each edge is uncertain. The problem is expressed as a bi-criterion optimisation with the mutually exclusive aims of minimising both the total mean transit time and the total variance in transit time. In this paper we introduce a hybrid dynamic programming – ant colony optimisation technique to solve this problem. The hybrid technique uses the principles of dynamic programming to first solve simple problems using ACO (routing from each adjacent node to the end node), and then builds on this to eventually provide solutions (i.e. Pareto fronts) for routing between each node in the network and the destination node. However, the hybrid technique updates the pheromone concentrations only along the first edge visited by each ant. As a result it is shown to provide the overall solution in quicker time than an established bi-criterion ACO technique, that is concerned only with routing between the start and destination nodes. Moreover, we show that the new technique both determines more routes on the Pareto front, and results in a 20% increase in solution quality for both the total mean transit time and total variance in transit time criteria. However the main advantage of the technique is that it provides solutions in routing between each node to the destination node. Hence it allows “instantaneous” re-routing subject to dynamic changes within the road network.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, Chichester (1999)
Beasley, J.E., Christofides, N.: An Algorithm for the Resource Constrained Shortest Path Problem. Networks 19, 379–394 (1989)
Dorigo, M., Maniezzo, V., Colorni, A.: The Ant System: An Autocatalytic Optimizing Process. Technical Report 91-016 (revised), Politecnico di Milano, Italy (1991)
Colorni, A., Dorigo, M., Maniezzo, V.: Distributed Optimization by Ant Colonies. In: Varela, F., Bourgine, P. (eds.) Proceedings of the European Conference on Artificial Life, Elsevier, Amsterdam (1991)
Denebourg, J.L., Pasteels, J.M., Verhaeghe, J.C.: Probabilistic Behaviour in Ants: a Strategy of Errors? Journal of Theoretical Biology 105, 259–271 (1983)
Costa, D., Hertz, A.: Ants can colour graphs. Journal of the Operational Research Society 48, 295 (1997)
Bullnheimer, B., Kotsis, G., Strauss, C.: Applying the Ant System to the Vehicle Routing Problem. In: Proceedings of the Second International Conference on Metaheuristics (1997)
Bullnheimer, B., Hartl, R.F., Strauss, C.: An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research 89, 319–328 (1999)
Schoonderwoerd, R., Holland, O., Bruten, J.: Ants for load balancing in telecommunications networks. Hewlett Packard Laboratory Technical Report (1996)
Di Caro, G., Dorigo, M.: AntNet: Distributed Stigmergetic Control for Communications Networks. Journal of Artificial Intelligence Research 9, 317–365 (1998)
Guntsch, M., Middendorf, M., Schmeck, H.: An Ant Colony Optimization Approach to Dynamic TSP. In: Proceeedings of the Genetic and Evolutionary Computation Conference, pp. 860–867 (2001)
Jungnickel, D.: Graphs, Networks and Algorithms. Springer, Heidelberg (1998)
Iredi, S., Merkle, D., Middendorf, M.: Bi-Criterion Optimization with Multi Colony Ant Algorithms. In: Zitzler, E. (ed.) Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, Springer, Heidelberg (2001)
Maniezzo, V., Colorni, A., Dorigo, M.: The Ant System Applied to the Quadratic Assignment Problem. Technical Report IRIDIA/94-28, Universite Libre de Bruxelles (1994)
Colorni, A., Dorigo, M., Maniezzo, V., Trubian, M.: Ant System for Job Shop Scheduling. Belgian Journal of Operations Research, Statistics, and Computer Science 34, 39 (1994)
Parpinelli, R.S., Lopes, H.S., Freitas, A.A.: An Ant Colony Based System for Data Mining: Applications to Medical Data. In: Proceeedings of the Genetic and Evolutionary Computation Conference, pp. 791–797 (2001)
Bellman, R.E.: Dynamic Programming. Princeton University Press, Princeton (1957)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chitty, D.M., Hernandez, M.L. (2004). A Hybrid Ant Colony Optimisation Technique for Dynamic Vehicle Routing. In: Deb, K. (eds) Genetic and Evolutionary Computation – GECCO 2004. GECCO 2004. Lecture Notes in Computer Science, vol 3102. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24854-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-24854-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22344-3
Online ISBN: 978-3-540-24854-5
eBook Packages: Springer Book Archive