Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
4OR
Erschienen in: 4OR 1/2023

26.11.2021 | Research Paper

A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem

verfasst von: Caio Marinho Damião, João Marcos Pereira Silva, Eduardo Uchoa

Erschienen in: 4OR | Ausgabe 1/2023

Einloggen

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

search-config
loading …

Abstract

The Cumulative Capacitated Vehicle Routing Problem is a variant of the classic routing problem in which the objective function is to minimize the sum of arrival times to customers. This article proposes a model for the problem that uses position indexes in order to calculate the contribution of the travel time of an edge to the arrival times of the remaining customers on a route. The model is implemented and solved by the branch-cut-and-price (BCP) algorithm in the VRPSolver package. Computational experiments indicate that the proposed BCP model is superior to the literature, being able to solve many open instances. Good results were also obtained for the Multi-Depot variant of the problem.
Vorheriger Artikel Multiple criteria sorting models and methods—Part I: survey of the literature
Nächster Artikel A theoretical look at Electre Tri-nB and related sorting models

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 "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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
Literatur
Abeledo H, Fukasawa R, Pessoa A, Uchoa E (2013) The time dependent traveling salesman problem: polyhedra and algorithm. Math Program Comput 5(1):27–55CrossRef
Augerat P, Belenguer JM, Benavent E, Corberán A, Naddef D, Rinaldi G (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. Tech. Rep. 949-M, Université Joseph Fourier, Grenoble, France
Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math Program 115:351–385CrossRef
Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper Res 59(5):1269–1283CrossRef
Blum A, Chalasani P, Coppersmith D, Pulleyblank B, Raghavan P, Sudan M (1994) The minimum latency problem. In: Proceedings of the twenty-sixth annual ACM symposium on theory of computing, pp 163–171
Bruni M, Nucamendi-Guillén S, Khodaparasti S, Beraldi P (2019) The cumulative capacitated vehicle routing problem with profits under uncertainty. Advances in optimization and decision science for society. Springer, Services and Enterprises, Berlin, pp 311–322
Bulhoes T, Sadykov R, Uchoa E (2018) A branch-and-price algorithm for the minimum latency problem. Comput Oper Res 93:66–78CrossRef
Campbell AM, Vandenbussche D, Hermann W (2008) Routing for relief efforts. Transp Sci 42(2):127–145CrossRef
Christofides N, Eilon S (1969) An algorithm for the vehicle-dispatching problem. J Oper Res Soc 20(3):309–318CrossRef
Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. In: Mingozzi A, Toth P, Sandi C, Christofides N (eds) Combinatorial optimization. Wiley, Hoboken
Cinar D, Ervural BC, Gakis K, Pardalos PM (2017) Constructive algorithms for the cumulative vehicle routing problem with limited duration. In: Sustainable logistics and transportation, Springer, pp 57–86
Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim 12:129–146CrossRef
Cordeau JF, Gendreau M, Laporte G (1997) A tabu search heuristic for periodic and multi-depot vehicle routing problems. Netw Int J 30(2):105–119
Corona-Gutiérrez K, Cruz ML, Nucamendi-Guillén S, Olivares-Benitez E (2020) The cumulative capacitated vehicle routing problem including priority indexes. In: Green transportation and new advances in vehicle routing problems, Springer, pp 91–129
Dunning I, Huchette J, Lubin M (2017) JuMP: a modeling language for mathematical optimization. SIAM Rev 59(2):295–320CrossRef
Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column Gener. Springer, Boston, pp 33–65CrossRef
Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper Res 56(2):497–511CrossRef
Ke L (2018) A brain storm optimization approach for the cumulative capacitated vehicle routing problem. Memet Comput 10(4):411–421CrossRef
Kyriakakis NA, Marinaki M, Marinakis Y (2021) A hybrid ant colony optimization-variable neighborhood descent approach for the cumulative capacitated vehicle routing problem. Comput Oper Res p 105397
Lalla-Ruiz E, Voß S (2020) A popmusic approach for the multi-depot cumulative capacitated vehicle routing problem. Optim Lett 14(3):671–691CrossRef
Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. Oper-Res-Spektrum 5(2):77–85CrossRef
Liu R, Jiang Z (2019) A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints. Appl Soft Comput 80:18–30CrossRef
Lucena A (1990) Time-dependent traveling salesman problem-the deliveryman case. Networks 20(6):753–763CrossRef
Lysgaard J, Wøhlk S (2014) A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. Eur J Oper Res 236(3):800–810CrossRef
Montoya-Torres JR, Franco JL, Isaza SN, Jiménez HF, Herazo-Padilla N (2015) A literature review on the vehicle routing problem with multiple depots. Comput Ind Eng 79:115–129CrossRef
Ngueveu SU, Prins C, Calvo RW (2010) An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput Oper Res 37(11):1877–1885CrossRef
Nucamendi-Guillén S, Angel-Bello F, Martínez-Salazar I, Cordero-Franco AE (2018) The cumulative capacitated vehicle routing problem: new formulations and iterated greedy algorithms. Expert Syst Appl 113:315–327CrossRef
Nucamendi-Guillén S, Flores-Díaz D, Olivares-Benitez E, Mendoza A (2020) A memetic algorithm for the cumulative capacitated vehicle routing problem including priority indexes. Appl Sci 10(11):3943CrossRef
Osorio-Mora A, Soto-Bustos M, Gatica G, Palominos P, Linfati R (2021) The multi-depot cumulative vehicle routing problem with mandatory visit times and minimum delayed latency. IEEE Access 9:27210–27225CrossRef
Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math Program Comput 9(1):61–100CrossRef
Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H (2017) Limited memory rank-1 cuts for vehicle routing problems. Oper Res Lett 45(3):206–209CrossRef
Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2019) A generic exact solver for vehicle routing and related problems. In: Lodi A, Nagarajan V (eds) Integer programming and combinatorial optimization. Springer International Publishing, Cham, pp 354–369CrossRef
Picard JC, Queyranne M (1978) The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper Res 26(1):86–110CrossRef
Ramadhan F, Imran A (2019) An adaptation of the record-to-record travel algorithm for the cumulative capacitated vehicle routing problem. In: 2019 IEEE international conference on industrial engineering and engineering management (IEEM), IEEE, pp 238–242
Ribeiro GM, Laporte G (2012) An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Comput Oper Res 39(3):728–735CrossRef
Roberti R, Mingozzi A (2014) Dynamic ng-path relaxation for the delivery man problem. Transp Sci 48(3):413–424CrossRef
Salehipour A, Goos P, Sorensen K, Braysy O (1983) The traveling repairman problem. In: Proceedings of the 21st annual conference of the Belgian operational research society (ORBEL’83)
Smiti N, Dhiaf MM, Jarboui B, Hanafi S (2020) Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem. Int Trans Oper Res 27(1):651–664CrossRef
Sze JF, Salhi S, Wassan N (2017) The cumulative capacitated vehicle routing problem with min–sum and min–max objectives: an effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search. Transp Res Part B Methodol 101:162–184CrossRef
Metadaten
Titel
A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem
verfasst von
Caio Marinho Damião
João Marcos Pereira Silva
Eduardo Uchoa
Publikationsdatum
26.11.2021
Verlag
Springer Berlin Heidelberg
Erschienen in
4OR / Ausgabe 1/2023
Print ISSN: 1619-4500
Elektronische ISSN: 1614-2411
DOI
https://doi.org/10.1007/s10288-021-00498-7

Weitere Artikel der Ausgabe 1/2023

4OR 1/2023 Zur Ausgabe

Research Paper

A branch and bound approach for the tower crane selection and positioning problem with respect to mutual interference

PhD Thesis

Empirical analysis of stochastic local search behaviour: connecting structure, components and landscape

Research Paper

A decomposition based minimax regret approach for inverse multiple criteria sorting problem

Research Paper

A theoretical look at Electre Tri-nB and related sorting models

Research Paper

Constraint qualifications and optimality conditions for robust nonsmooth semi-infinite multiobjective optimization problems

PhD Thesis

Exploiting hypergraphs’ properties in binary polynomial optimization

Premium Partner

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen. 

    Zur Marktübersicht
    Bildnachweise