Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
4OR
Published in: 4OR 1/2023

26-11-2021 | Research Paper

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

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

Published in: 4OR | Issue 1/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

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.
previous article Multiple criteria sorting models and methods—Part I: survey of the literature
next article A theoretical look at Electre Tri-nB and related sorting models

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now
Appendix
Available only for authorised users
Footnotes
Literature
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
Metadata
Title
A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem
Authors
Caio Marinho Damião
João Marcos Pereira Silva
Eduardo Uchoa
Publication date
26-11-2021
Publisher
Springer Berlin Heidelberg
Published in
4OR / Issue 1/2023
Print ISSN: 1619-4500
Electronic ISSN: 1614-2411
DOI
https://doi.org/10.1007/s10288-021-00498-7

Other articles of this Issue 1/2023

4OR 1/2023 Go to the issue

Research Paper

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

Research Paper

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

PhD Thesis

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

PhD Thesis

Exploiting hypergraphs’ properties in binary polynomial optimization

Invited Survey

Multiple criteria sorting models and methods—Part I: survey of the literature

Research Paper

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

Premium Partners

    Image Credits