State-of-the Art Review—Evolutionary Algorithms for Vehicle Routing

References

• Alba E., Dorronsoro B., Gottlieb J., Raidl G. R. Solving the vehicle routing problem by using cellular genetic algorithms. Evolutionary Computation in Combinatorial Optimization (2004) 3004(Springer-Verlag, Berlin) 11–20Lecture Notes in Computer ScienceCrossref, Google Scholar
• Alba E., Dorronsoro B. Computing nine new best-so-far solutions for capacitated VRP with a cellular genetic algorithm. Inform. Processing Lett. (2006) 98(6):225–230Crossref, Google Scholar
• Alvarenga G. B., Mateus G. R., Ishikawa M., Hashimoto S., Paprzycki M., Barakova E., Yoshida K., Köppen M., Corne D. W., Abraham A. A two-phase genetic and set partitioning approach for the vehicle routing problem with time windows. Proc. Fourth Internat. Conf. Hybrid Intelligent Systems (2004a) (IEEE Computer Society Press, Los Alamitos, CA) 428–433Crossref, Google Scholar
• Alvarenga G. B., Mateus G. R., Ishikawa M., Hashimoto S., Paprzycki M., Barakova E., Yoshida K., Köppen M., Corne D. W., Abraham A. Hierarchical tournament selection genetic algorithm for the vehicle routing problem with time windows. Proc. Fourth Internat. Conf. Hybrid Intelligent Systems (2004b) (IEEE Computer Society Press, Los Alamitos, CA) 410–415Crossref, Google Scholar
• Alvarenga G. B., de Abreu Silva R. M., Sampaio R. M. A hybrid algorithm for the vehicle routing problem with time window. INFOCOMP J. Comput. Sci. (2005) 4(2):9–16Google Scholar
• Alvarenga G. B., Mateus G. R., de Tomi G. A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Comput. Oper. Res. (2007) 34(6):1561–1584Crossref, Google Scholar
• Augerat P., Belenguer J. M., Benavent E., Corberán A., Naddef D., Rinaldi G. Computational results with a branch-and-cut code for the capacitated vehicle routing problem. (1995) . Research Report 949-M, Université Joseph Fourier, Grenoble, FranceGoogle Scholar
• Baker B. M., Ayechew M. A. A genetic algorithm for the vehicle routing problem. Comput. Oper. Res. (2003) 30(5):787–800Crossref, Google Scholar
• Bean J. C. Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. (1994) 6(2):154–160Link, Google Scholar
• Bent R., Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Sci. (2004) 38(4):515–530Link, Google Scholar
• Benyahia I., Potvin J.-Y. Generalization and refinement of route construction heuristics using genetic algorithms. IEEE Internat. Conf. Evolutionary Comput. (1995) 1Perth, Australia(IEEE Press, Piscataway, NJ) 39–43Crossref, Google Scholar
• Benyahia I., Potvin J.-Y. Decision support for vehicle dispatching using genetic programming. IEEE Trans. Systems, Man Cybernetics A (1998) 28(3):306–314Crossref, Google Scholar
• Berger J., Barkaoui M., Cantú-Paz E., Foster J. A., Deb K., Davis L. D., Roy R., O'Reilly U.-M., Beyer H. G., et al. A hybrid genetic algorithm for the capacitated vehicle routing problem. Proc. Genetic and Evolutionary Comput. Conf. (2003a) 2723(Springer-Verlag, Berlin) 646–656Lecture Notes in Computer ScienceCrossref, Google Scholar
• Berger J., Barkaoui M. A new hybrid genetic algorithm for the capacitated vehicle routing problem. J. Oper. Res. Soc. (2003b) 54(12):1254–1262Crossref, Google Scholar
• Berger J., Barkaoui M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Comput. Oper. Res. (2004) 31(12):2037–2053Crossref, Google Scholar
• Berger J., Barkaoui M., Bräysy O. A route-directed hybrid genetic approach for the vehicle routing problem with time windows. INFOR (2003) 41(2):179–194Google Scholar
• Berger J., Salois M., Bégin R., Mercer R. E., Neufeld E. A hybrid genetic algorithm for the vehicle routing problem with time windows. Advances in Artificial Intelligence (1998) 1418(Springer-Verlag, London) 114–127Lecture Notes in Computer ScienceCrossref, Google Scholar
• Berger J., Sassi M., Salois M., Banhaf W., Daida J. M., Eiben A. E., Garzon M. H., Honavar V., Jakiela M. J., Smith R. E. A hybrid genetic algorithm for the vehicle routing problem with time windows and itinerary constraints. Proc. Genetic and Evolutionary Comput. Conf. (1999) (Morgan Kaufmann, San Francisco) 44–51Google Scholar
• Beyer H.-G., Schwefel H.-P. Evolution strategies: A comprehensive introduction. Natural Comput. (2002) 1(1):3–52Crossref, Google Scholar
• Blanton J. L., Wainwright R. L., Forrest S. Multiple vehicle routing with time and capacity constraints using genetic algorithms. Proc. Fifth Internat. Conf. Genetic Algorithms (1993) (Morgan Kaufmann, San Mateo, CA) 451–459Google Scholar
• Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surveys (2003) 35(3):268–308Crossref, Google Scholar
• Brandao de Oliveira H. C., Alexandrino J. L., Moreira de Souza M. Memetic and genetic algorithms: A comparison among different approaches to solve vehicle routing problem with time windows. Internat. Conf. Hybrid Intelligent Systems (2006) Auckland, New Zealand(IEEE Computer Society Press, Los Alamitos, CA) 55Crossref, Google Scholar
• Bräysy O. A reactive variable neighborhood search for the vehicle routing problem with time windows. INFORMS J. Comput. (2003) 15(4):347–368Link, Google Scholar
• Bräysy O., Dullaert W. A fast evolutionary metaheuristic for the vehicle routing problem with time windows. Internat. J. Artificial Intelligence Tools (2003) 12(2):153–172Crossref, Google Scholar
• Bräysy O., Gendreau M. Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation Sci. (2005) 39(1):119–139Link, Google Scholar
• Bräysy O., Berger J., Barkaoui M. A new hybrid evolutionary algorithm for the vehicle routing problem with time windows. Route 2000 Workshop (2000) Skodsborg, Denmark(Technical University of Denmark, Lyngby) Google Scholar
• Bräysy O., Dullaert W., Gendreau M. Evolutionary algorithms for the vehicle routing problem with time windows. J. Heuristics (2004a) 10(6):587–611Crossref, Google Scholar
• Bräysy O., Hasle G., Dullaert W. A multi-start local search algorithm for the vehicle routing problem with time windows. Eur. J. Oper. Res. (2004b) 159(3):586–605Crossref, Google Scholar
• Calégari P., Coray G., Hertz A., Kobler D., Kluonen P. A taxonomy of evolutionary algorithms in combinatorial optimization. J. Heuristics (1999) 5(2):145–158Crossref, Google Scholar
• Chang Y., Chen L. Solve the vehicle routing problem with time windows via a genetic algorithm. Discrete Continuous Dynamical Systems (2007) Supplement):240–249Google Scholar
• Chen A.-L., Yang G. K., Wu Z. M. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J. Zhejiang Univ. Sci. A (2006) 7(4):607–614Crossref, Google Scholar
• Chin A. J., Kit H. W., Lim A. A new GA approach for the vehicle routing problem. IEEE Internat. Conf. Tools Artificial Intelligence (1999) Chicago(IEEE Press, Piscataway, NJ) 307–310Crossref, Google Scholar
• Christofides N., Mingozzi A., Toth P., Christofides N., Mingozzi A., Toth P., Sandi C. The vehicle routing problem. Combinatorial Optimization (1979) (John Wiley & Sons, Chichester, UK) 315–338Google Scholar
• Clarke G., Wright J. W. Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. (1964) 12(4):568–581Link, Google Scholar
• Deb K., Agrawa S., Pratap A., Meyarivan T., Schoenauer M., Deb K., Rudolph G., Yao X., Lutton E., Mereb J. J., Schwefel H. P. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. Parallel Problem Solving from Nature PPSN VI (2000) 1917(Springer-Verlag, Berlin) 849–858Lecture Notes in Computer ScienceCrossref, Google Scholar
• Derigs U., Kaiser R. Applying the attribute based hill climber heuristic to the vehicle routing problem. Eur. J. Oper. Res. (2007) 177(2):719–732Crossref, Google Scholar
• Drummond L. M. A., Ochi L. S., Vianna D. S. An asynchronous parallel metaheuristic for the period vehicle routing problem. Future Generation Comput. Systems (2001) 17(4):379–386Crossref, Google Scholar
• Dueck G. New optimization heuristics: The great deluge algorithm and the record-to-record travel. J. Computational Phys. (1993) 104(1):86–92Crossref, Google Scholar
• Dueck G., Scheurer T. Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. J. Computational Phys. (1990) 90(1):161–175Crossref, Google Scholar
• Feillet D., Dejax P., Gendreau M. Traveling salesman problem with profits. Transportation Sci. (2005) 39(2):188–205Link, Google Scholar
• Filipec M., Skrlec D., Krajcar S. Darwin meets computers: New approach to multiple depot capacitated vehicle routing problem. IEEE Internat. Conf. Systems (1997) 1Man Cybernetics, Orlando, FL(IEEE Press, Piscataway, NJ) 421–426Crossref, Google Scholar
• Filipec M., Skrlec D., Krajcar S. An efficient implementation of genetic algorithms for constrained vehicle routing problem. IEEE Internat. Conf. Systems (1998) 3Man Cybernetics, San Diego(IEEE Press, Piscataway, NJ) 2231–2236Crossref, Google Scholar
• Filipec M., Skrlec D., Krajcar S. Genetic algorithm approach for multiple depot capacitated vehicle routing problem solving with heuristic improvements. Internat. J. Model. Simulation (2000) 20(4):320–328Crossref, Google Scholar
• Fisher M. L. Optimal solution of vehicle routing problems using minimum K-trees. Oper. Res. (1994) 42(4):626–642Link, Google Scholar
• Fox B. R., McMahon M. B., Rawlins G. J. E. Genetic operators for sequencing problems. Foundations of Genetic Algorithms (1991) (Morgan Kaufmann, San Mateo, CA) 284–300Crossref, Google Scholar
• Ganesh K., Narendran T. T. CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up. Eur. J. Oper. Res. (2007) 178(3):699–717Crossref, Google Scholar
• Gehring H., Homberger J., Miettinen K., Mäkelä M. M., Toivanen J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. Proc. EUROGEN99—Short Course on Evolutionary Algorithms Engrg. Comput. Sci. (1999) 57–64Reports of the Department of Mathematical Information Technology, No. A 2/1999, University of Jyväskylä, Jyväskylä, FinlandGoogle Scholar
• Gehring H., Homberger J. A parallel two-phase metaheuristic for routing problems with time windows. Asia-Pacific J. Oper. Res. (2001) 18:35–47Google Scholar
• Gehring H., Homberger J. Parallelization of a two-phase metaheuristic for routing problems with time windows. J. Heuristics (2002) 8(3):251–276Crossref, Google Scholar
• Gendreau M., Potvin J.-Y. Metaheuristics in combinatorial optimization. Ann. Oper. Res. (2005) 140(1):189–213Crossref, Google Scholar
• Gendreau M., Laporte G., Potvin J.-Y., Lenstra J. K., Aarts E. H. L. Vehicle routing: Modern heuristics. Local Search in Combinatorial Optimization (1997) (John Wiley & Sons, Chichester, UK) 311–336Google Scholar
• Gendreau M., Laporte G., Potvin J.-Y., Toth P., Vigo D. Metaheuristics for the capacitated VRP. The Vehicle Routing Problem (2002) (SIAM, Philadelphia) 129–154SIAM Series on Discrete Mathematics and ApplicationsCrossref, Google Scholar
• Gendreau M., Laporte G., Potvin J.-Y., Semet F., Pirlot M., Teghem J. Métaheuristiques pour le problème des tournées de véhicules. Résolution de Problèmes de RO par les Métaheuristiques (2003) (Hermès, Paris) 49–70Google Scholar
• Gendreau M., Potvin J.-Y., Bräysy O., Hasle G., Løkketangen A., Golden B. L., Raghavan S., Wasil E. Metaheuristics for the vehicle routing problem and extensions: A categorized bibliography. The Vehicle Routing Problem: Latest Advances and New Challenges (2008) (Springer, New York) 143–170Crossref, Google Scholar
• Glover F. Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Appl. Math. (1996) 65(1–3):223–253Crossref, Google Scholar
• Glover F., Laguna M.Tabu Search (1997) (Kluwer, Boston) Crossref, Google Scholar
• Goldberg D. E., Richardson J., Grefenstette J. J. Genetic algorithms with sharing for multimodal function optimization. Proc. Second Internat. Conf. Genetic Algorithms Their Appl. (1987) (Lawrence Erlbaum Associates, Hillsdale, NJ) 41–49Google Scholar
• Goldberg D. E., Richardson J., Grefenstette J. J. Alleles, loci, and the traveling salesman problem. Proc. First Internat. Conf. Genetic Algorithms Their Appl. (1988) (Lawrence Erlbaum Associates, Hillsdale, NJ) 154–159Google Scholar
• Goldberg D. E., Korb B., Deb K. Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems (1989) 3:493–530Google Scholar
• Golden B. L., Wasil E. A., Kelly J. P., Chao I.-M., Crainic T. G., Laporte G. The impact of metaheuristics on solving the vehicle routing problem: Algorithms, problem sets and computational results. Fleet Management and Logistics (1998) (Kluwer, Norwell, MA) 33–56Crossref, Google Scholar
• Haghani A., Jung S. A dynamic vehicle routing problem with time-dependent travel times. Comput. Oper. Res. (2005) 32(11):2959–2986Crossref, Google Scholar
• Han S. A hybrid meta-heuristic algorithm for vehicle scheduling problem: Genetic algorithm and tabu search. NUCB J. Econom. Inform. Sci. (2004) 48:343–358Google Scholar
• Han S., Tabata Y. A hybrid genetic algorithm for the vehicle routing problem with controlling lethal gene. Internat. J. Asian Pacific Management Rev. (2002) 7(3):287–298Google Scholar
• Hanshar F. T., Ombuki-Berman B. M. Dynamic vehicle routing using genetic algorithms. Appl. Intelligence (2007) 27(1):89–99Crossref, Google Scholar
• Ho W.-K., Chin J., Lim A. A hybrid search algorithm for the vehicle routing problem with time windows. Internat. J. Artificial Intelligence Tools (2001) 10(3):431–449Crossref, Google Scholar
• Holland J. H.Adaptation in Natural and Artificial Systems (1975) (University of Michigan Press, Ann Arbor) . [Reprint, MIT Press, Cambridge, MA 1992.]Google Scholar
• Homberger J., Gehring H. Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR (1999) 37(August):297–318Google Scholar
• Homberger J., Gehring H. A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. (2005) 162(1):220–238Crossref, Google Scholar
• Housroum H., Hsu T., Dupas R., Goncalves G. A hybrid GA approach for solving the dynamic vehicle routing problem with time windows. IEEE Internat. Conf. Inform. Comm. Technologies (2006) 1Damascus, Syria(IEEE Press, Piscataway, NJ) 787–792Crossref, Google Scholar
• Hwang H.-S. An improved model for vehicle routing problem with time constraint based on a genetic algorithm. Comput. Indust. Engrg. (2002) 42(2–4):361–369Crossref, Google Scholar
• Ibaraki T., Imahori S., Kubo M., Masuda T., Uno T., Yagiura M. Effective local search algorithms for routing and scheduling problems with general time window constraints. Transportation Sci. (2005) 39(2):206–232Link, Google Scholar
• Jaszkiewicz A., Kominek P. Genetic local search with distance preserving recombination operator for a vehicle routing problem. Eur. J. Oper. Res. (2003) 151(2):352–364Crossref, Google Scholar
• Jih W.-R., Yung-Jen Hsu J. Dynamic vehicle routing using hybrid genetic algorithms. IEEE Internat. Conf. Robotics and Automation (1999) 1Detroit(IEEE Press, Piscataway, NJ) 453–458Google Scholar
• Jones D. R., Beltramo M. A., Belew R. K., Booker L. B. Solving partitioning problems with genetic algorithms. Proc. Fourth Internat. Conf. Genetic Algorithms (1991) (Morgan Kaufmann, San Mateo, CA) 442–449Google Scholar
• Jorgensen R. M., Larsen J., Bergvinsdottir K. B. Solving the dial-a-ride problem using genetic algorithms. J. Oper. Res. Soc. (2007) 58(10):1321–1331Crossref, Google Scholar
• Jozefowiez N., Semet F., Talbi E. G., Guervós J. J. M., Adamidis P., Beyer H.-G., Fernández-Villacañas J.-L., Schwefel H.-P. Parallel and hybrid models for multi-objective optimization: Application to the vehicle routing problem. Parallel Problem Solving from Nature–PPSN VII (2002) 2439(Springer-Verlag, Berlin) 271–280Lecture Notes in Computer ScienceCrossref, Google Scholar
• Jozefowiez N., Semet F., Talbi E. G., Talbi E.-G., Liardet P., Collet P., Lutton E., Schoenauer M. Enhancements of NSGA-II and its application to the vehicle routing problem with route balancing. Artificial Evolution (2006) 3871(Springer-Verlag, Berlin) 131–142Lecture Notes in Computer ScienceCrossref, Google Scholar
• Jung S., Haghani A. Genetic algorithm for a pickup and delivery problem with time windows. Transportation Res. Record (2000) 1733:1–7Crossref, Google Scholar
• Jung S., Haghani A. Genetic algorithm for the time-dependent vehicle routing problem. Transportation Res. Record (2001) 1771:164–171Crossref, Google Scholar
• Jung S., Moon B.-R., Whitley D., Goldberg D. E., Cantú-Paz E., Spector L., Parmee I. C., Beyer H.-G. The natural crossover for the 2D Euclidean TSP. Proc. Genetic and Evolutionary Comput. Conf. (2000) (Morgan Kaufmann, San Francisco) 1003–1010Google Scholar
• Jung S., Moon B.-R., Langdon W. B., Cantú-Paz E., Mathias K. E., Roy R., Davis D., Poli R., Balakrishnan K., et al. A hybrid genetic algorithm for the vehicle routing problem with time windows. Proc. Genetic and Evolutionary Comput. Conf. (2002) (Morgan Kaufmann, San Francisco) 1309–1316Google Scholar
• Kennedy J., Eberhart R. C.Swarm Intelligence (2001) (Morgan Kaufmann, San Francisco) Google Scholar
• Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing. Science (1983) 220(4598):671–680Crossref, Google Scholar
• Koza J. R.Genetic Programming: On the Programming of Computers by Means of Natural Selection (1992) (MIT Press, Cambridge, MA) Google Scholar
• Krajcar S., Skrlec D., Pribicevic B., Blagajac S., Pinto-Ferreira C. A., Mamede N. J. GA approach to solving multiple vehicle routing problem. Progress in Artificial Intelligence (1995) 990(Springer-Verlag, Berlin) 473–481Lecture Notes in Computer ScienceCrossref, Google Scholar
• Kubiak M. Systematic construction of recombination operators for the vehicle routing problem. Foundations Comput. Decision Sci. (2004) 29(3):205–226Google Scholar
• Kubiak M., Wesolek P., Cotta C., van Hemert J. Accelerating local search in a memetic algorithm for the capacitated vehicle routing problem. Evolutionary Computation in Combinatorial Optimization (2007) 4446(Springer-Verlag, Berlin) 96–107Lecture Notes in Computer ScienceCrossref, Google Scholar
• Laporte G., Gendreau M., Potvin J.-Y., Semet F. Classical and modern heuristics for the vehicle routing problem. Internat. Trans. Oper. Res. (2000) 7(4–5):285–300Crossref, Google Scholar
• Lau H. C., Liang Z. Pickup and delivery with time windows: Algorithms and test cases. IEEE Internat. Conf. Tools with Artificial Intelligence (2001) Dallas(IEEE Computer Society, Los Alamitos, CA) 333–340Crossref, Google Scholar
• Le Bouthillier A. Recherches coopératives pour la résolution de problèmes d'optimisation combinatoire. (2007) . Ph.D. thesis, Département d'informatique et de recherche opérationnelle, Université de Montréal, MontréalGoogle Scholar
• Le Bouthillier A., Crainic T. G. A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. Comput. Oper. Res. (2005) 32(7):1685–1708Crossref, Google Scholar
• Le Bouthillier A., Crainic T. G., Kropf P. A guided cooperative search for the vehicle routing problem with time windows. IEEE Intelligent Systems (2005) 20(4):36–42Crossref, Google Scholar
• Leclerc F., Potvin J.-Y. Genetic algorithms for vehicle dispatching. Internat. Trans. Oper. Res. (1997) 4(5–6):391–400Crossref, Google Scholar
• Li H., Lim A. A metaheuristic for solving the pickup and delivery problem with time windows. IEEE Internat. Conf. Tools with Artificial Intelligence (2001) Dallas(IEEE Computer Society, Los Alamitos, CA) 160–167Google Scholar
• Li F., Golden B. L., Wasil E. A. Very large-scale vehicle routing: New test problems, algorithms and results. Comput. Oper. Res. (2005) 32(5):1165–1179Crossref, Google Scholar
• Lin S. Computer solutions of the traveling salesman problem. Bell Systems Tech. J. (1965) 44:2245–2269Crossref, Google Scholar
• Louis S. J., Yin X., Yuan Z. Y. Multiple vehicle routing with time windows using genetic algorithms. IEEE Congress on Evolutionary Comput. (1999) Washington, DC(IEEE Press, Piscataway, NJ) 1804–1808Crossref, Google Scholar
• Machado P., Tavares J., Pereira F. B., Costa E., Langdon W. B., Cantú-Paz E., Mathias K. E., Roy R., Davis D., Poli R., Balakrishnan K., et al. Vehicle routing problem: Doing it the evolutionary way. Proc. Genetic and Evolutionary Comput. Conf. (2002) (Morgan Kaufmann, San Francisco) 690Google Scholar
• Maeda O., Nakamura M., Ombuki B., Onaga K. A genetic algorithm approach to vehicle routing problem with time deadlines in geographical information systems. IEEE Internat. Conf. Systems (1999) Man Cybernetics, Tokyo(IEEE Press, Piscataway, NJ) 595–600Crossref, Google Scholar
• Mester D., Bräysy O. Active guided evolution strategies for large-scale vehicle routing problems with time windows. Comput. Oper. Res. (2005) 32(6):1593–1614Crossref, Google Scholar
• Mester D., Bräysy O. Active guided evolution strategies for large-scale capacitated vehicle routing problems. Comput. Oper. Res. (2007) 34(10):2964–2975Crossref, Google Scholar
• Mester D., Bräysy O., Dullaert W. A multi-parametric evolution strategies algorithm for vehicle routing problems. Expert Systems Appl. (2007) 32(2):508–517Crossref, Google Scholar
• Michalewicz Z.Genetic Algorithms + Data Structures = Evolution Programs (1996) 3rd ed.(Springer-Verlag, Berlin) Crossref, Google Scholar
• Mladenović N., Hansen P. Variable neighborhood search. Comput. Oper. Res. (1997) 24(11):1097–1100Crossref, Google Scholar
• Moin N. H. Hybrid genetic algorithms for vehicle routing problems with time windows. Internat. J. Comput., Internet Management (2002) 10(1):51–67Google Scholar
• Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. (1989) . Technical Report Caltech Concurrent Computation Program 826, California Institute of Technology, PasadenaGoogle Scholar
• Moscato P., Cotta C., Glover F., Kochenberger G. A. A gentle introduction to memetic algorithms. Handbook of Metaheuristics (2003) (Kluwer, Boston) 105–144Crossref, Google Scholar
• Mühlenbein H., Gorges-Schleuter M., Krämer O. Evolution algorithms in combinatorial optimization. Parallel Comput. (1988) 7(1):65–85Crossref, Google Scholar
• Nagata Y., Cotta C., van Hemert J. Edge assembly crossover for the capacitated vehicle routing problem. Evolutionary Computation in Combinatorial Optimization (2007a) 4446(Springer-Verlag, Berlin) 142–153Lecture Notes in Computer ScienceCrossref, Google Scholar
• Nagata Y. Effective memetic algorithm for the vehicle routing problem with time windows: Edge assembly crossover for the VRPTW. Metaheuristics Internat. Conf. (2007b) MontréalGoogle Scholar
• Nagata Y., Kobayashi S., Bäck T. Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem. Proc. Seventh Internat. Conf. Genetic Algorithms (1997) (Morgan Kaufmann, San Francisco) 450–457Google Scholar
• Nanry W. P., Barnes J. W. Solving the pickup and delivery problem with time windows using reactive tabu search. Transportation Res. B (2000) 34(2):107–121Crossref, Google Scholar
• Ochi L. S., Vianna D. S., Drummond L. M. A., Victor A. O. A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet. Future Generation Comput. Systems (1998a) 14(5–6):285–292Crossref, Google Scholar
• Ochi L. S., Vianna D. S., Drummond L. M. A., Victor A. O., Banzhaf W., Poli R., Schoenauer M., Fogarty T. C. An evolutionary hybrid metaheuristic for solving the vehicle routing problem with heterogeneous fleet. Genetic Programming: First Eur. Workshop (1998b) 1391(Springer-Verlag, Berlin) 187–195Lecture Notes in Computer ScienceCrossref, Google Scholar
• Oliver I. M., Smith D. J., Holland J. R. C., Grefenstette J. J. A study of permutation crossover operators on the traveling salesman problem. Proc. Second Internat. Conf. Genetic Algorithms Their Appl. (1987) (Lawrence Erlbaum Associates, Hillsdale, NJ) 224–230Google Scholar
• Ombuki B., Nakamura M., Maeda O. A hybrid search based on genetic algorithms and tabu search for vehicle routing. IASTED Internat. Conf. Artificial Intelligence Soft Comput. (2002) Banff, Canada(ACTA Press, Calgary, ON, Canada) 176–181Google Scholar
• Ombuki B., Ross B. J., Hanshar F. Multi-objective genetic algorithms for vehicle routing problem with time windows. Appl. Intelligence (2006) 24(1):17–30Crossref, Google Scholar
• Or I. Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. (1976) . Ph.D. thesis, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, ILGoogle Scholar
• Osman I. H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann. Oper. Res. (1993) 41(1–4):421–451Crossref, Google Scholar
• Ozdemir H. T., Mohan C. K. Evolving schedule graphs for the vehicle routing problem with time windows. IEEE Congress on Evolutionary Comput. (2000) 2La Jolla, CA(IEEE Press, Piscataway, NJ) 888–895Crossref, Google Scholar
• Pankratz G. A grouping genetic algorithm for the pickup and delivery problem with time windows. OR Spectrum (2005a) 27(1):21–41Crossref, Google Scholar
• Pankratz G. Dynamic vehicle routing by means of a genetic algorithm. Internat. J. Physical Distribution Logist. (2005b) 35(5):362–383Crossref, Google Scholar
• Pedroso J. P. Niche search: An application in vehicle routing. IEEE Internat. Conf. Evolutionary Comput. (1998) Anchorage, AK(IEEE Press, Piscataway, NJ) 177–182Crossref, Google Scholar
• Pereira F. B., Tavares J., Machado P., Costa E., O'Neill M., Sutcliffe R. F. E., Ryan C., Eaton M. GVR: A new genetic representation for the vehicle routing problem. Artificial Intelligence and Cognitive Science (2002) 2464(Springer-Verlag, Berlin) 95–102Lecture Notes in Computer ScienceCrossref, Google Scholar
• Pisinger D., Ropke S. A general heuristic for vehicle routing problems. Comput. Oper. Res. (2007) 34(8):2403–2435Crossref, Google Scholar
• Potter T., Bossomaier T. Solving vehicle routing problems with genetic algorithms. IEEE Internat. Conf. Evolutionary Comput. (1995) 2Perth, Australia(IEEE Press, Piscataway, NJ) 788–793Crossref, Google Scholar
• Potvin J.-Y. Genetic algorithms for the traveling salesman problem. Ann. Oper. Res. (1996) 63(3):339–370Crossref, Google Scholar
• Potvin J.-Y., Bengio S. The vehicle routing problem with time windows, Part II: Genetic search. INFORMS J. Comput. (1996) 8(2):165–172Link, Google Scholar
• Potvin J.-Y., Dubé D. Improving a vehicle routing heuristic through genetic search. IEEE Internat. Conf. Evolutionary Comput. (1994) Orlando, FL(IEEE Press, Piscataway, NJ) 194–199Crossref, Google Scholar
• Potvin J.-Y., Guertin F., Barr R. S., Helgason R. V., Kennington J. L. Coupling a greedy route construction heuristic with a genetic algorithm for the vehicle routing problem with time windows. Advances in Metaheuristics, Optimization and Stochastic Modeling Technologies (1997) (Kluwer, Boston) 423–442Crossref, Google Scholar
• Potvin J.-Y., Rousseau J.-M. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. Eur. J. Oper. Res. (1993) 66(3):331–340Crossref, Google Scholar
• Potvin J.-Y., Rousseau J.-M. An exchange heuristic for routing problems with time windows. J. Oper. Res. Soc. (1995) 46(12):1433–1446Crossref, Google Scholar
• Potvin J.-Y., Thangiah S. R., Jain L. C., Martin N. M. Vehicle routing through simulation of natural processes. Fusion of Neural Networks, Fuzzy Sets and Genetic Algorithms: Industrial Applications (1999) (CRC Press, Boca Raton, FL) 141–168Google Scholar
• Potvin J.-Y., Dubé D., Robillard C. A hybrid approach to vehicle routing using neural networks and genetic algorithms. Appl. Intelligence (1996a) 6(3):241–252Crossref, Google Scholar
• Potvin J.-Y., Duhamel C., Guertin F. A genetic algorithm for vehicle routing with backhauling. Appl. Intelligence (1996b) 6(4):345–355Crossref, Google Scholar
• Prescott-Gagnon E., Desaulniers G., Rousseau L.-M. A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows. (2007) . Technical Report G-2007-67, Groupe d'Études et de Recherche en Analyse des Décisions, MontréalGoogle Scholar
• Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. (2004) 31(12):1985–2002Crossref, Google Scholar
• Prins C., Prodhon C., Calvo R. W., Gottlieb J., Raidl G. R. A memetic algorithm with population management (MA/PM) for the capacitated location-routing problem. Evolutionary Computation in Combinatorial Optimization (2006) 3906(Springer-Verlag, Berlin) 183–194Lecture Notes in Computer ScienceCrossref, Google Scholar
• Rahoual M., Kitoun B., Mabed M.-H., Bachelet V., Benameur F. Multicriteria genetic algorithms for the vehicle routing problem with time windows. Metaheuristics Internat. Conf. (2001) Porto, Portugal:527–532Google Scholar
• Rochat Y., Taillard É. D. Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics (1995) 1(1):147–167Crossref, Google Scholar
• Ropke S., Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Sci. (2006) 40(4):455–472Link, Google Scholar
• Ropke S., Cordeau J.-F., Laporte G. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks (2007) 49(4):258–272Crossref, Google Scholar
• Russell R. A. Hybrid heuristics for the vehicle routing problem with time windows. Transportation Sci. (1995) 29(2):156–166Link, Google Scholar
• Russell M. A., Lamont G. B., Beyer H.-G., O'Reilly U.-M. A genetic algorithm for unmanned aerial vehicle routing. Proc. Genetic and Evolutionary Comput. Conf. (2005) (ACM Press, New York) 1523–1530Crossref, Google Scholar
• Salhi S., Thangiah S. R., Rahman F., Smith G. D., Steele N. C., Albrecht R. F. A genetic clustering method for the multi-depot vehicle routing problem. Artificial Neural Networks and Genetic Algorithms (1998) (Springer-Verlag, Vienna) 234–237Crossref, Google Scholar
• Santos H. G., Ochi L. S., Marinho E. H., Drummond L. M. A. Combining an evolutionary algorithm with data mining to solve a single-vehicle routing problem. Neurocomputing (2006) 70(1–3):70–77Crossref, Google Scholar
• Schmitt L. J. An empirical computational study of genetic algorithms to solve order-based problems: An emphasis on the TSP and VRPTC. (1994) . Doctoral dissertation, Fogelman College of Business and Economics, University of Memphis, Memphis, TNGoogle Scholar
• Schönberger J., Kopfer H., Leopold-Wildburger U., Rendl F., Wäscher G. A combined approach to solve the pickup and delivery selection problem. Oper. Res. Proc. 2002 (2003a) (Springer-Verlag, Berlin) 150–155Crossref, Google Scholar
• Schönberger J., Kopfer H., Mohammadian M. A memetic algorithm for a pickup and delivery selection problem. Proc. Internat. Conf. Computational Intelligence for Modeling, Control and Automation (CIMCA 2003) (2003b) Vienna(University of Canberra, Canberra, Australia) Google Scholar
• Schönberger J., Kopfer H., Fleischmann B., Klose A. Planning the incorporation of logistics service providers to fulfill precedence and time window-constrained transport requests in a most profitable way. Distribution Logistics: Advanced Solutions to Practical Problems (2004) (Springer-Verlag, Berlin) 141–158Google Scholar
• Schrimpf G., Schneider J., Stamm-Wilmbrandt H., Duek G. Record breaking optimization results using the ruin and recreate principle. J. Computational Phys. (2000) 159(2):139–171Crossref, Google Scholar
• Shaw P., Maher M., Puget J.-F. Using constraint programming and local search methods to solve vehicle routing problems. Principles and Practice of Constraint Programming–CP98 (1998) 1520(Springer-Verlag, New York) 417–431Lecture Notes in Computer ScienceCrossref, Google Scholar
• Skok M., Skrlec D., Krajcar S. The genetic algorithm method for multiple depot capacitated vehicle routing problem solving. Internat. Conf. Knowledge-Based Intelligent Engrg. Systems Allied Technologies (2000a) Brighton, UK(IEEE Press, Piscataway, NJ) 520–526Crossref, Google Scholar
• Skok M., Skrlec D., Krajcar S. The non-fixed destination multiple depot capacitated vehicle routing problem and genetic algorithms. Internat. Conf. Inform. Tech. Interfaces (2000b) Zagreb, Croatia:403–408Google Scholar
• Skrlec D., Filipec M., Krajcar S. A heuristic modification of genetic algorithm used for solving the single depot capacitated vehicle routing problem. Intelligent Inform. Systems (1997) Grand Bahama Island, Bahamas(IEEE Computer Society, Los Alamitos, CA) 184–188Google Scholar
• Solomon M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. (1987) 35(2):254–265Link, Google Scholar
• Srinivas N., Deb K. Multi-objective function optimization using non-dominated sorting genetic algorithms. Evolutionary Comput. J. (1994) 2(3):221–248Crossref, Google Scholar
• Syswerda G., Schaffer J. D. Uniform crossover in genetic algorithms. Proc. Third Internat. Conf. Genetic Algorithms (1989) (Morgan Kaufmann, San Mateo, CA) 2–9Google Scholar
• Taillard É. D. Parallel iterative search methods for vehicle routing problems. Networks (1993) 23(8):661–673Crossref, Google Scholar
• 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 Sci. (1997) 31(2):170–186Link, Google Scholar
• Tan K. C., Chew Y. H., Lee L. H. A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems. Eur. J. Oper. Res. (2006a) 172(3):855–885Crossref, Google Scholar
• Tan K. C., Chew Y. H., Lee L. H. A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Computational Optim. Appl. (2006b) 34(1):115–151Crossref, Google Scholar
• Tan K. C., Lee L. H., Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engrg. Appl. Artificial Intelligence (2001a) 14(6):825–837Crossref, Google Scholar
• Tan K. C., Lee L. H., Ou K. Hybrid genetic algorithms in solving vehicle routing problems with time window constraints. Asia-Pacific J. Oper. Res. (2001b) 18:121–130Google Scholar
• Tan K. C., Lee T. H., Chew Y. H., Lee L. H. A hybrid multiobjective evolutionary algorithm for solving truck and trailer vehicle routing problems. IEEE Congress on Evolutionary Computation (2003a) 3Canberra, Australia(IEEE Press, Piscataway, NJ) 2134–2141Crossref, Google Scholar
• Tan K. C., Lee T. H., Chew Y. H., Lee L. H. A multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. IEEE Internat. Conf. Systems (2003b) 1Man Cybernetics, Washington, DC(IEEE Press, Piscataway, NJ) 361–366Crossref, Google Scholar
• Tan K. C., Lee T. H., Ou K., Lee L. H. A messy genetic algorithm for the vehicle routing problem with time window constraints. IEEE Congress on Evolutionary Computation (2001c) 1Seoul, South Korea(IEEE Press, Piscataway, NJ) 679–686Crossref, Google Scholar
• Tan K. C., Lee L. H., Zhu K. Q., Ou K. Heuristic methods for vehicle routing problem with time windows. Artificial Intelligence Engrg. (2001d) 15(3):281–295Crossref, Google Scholar
• Tarantilis C. D. Solving the vehicle routing problem with adaptive memory programming methodology. Comput. Oper. Res. (2005) 32(9):2309–2327Crossref, Google Scholar
• Tavakkoli-Moghaddam R., Saremi A. R., Ziaee M. S. A memetic algorithm for a vehicle routing problem with backhauls. Appl. Math. Comput. (2006) 181(2):1049–1060Crossref, Google Scholar
• Tavares J., Pereira F. B., Machado P., Costa E. GVR delivers it on time. Asia-Pacific Conf. Simulated Evolution Learn. (2002) Singapore:745–749Google Scholar
• Tavares J., Pereira F. B., Machado P., Costa E. Crossover and diversity: A study about GVR. Analysis and Design of Representations and Operators: A Bird-of-a-Feather Workshop at the 2003 Genetic and Evolutionary Comput. Conf. (2003a) Chicago:27–33Google Scholar
• Tavares J., Pereira F. B., Machado P., Costa E. On the influence of GVR in vehicle routing. ACM Sympos. Appl. Comput. (2003b) Melbourne, FL:753–758Crossref, Google Scholar
• Thangiah S. R., Eshelman L. J. An adaptive clustering method using a geometric shape for vehicle routing problems with time windows. Proc. Sixth Internat. Conf. Genetic Algorithms (1995a) (Morgan Kaufmann, San Francisco) 536–543Google Scholar
• Thangiah S. R., Chambers L. Vehicle routing with time windows using genetic algorithms. Practical Handbook of Genetic Algorithms: New Frontiers (1995b) II(CRC Press, Boca Raton, FL) 253–277Crossref, Google Scholar
• Thangiah S. R., Chambers L. A hybrid genetic algorithm, simulated annealing and tabu search heuristic for vehicle routing problems with time windows. Practical Handbook of Genetic Algorithms: Complex Coding Systems (1999) III(CRC Press, Boca Raton, FL) 347–384Google Scholar
• Thangiah S. R., Gubbi A. V. Effect of genetic sectoring on vehicle routing problems with time windows. IEEE Internat. Conf. Developing and Managing Intelligent System Projects (1993) Washington, DC(IEEE Computer Society Press, Los Alamitos, CA) 146–153Crossref, Google Scholar
• Thangiah S. R., Nygard K. E., Biswas G. School bus routing using genetic algorithms. Applications of Artificial Intelligence X: Knowledge-Based Systems (1992) (SPIE, Bellingham, WA) 387–398Crossref, Google Scholar
• Thangiah S. R., Petrovic P., Woodruff D. L. Introduction to genetic heuristics and vehicle routing problems with complex constraints. Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search (1998) (Kluwer, Boston) 253–286Crossref, Google Scholar
• Thangiah S. R., Salhi S. Genetic clustering: An adaptive heuristic for the multidepot vehicle routing problem. Appl. Artificial Intelligence (2001) 15(4):361–383Crossref, Google Scholar
• Thangiah S. R., Nygard K. E., Juell P. L. GIDEON: A genetic algorithm system for vehicle routing with time windows. IEEE Conf. Artificial Intelligence Appl. (1991) Miami, FL(IEEE Computer Society Press, Los Alamitos, CA) 322–328Crossref, Google Scholar
• Thangiah S. R., Vinayagamoorthy R., Gubbi A. V., Forrest S. Vehicle routing with time deadlines using genetic and local algorithms. Proc. Fifth Internat. Conf. Genetic Algorithms (1993) (Morgan Kaufmann, San Mateo, CA) 506–513Google Scholar
• Thangiah S. R., Osman I. H., Vinayagamoorthy R., Sun T. Algorithms for the vehicle routing problems with time deadlines. Amer. J. Math. Management Sci. (1995) 13(3–4):323–355Google Scholar
• Tong Z., Ning L., Debao S. Genetic algorithm for vehicle routing problem with time window with uncertain vehicle number. World Congress on Intelligent Control and Automation (2004) Hangzhou, China:2846–2849Google Scholar
• Toth P., Vigo D. The granular tabu search and its application to the vehicle-routing problem. INFORMS J. Comput. (2003) 15(4):333–346Link, Google Scholar
• Van Breedam A. An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related and time-related constraints. (1994) . Doctoral dissertation, Faculty of Applied Economics, University of Antwerp, Antwerp, BelgiumGoogle Scholar
• Van Breedam A. An analysis of the effect of local improvement operators in genetic algorithm and simulated annealing for the vehicle routing problem. (1996) . RUCA Working Paper 96/14, University of Antwerp, Antwerp, BelgiumGoogle Scholar
• Vianna D. S., Ochi L. S., Drummond L. M. A., Rolim J. P. D., et al. A parallel evolutionary metaheuristic for the period vehicle routing problem. Parallel and Distributed Processing (1999) 1586(Springer-Verlag, Berlin) 183–191Lecture Notes in Computer ScienceCrossref, Google Scholar
• Voudouris C., Tsang E. P. K. Guided local search. (1995) . Technical Report CSM-247, Department of Computer Science, University of Essex, Colchester, UKGoogle Scholar
• Voudouris C., Tsang E. P. K., Glover F., Kochenberger G. A. Guided local search. Handbook of Metaheuristics (2003) (Kluwer, Boston) 185–218Crossref, Google Scholar
• Whitley D., Schaffer J. D. The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. Proc. Third Internat. Conf. Genetic Algorithms (1989) (Morgan Kaufmann, San Mateo, CA) 116–121Google Scholar
• Yagiura M., Ibaraki T. On metaheuristic algorithms for combinatorial optimization problems. Systems Comput. Japan (2001) 32(3):33–55Crossref, Google Scholar
• Zhu K. Q., Arabnia H. R. A new genetic algorithm for VRPTW. Proc. Internat. Conf. Artificial Intelligence (2000) (CSREA Press, Las Vegas, NV) 1–10Google Scholar
• Zhu K. Q. A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windows. Internat. Conf. Tools Artificial Intelligence (2003) Sacramento, CA(IEEE Computer Society, Los Alamitos, CA) 176–183Crossref, Google Scholar
• Zhu Q., Qian L., Li Y., Zhu S. An improved particle swarm optimization algorithm for vehicle routing problem with time windows. IEEE Congress on Evolutionary Comput. (2006) Vancouver(IEEE Press, Piscataway, NJ) 1386–1390Google Scholar