nach oben

Soft Computing

Erschienen in:

18.05.2019 | Methodologies and Application

A multi-start ILS–RVND algorithm with adaptive solution acceptance for the CVRP

verfasst von: Osman Gokalp, Aybars Ugur

Erschienen in: Soft Computing | Ausgabe 4/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This study proposes a novel hybrid algorithm based on Iterated Local Search (ILS) and Random Variable Neighborhood Descent (RVND) metaheuristics for the purpose of solving the Capacitated Vehicle Routing Problem (CVRP). The main contribution of this work is that two new search rules have been developed for multi-starting and adaptive acceptance strategies, and applied together to enhance the power of the algorithm. A comprehensive experimental work has been conducted on two common CVRP benchmarks. Computational results demonstrate that both multi-start and adaptive acceptance strategies provide a significant improvement on the performance of pure ILS–RVND hybrid. Experimental work also shows that our algorithm is highly effective in solving CVRP and comparable with the state of the art.

Vorheriger Artikel Analysis of semi-asynchronous multi-objective evolutionary algorithm with different asynchronies

Nächster Artikel Dense adaptive cascade forest: a self-adaptive deep ensemble for classification problems

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

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Agrawal V, Lightner C, Lightner-Laws C, Wagner N (2017) A bi-criteria evolutionary algorithm for a constrained multi-depot vehicle routing problem. Soft Comput 21(17):5159–5178CrossRef

Alabas-Uslu C, Dengiz B (2011) A self-adaptive local search algorithm for the classical vehicle routing problem. Expert Syst Appl 38(7):8990–8998CrossRef

Avci M, Topaloglu S (2015) An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Comput Ind Eng 83:15–29CrossRef

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, pp 315–338MATH

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

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

Dethloff J (2001) Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum 23(1):79–96MathSciNetCrossRef

Dueck G, Scheuer T (1990) Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. J Comput Phys 90(1):161–175MathSciNetCrossRef

Fu Z, Eglese R, Li LYO (2005) A new tabu search heuristic for the open vehicle routing problem. J Oper Res Soc 56(3):267–274CrossRef

Gee SB, Arokiasami WA, Jiang J, Tan KC (2016) Decomposition-based multi-objective evolutionary algorithm for vehicle routing problem with stochastic demands. Soft Comput 20(9):3443–3453CrossRef

Hansen P, Mladenović N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130(3):449–467MathSciNetCrossRef

Irnich S, Funke B, Grünert T (2006) Sequential search and its application to vehicle-routing problems. Comput Oper Res 33(8):2405–2429CrossRef

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680MathSciNetCrossRef

Lenstra JK, Kan AR (1981) Complexity of vehicle routing and scheduling problems. Networks 11(2):221–227CrossRef

López-Ibáñez M, Dubois-Lacoste J, Cáceres LP, Birattari M, Stützle T (2016) The irace package: iterated racing for automatic algorithm configuration. Oper Res Perspect 3:43–58MathSciNetCrossRef

Michallet J, Prins C, Amodeo L, Yalaoui F, Vitry G (2014) Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services. Comput Oper Res 41:196–207MathSciNetCrossRef

Molina J, López-Sánchez A, Hernández-Díaz AG, Martínez-Salazar I (2018) A multi-start algorithm with intelligent neighborhood selection for solving multi-objective humanitarian vehicle routing problems. J Heuristics 24(2):111–133CrossRef

Nalepa J, Blocho M (2016) Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows. Soft Comput 20(6):2309–2327CrossRef

Penna PHV, Subramanian A, Ochi LS (2013) An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. J Heuristics 19(2):201–232CrossRef

Psychas ID, Marinaki M, Marinakis Y, Migdalas A (2017) Parallel multi-start nondominated sorting particle swarm optimization algorithms for the minimization of the route-based fuel consumption of multiobjective vehicle routing problems. In: Butenko S, Pardalos PM, Shylo V (eds) Optimization methods and applications. Springer, Berlin, pp 425–456CrossRef

Rivera JC, Afsar HM, Prins C (2015) A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem. Comput Optim Appl 61(1):159–187MathSciNetCrossRef

Sassi O, Cherif-Khettaf WR, Oulamara A (2015) Multi-start iterated local search for the mixed fleet vehicle routing problem with heterogenous electric vehicles. In: European conference on evolutionary computation in combinatorial optimization. Springer, pp 138–149

Stützle T (1998) Local search algorithms for combinatorial problems. Dissertation, Darmstadt University of Technology

Subramanian A, Uchoa E, Ochi LS (2013) A hybrid algorithm for a class of vehicle routing problems. Comput Oper Res 40(10):2519–2531CrossRef

Taillard E, Badeau P, Gendreau M, Guertin F, Potvin JY (1997) A tabu search heuristic for the vehicle routing problem with soft time windows. Transp Sci 31(2):170–186CrossRef

Tarantilis C, Kiranoudis C, Vassiliadis V (2002) A backtracking adaptive threshold accepting algorithm for the vehicle routing problem. Syst Anal Model Simul 42(5):631–664MathSciNetCrossRef

Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur J Oper Res 257(3):845–858MathSciNetCrossRef

Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W (2012) A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper Res 60(3):611–624MathSciNetCrossRef

Titel: A multi-start ILS–RVND algorithm with adaptive solution acceptance for the CVRP
verfasst von: Osman Gokalp
Aybars Ugur
Publikationsdatum: 18.05.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 4/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-019-04072-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2020

Estimation of dynamic mixed double factors model in high-dimensional panel data

A comprehensive model for fuzzy multi-objective portfolio selection based on DEA cross-efficiency model

Multi-period multi-scenario optimal design for closed-loop supply chain network of hazardous products with consideration of facility expansion

Uncertain Johnson–Schumacher growth model with imprecise observations and k-fold cross-validation test

Teaching–learning-based optimisation algorithm and its application in capturing critical slip surface in slope stability analysis

Correction to: Optimal operational strategies of capital-constrained supply chain with logistics service and price dependent demand under 3PL financing service

Premium Partner