nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

An Island Memetic Algorithm for Real World Vehicle Routing Problems

verfasst von : Ioannis Rogdakis, Magdalene Marinaki, Yannis Marinakis, Athanasios Migdalas

Erschienen in: Operational Research in Business and Economics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, a new algorithm is presented which is applied to a real world Vehicle Routing Problem (VRP) of a provision company in the island of Crete in Greece. The company serves 116 customers located in Crete. This real world problem is solved effectively by a hybrid Island Memetic Algorithm (IMA) which employs Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Local Search (ILS). The proposed algorithm is also compared to five other approaches both on the real world problem and on classic benchmark instances from the literature. Methods such as GRASP, local search and Iterated Local Search (ILS) are employed as subroutines with certain probabilities in the algorithms. Furthermore, it is also demonstrated how premature convergence can be prevented by adopting specific strategy. Computational results show the superiority of the proposed hybrid Island Memetic Algorithm.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Approximating Throughput of Small Production Lines Using Genetic Programming

Nächstes Kapitel Three-Dimensional Multiple-Bin-Size Bin Packing: A Case Study with a New MILP-Based Upper Bound

Altinkemer K, Gavish B (1991) Parallel savings based heuristics for the delivery problem. Oper Res 39(3):456–469CrossRef

Baker BM, Ayechew MA (2003) A genetic algorithm for the vehicle routing problem. Comput Oper Res 30(5):787–800CrossRef

Barbarosoglu G, Ozgur D (1999) A tabu search algorithm for the vehicle routing problem. Comput Oper Res 26:255–270CrossRef

Berger J, Barkaoui M (2003) A hybrid genetic algorithm for the capacitated vehicle routing problem. Proceedings of the genetic and evolutionary computation conference, Chicago, IL, pp 646–656

Besten M, Stutzle T, Dorigo M (2001) A hybrid genetic algorithm for the capacitated vehicle routing problem. In: Boers EJW et al (eds) Design of iterated local search algorithms, EvoWorkshop LNCS 2037. Springer, Berlin, pp 441–451

Bodin L, Golden B (1981) Classification in vehicle routing and scheduling. Networks 11:97–108CrossRef

Bodin L, Golden B, Assad A, Ball M (1983) The state of the art in the routing and scheduling of vehicles and crews. Comput Oper Res 10:63–212CrossRef

Bullnheimer B, Hartl PF, Strauss C (1999) An improved ant system algorithm for the vehicle routing problem. Ann Oper Res 89:319–328CrossRef

Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P, Sandi C (eds) Combinatorial optimization. Wiley, Chichester

