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

Caio Marinho Damião (), João Marcos Pereira Silva () and Eduardo Uchoa ()
Additional contact information
Caio Marinho Damião: Universidade Federal Fluminense
João Marcos Pereira Silva: Universidade Federal Fluminense
Eduardo Uchoa: Universidade Federal Fluminense

4OR, 2023, vol. 21, issue 1, No 2, 47-71

Abstract: 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.

Keywords: Routing; Column generation; Integer programming; Modeling; 90B06; 90C57; 90C27; 90C35; 90C11 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10288-021-00498-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:21:y:2023:i:1:d:10.1007_s10288-021-00498-7

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-021-00498-7

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().