nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.02.2016

Multi-depot vehicle routing problem with time windows under shared depot resources

verfasst von: Jian Li, Yang Li, Panos M. Pardalos

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A new variant of multi-depot vehicle routing problem with time windows is studied. In the new variant, the depot where the vehicle ends is flexible, namely, it is not entirely the same as the depot that it starts from. An integer programming model is formulated with the minimum total traveling cost under the constrains of time window, capacity and route duration of the vehicle, the fleet size and the number of parking spaces of each depot. As the problem is an NP-Hard problem, a hybrid genetic algorithm with adaptive local search is proposed to solve it. Finally, the computational results show that the proposed method is competitive in terms of solution quality. Compared with the classic MDVRPTW, allowing flexible choice of the stop depot can further reduce total traveling cost.

Vorheriger Artikel Integral packing of branchings in capacitaded digraphs

Nächster Artikel Crossing edges and faces of line arrangements in the plane

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

Bräysy O (2003) A reactive variable neighborhood search for the vehicle-routing problem with time windows. INFORMS J Comput 15:347–368MathSciNetCrossRefMATH

Chakhlevitch K, Cowling P (2008) Hyperheuristics: recent developments. In: Cotta C et al (eds) Adaptive and multilevel metaheuristics SCI 136. Springer, Heidelberg, pp 3–29CrossRef

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, Larporte G, Mercier A (2001) A unified tabu search heuristic for vehicle routing problems with time windows. J Oper Res Soc 52:928–936CrossRefMATH

Cordeau JF, Larporte G, Mercier A (2004) Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows. J Oper Res Soc 55:542–546CrossRefMATH

Cordeau JF, Maischberger M (2012) A parallel iterated tabu search heuristic for vehicle routing problems. Comput Oper Res 39:2033–2050CrossRef

Hashimoto H, Yagiura M, Imahori S, Ibaraki T (2013) Recent progress of local search in handling the time window constraints of the vehicle routing problem. Ann Oper Res 204:171–187MathSciNetCrossRefMATH

Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor, MI

Irnich S (2008) A unified modeling and solution framework for vehicle routing and local search-based metaheuristics. INFORMS J Comput 20:270–287MathSciNetCrossRefMATH

Juan AA, Faulin J, Ferrer A, Lourenço HR, Barrios B (2013) MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems. Top 21:109–132MathSciNetCrossRefMATH

Li F, Golden B, Wasil E (2007) The open vehicle routing problem: algorithms, large-scale test problems, and computational results. Comput Oper Res 34:2918–2930CrossRefMATH

Moccia L, Cordeau JF, Laporte G (2012) A Incremental tabu search heuristic for the generalized Vehicle routing problem with time windows. J Oper Res Soc 63:232–244CrossRef

Nagata Y, Bräysy O, Dullaert W (2010) A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput Oper Res 37:724–737CrossRefMATH

Noori S, Ghannadpour SF (2012) High-level relay hybrid metaheuristic method for multi-depot vehicle routing problem with time windows. J Math Modell Algorithms 11:159–179MathSciNetCrossRefMATH

Pisinger D, Ropke S (2007) A general heuristic for vehicle routing problems. Comput Oper Res 34:2403–2435MathSciNetCrossRefMATH

Polacek M, Harlt RF, Doerner KF (2004) A variable neighborhood search for the multi depot vehicle routing problem with time windows. J Heuristics 10:613–627CrossRef

Polacek M, Benkner S, Doerner KF, Hartl RF (2008) A cooperative and adaptive variable neighborhood search for the multi depot vehicle routing problem with time windows. BuR-Bus Res 1:207–218CrossRef

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

Repoussis PP, Tarantilis CD, Ioannou G (2007) The open vehicle routing problem with time windows. J Oper Res Soc 58:355–367CrossRefMATH

Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40:455–472CrossRef

Savelsbergh MWP (1992) The vehicle routing problem with time windows: minimizing route duration. ORSA J Comput 4:146–154CrossRefMATH

Shaw P (1997) A new local search algorithm providing high quality solutions to vehicle routing problems. Department of Computer Science, University of Strathclyde, Scotland, Technical report

Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35:254–265MathSciNetCrossRefMATH

Tansini L, Viera O (2006) New measures of proximity for the assignment algorithms in the MDVRPTW. J Oper Res Soc 57:241–249CrossRefMATH

Vidal T, Crainic TG, Gendreau M, Prins C (2013) A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows. Comput Oper Res 40:475–489MathSciNetCrossRef

Titel: Multi-depot vehicle routing problem with time windows under shared depot resources
verfasst von: Jian Li
Yang Li
Panos M. Pardalos
Publikationsdatum: 01.02.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-014-9767-4

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 2/2016

Extremal polyomino chains with respect to general Randić index

An approximation algorithm for the partial vertex cover problem in hypergraphs

Acyclic 3-coloring of generalized Petersen graphs

-labeling for brick product graphs

Algorithms for finding maximum transitive subtournaments

Improved approximations for buy-at-bulk and shallow-light -Steiner trees and -subgraph

Premium Partner