Clarke G, Wright J (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:568–581CrossRef

Cordeau JF, Gendreau M, Laporte G, Potvin JY, Semet F (2002) A guide to vehicle routing heuristics. J Oper Res Soc 53:512–522CrossRef

Cordeau JF, Gendreau M, Hertz A, Laporte G, Sormany JS (2005) New heuristics for the vehicle routing problem. In: Langevine A, Riopel D (eds) Logistics systems: design and optimization. Wiley, Chichester, pp 279–298CrossRef

Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manage Sci 6(1):80–91CrossRef

Desrochers M, Verhoog TW (1989) A matching based savings algorithm for the vehicle routing problem. Les Cahiers du GERAD G-89-04, Ecole des Hautes Etudes Commerciales de Montreal

Engelbrecht AP (2007) Computational intelligence: an introduction. Wiley, ChichesterCrossRef

Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedure. J Glob Optim 6:109–133CrossRef

Fisher ML (1995) Vehicle routing. In: Ball MO, Magnanti TL, Momma CL, Nemhauser GL (eds) Network routing, vol 8, Handbooks in operations research and management science. Elsevier, Amsterdam, pp 1–33CrossRef

Fisher ML, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Networks 11:109–124CrossRef

Foster BA, Ryan DM (1976) An integer programming approach to the vehicle scheduling problem. Oper Res 27:367–384CrossRef

Gendreau M, Hertz A, Laporte G (1994) A tabu search heuristic for the vehicle routing problem. Manage Sci 40:1276–1290CrossRef

Gendreau M, Laporte G, Potvin J-Y (1997) Vehicle routing: modern heuristics. In: Aarts EHL, Lenstra JK (eds) Local search in combinatorial optimization. Wiley, Chichester, pp 311–336

Gendreau M, Laporte G, Potvin JY (2002) Metaheuristics for the capacitated VRP. In: Toth P, Vigo D (eds) The vehicle routing problem, Monographs on discrete mathematics and applications. Siam, Philadelphia, PA, pp 129–154CrossRef

Gillett BE, Miller LR (1974) A heuristic algorithm for the vehicle dispatch problem. Oper Res 22:240–349CrossRef

Glover F, Laguna M, Marti R (2003) Scatter search and path relinking: advances and applications. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics. Kluwer, Boston, MA, pp 1–36

Golden BL, Assad AA (1988) Vehicle routing: methods and studies. Elsevier, Amsterdam

Golden BL, Wasil EA, Kelly JP, Chao IM (1998) The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results. In: Crainic TG, Laporte G (eds) Fleet management and logistics. Kluwer, Boston, MA, pp 33–56CrossRef

Golden B, Raghavan S, Wasil E (2008) The vehicle routing problem: latest advances and new challenges. Springer, New York, NYCrossRef

Laporte G, Semet F (2002) Classical heuristics for the capacitated VRP. In: Toth P, Vigo D (eds) The vehicle routing problem, Monographs on discrete mathematics and applications. Siam, Philadelphia, PA, pp 109–128CrossRef

Laporte G, Gendreau M, Potvin J-Y, Semet F (2000) Classical and modern heuristics for the vehicle routing problem. Int Trans Oper Res 7:285–300CrossRef

Li F, Golden B, Wasil E (2005) Very large-scale vehicle routing: new test problems, algorithms and results. Comput Oper Res 32(5):1165–1179CrossRef

Lin S (1965) Computer solutions of the traveling salesman problem. Bell Syst Tech J 44:2245–2269CrossRef

Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21:498–516CrossRef

Lourenco HR, Martin O, Stutzle T (2002) Iterated local search. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics, vol 57, Operations research and management science. Kluwer, Norwell, MA, pp 321–353

Marinakis Y, Marinaki M (2010) A hybrid genetic—particle swarm optimization algorithm for the vehicle routing problem. Expert Syst Appl 37:1446–1455CrossRef

Marinakis Y, Migdalas A (2002) Heuristic solutions of vehicle routing problems in supply chain management. In: Burkard R, Pardalos PM, Migdalas A (eds) Combinatorial and global optimization. World Scientific Publishing, Singapore, pp 205–236CrossRef

Marinakis Y, Migdalas A, Pardalos PM (2005a) Expanding neighborhood GRASP for the traveling salesman problem. Comput Optim Appl 32:231–257CrossRef

Marinakis Y, Migdalas A, Pardalos PM (2005b) A hybrid Genetic-GRASP algorithm using Langrangean relaxation for the traveling salesman problem. J Comb Optim 10:311–326CrossRef

Marinakis Y, Migdalas A, Pardalos PM (2007) A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm. J Glob Optim 38:555–580CrossRef

Marinakis Y, Marinaki M, Dounias G (2008) Honey bees mating optimization algorithm for the vehicle routing problem. In: Krasnogor N, Nicosia G, Pavone M, Pelta D (eds) Nature Inspired Cooperative Strategies for Optimization—NICSO 2007, vol 129, Studies in Computational Intelligence. Springer, Berlin, pp 139–148

Marinakis Y, Migdalas A, Pardalos PM (2009) Multiple phase neighborhood search GRASP based on Lagrangean relaxation and random backtracking Lin Kernighan for the traveling salesman problem. J Comb Optim 17:134–156CrossRef

Marinakis Y, Marinaki M, Dounias G (2010) A hybrid particle swarm optimization algorithm for the vehicle routing problem. Eng Appl Artif Intel 23:463–472CrossRef

Marinakis Y, Iordanidou G, Marinaki M (2013) Particle swarm optimization for the vehicle routing problem with stochastic demands. Appl Soft Comput 13(4):1693–1704CrossRef

Martin O, Otto SW, Felten EW (1991) Large-step Markov chains for the traveling salesman problem. Complex Syst 5(3):299–326

Mester D, Braysy O (2005) Active guided evolution strategies for the large scale vehicle routing problems with time windows. Comput Oper Res 32:1593–1614CrossRef

Mester D, Braysy O (2007) Active guided evolution strategies for large scale capacitated vehicle routing problems. Comput Oper Res 34:2964–2975CrossRef

Mole RH, Jameson SR (1976) A sequential route-building algorithm employing a generalized savings criterion. Oper Res Q 27:503–511CrossRef

Moscato P, Cotta C (2003) A gentle introduction to memetic algorithms. In: Glover F, Kochenberger GA (eds) Handbooks of metaheuristics. Kluwer, Dordrecht, pp 105–144

Osman IH (1993) Metastrategy simulated annealing and tabu search algorithms for combinatorial optimization problems. Ann Oper Res 41:421–451CrossRef

Pereira FB, Tavares J (2008) Bio-inspired algorithms for the vehicle routing problem, vol 161, Studies in computational intelligence. Springer, Berlin

Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31:1985–2002CrossRef

Prins C (2008) A GRASP X evolutionary local search hybrid for the vehicle routing problem. In: Pereira FB, Tavares J (eds) Bio-inspired algorithms for the vehicle routing problem, SCI 161. Springer, Berlin, pp 35–53

Rego C (1998) A subpath ejection method for the vehicle routing problem. Manage Sci 44:1447–1459CrossRef

Rego C (2001) Node-ejection chains for the vehicle routing problem: sequential and parallel algorithms. Parallel Comput 27(3):201–222CrossRef

Reimann M, Stummer M, Doerner K (2002) A savings based ant system for the vehicle routing problem. Proceedings of the genetic and evolutionary computation conference, New York, pp 1317–1326

Reimann M, Doerner K, Hartl RF (2004) D-Ants: savings based ants divide and conquer the vehicle routing problem. Comput Oper Res 31(4):563–591CrossRef

Resende MGC, Ribeiro CC (2003) Greedy randomized adaptive search procedures. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics. Kluwer, Boston, MA, pp 219–249

Rochat Y, Taillard ED (1995) Probabilistic diversification and intensification in local search for vehicle routing. J Heuristics 1:147–167CrossRef

Taillard ED (1993) Parallel iterative search methods for vehicle routing problems. Networks 23:661–672CrossRef

Talbi E-G (2009) Metaheuristics: from design to implementation. Wiley, Hoboken, NJCrossRef

Tarantilis CD (2005) Solving the vehicle routing problem with adaptive memory programming methodology. Comput Oper Res 32(9):2309–2327CrossRef

Tarantilis CD, Kiranoudis CT (2002) BoneRoute: an adaptive memory-based method for effective fleet management. Ann Oper Res 115(1):227–241CrossRef

Tarantilis CD, Kiranoudis CT, Vassiliadis VS (2002a) A backtracking adaptive threshold accepting metaheuristic method for the Vehicle Routing Problem. Syst Anal Model Simul 42(5):631–644

Tarantilis CD, Kiranoudis CT, Vassiliadis VS (2002b) A list based threshold accepting algorithm for the capacitated vehicle routing problem. Int J Comp Math 79(5):537–553CrossRef

Toth P, Vigo D (2002) The vehicle routing problem, Monographs on discrete mathematics and applications. Siam, Philadelphia, PACrossRef

Toth P, Vigo D (2003) The granular tabu search (and its application to the vehicle routing problem). INFORMS J Comput 15(4):333–348CrossRef

Toth P, Vigo D (2014) Vehicle routing: problems, methods and applications, 2nd edn, MOS-Siam series on optimization. Siam, Philadelphia, PACrossRef

Wark P, Holt J (1994) A repeated matching heuristic for the vehicle routing problem. J Oper Res Soc 45:1156–1167CrossRef

Xu J, Kelly JP (1996) A new network flow-based tabu search heuristic for the vehicle routing problem. Transp Sci 30:379–393CrossRef

Titel: An Island Memetic Algorithm for Real World Vehicle Routing Problems
verfasst von: Ioannis Rogdakis
Magdalene Marinaki
Yannis Marinakis
Athanasios Migdalas
Verlag: Springer International Publishing
Buch: Operational Research in Business and Economics
Print ISBN: 978-3-319-33001-3

Electronic ISBN: 978-3-319-33003-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-33003-7_10