nach oben

OR Spectrum

Erschienen in:

25.11.2019 | Regular Article

A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes

verfasst von: Tânia Rodrigues Pereira Ramos, Maria Isabel Gomes, Ana Paula Barbosa-Póvoa

Erschienen in: OR Spectrum | Ausgabe 1/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The multi-depot vehicle routing problem with inter-depot routes is studied in this paper, where vehicles may reset their capacity at any depot during the working day. Due to the complexity of this problem, exact approaches are limited to small-size applications. In order to overcome this limitation, we propose a matheuristic which integrates a mixed integer linear programming formulation with a set of relax-and-fix strategies. This solution approach is shown to be very efficient, and for the first time, large-size benchmarking instances are solved.

Vorheriger Artikel Mathematical models to improve the current practice in a Home Healthcare Unit

Nächster Artikel A matheuristic for the swap body vehicle routing problem

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

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 "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

Nur mit Berechtigung zugänglich

Angelelli E, Speranza MG (2002) The periodic vehicle routing problem with intermediate facilities. Eur J Oper Res 137(2):233–247CrossRef

Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math Program 120(2):347–380CrossRef

Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper Res 52(5):723–738CrossRef

Bard JF, Huang L, Dror M, Jaillet P (1998) A branch and cut algorithm for the VRP with satellite facilities. IIE Trans 30(9):821–834

Benjamin AM, Beasley JE (2010) Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Comput Oper Res 37(12):2270–2280CrossRef

Brandao J, Mercer A (1997) A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. Eur J Oper Res 100(1):180–191CrossRef

Cattaruzza D, Absi N, Feillet D, Vidal T (2014) A memetic algorithm for the multi trip vehicle routing problem. Eur J Oper Res 236(3):833–848CrossRef

Chao I, Golden BL, Wasil E (1993) A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. Am J Math Manag Sci 13:371–406

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

Cordeau JF, Gendreau M, Laporte G (1997) A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2):105–119CrossRef

Crevier B, Cordeau JF, Laporte G (2007) The multi-depot vehicle routing problem with inter-depot routes. Eur J Oper Res 176(2):756–773CrossRef

Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2:393–410

Dondo RGDRG, Cerda J (2009) A hybrid local improvement algorithm for large-scale multi-depot vehicle routing problems with time windows. Comput Chem Eng 33(2):513–530CrossRef

Gillet BE, Miller LR (1974) A Heuristic algorithm for the vehicle-dispatch problem. Oper Res 22:340–349CrossRef

Hemmelmayr V, DoernerK F, Hartl RF, Rath S (2013) A heuristic solution method for node routing based solid waste collection problems. J Heuristics 19(2):129–156CrossRef

Kim BI, Kim S, Sahoo S (2006) Waste collection vehicle routing problem with time windows. Comput Oper Res 33(12):3624–3642CrossRef

Laporte G (2009) Fifty years of vehicle routing. Transp Sci 43(4):408–416CrossRef

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

Laporte G, Nobert Y, Arpin D (1984) Optimal solutions to capacitated multi-depot vehicle routing problems. Congressus Numerantium 44:283–292

Laporte G, Nobert Y, Taillefer S (1988) Solving a family of multi-depot vehicle-routing and location-routing problems. Transp Sci 22(3):161–172CrossRef

Lim A, Wang F (2005) Multi-depot vehicle routing problem: a one-stage approach. IEEE Trans Autom Sci Eng 2(4):397–402CrossRef

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

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

Maniezzo V, Stützle T, Voß S (eds) (2009) Matheuristics: hybridizing metaheuristics and mathematical programming. Annals of information system. Springer, Berlin

Markov I, Varone S, Bierlaire M (2016) Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities. Transp Res B 84:256–273CrossRef

Mingozzi A, Roberti R, Toth P (2013) An exact algorithm for the multitrip vehicle routing problem. Inf J Comput 25(2):193–207CrossRef

Muter I, Cordeau JF, Laporte G (2014) A branch-and-price algorithm for the multidepot vehicle routing problem with interdepot routes. Transp Sci 48(3):425–441CrossRef

Petch RJ, Salhi S (2003) A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discrete Appl Math 133:69–92CrossRef

Renaud J, Boctor FF, Laporte G (1996a) An improved petal heuristic for the vehicle routing problem. J Oper Res Soc 47:329–336CrossRef

Renaud J, Laporte G, Boctor FF (1996b) A tabu search heuristic for the multi-depot vehicle routing problem. Comput Oper Res 23(3):229–235CrossRef

Schneider M, Stenger A, Hof J (2015) An adaptive VNS algorithm for vehicle routing problems with intermediate stops. OR Spectr 37:353–387CrossRef

Tarantilis CD, Zachariadis EE, Kiranoudis CT (2008) A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities. Inf J Comput 20(1):154–168CrossRef

Toth P, Vigo D (eds) (2014) Vehicle routing: problems, methods, and applications, second edition. MOS-SIAM series on optimization, no. 18. SIAM, Philadelphia

Tu W, Fang Z, Li Q, Shaw S-L, Chen B (2014) A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem. Transp Res E 61:84–97CrossRef

Van Breedam A (2001) Comparing descent heuristics and metaheuristics for the vehicle routing problem. Comput Oper Res 28(4):289–315CrossRef

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

Titel: A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes
verfasst von: Tânia Rodrigues Pereira Ramos
Maria Isabel Gomes
Ana Paula Barbosa-Póvoa
Publikationsdatum: 25.11.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: OR Spectrum / Ausgabe 1/2020
Print ISSN: 0171-6468
Elektronische ISSN: 1436-6304
DOI: https://doi.org/10.1007/s00291-019-00568-7

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"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2020

Enhancing Benders decomposition algorithm to solve a combat logistics problem

A long-term unit commitment problem with hydrothermal coordination for economic and emission control in large-scale electricity systems

Balance in resource allocation problems: a changing reference approach

A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings

A matheuristic for the swap body vehicle routing problem

Acknowledgement to Reviewers