Abstract
Cellular Genetic Algorithms (cGAs) are a subclass of Genetic Algorithms (GAs) in which the population diversity and exploration are enhanced thanks to the existence of small overlapped neighborhoods. Such kind of structured algorithms is well suited for complex problems. In this paper, a cGA for solving the vehicle routing problem with time windows (VRPTW) is proposed. The benchmark of Solomon is selected for testing the proposed cGAs, and compares them with some other heuristics in the literature. The results demonstrate that the proposed cGA has a good potential for solving this kind of problems.
This is a preview of subscription content, log in via an institution to check access.
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
Berger, J., Barkaoui, M., Bräysy, O.: A parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows, working paper, Defence Research Establishment Velcartier, Canada (2001)
Bodin, L., Golden, B., Assad, A., Ball, M.: The State of the Art in the Routing and Scheduling of Vehicles and Crews. Computers and Operations Rsearch 10(2), 63–211 (1983)
Chiang, W.C., Russel, R.: Hybrid Heuristics for the Vehicle Routing Problem with Time Windows, Working Paper, Department of Quantitative Methods, University of Tulsa, OK, USA (1993)
Gambardella, L.M., Tillard, E., Agazzi, G.: MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. Mcgraw-Hill’S Advanced Topics In Computer Science Series, pp. 63–67 (1999)
Golden, B., Assad, A. (eds.): Vehicle Routing: Methods and Studies. North Holland, Amsterdam (1988)
Potvin, J.-Y., Bengio, S.: The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing 8, 165–172 (1996)
Rochat, Y., Taillard, É.D.: Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics 1, 147–167 (1995)
Solomon, M.M., Desrosiers, J.: Time Window Constrained Routing and Scheduling Problems: A Survey. Transportation Science 22(1), 1–11 (1986)
Taillard, É.D., Badeau, P., Gendreau, M., Guertin, F., Potvin, J.-Y.: A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Transportation Science 31, 170–186 (1997)
Whitley, D.: Cellular genetic algorithms. In: Forrest, S. (ed.) Proceedings of the 5th ICGA, p. 658. Morgan-Kaufmann, CA (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kamkar, I., Poostchi, M., Akbarzadeh Totonchi, M.R. (2010). A Cellular Genetic Algorithm for Solving the Vehicle Routing Problem with Time Windows. In: Gao, XZ., Gaspar-Cunha, A., Köppen, M., Schaefer, G., Wang, J. (eds) Soft Computing in Industrial Applications. Advances in Intelligent and Soft Computing, vol 75. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11282-9_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-11282-9_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11281-2
Online ISBN: 978-3-642-11282-9
eBook Packages: EngineeringEngineering (R0)