An Exact Price-Cut-and-Enumerate Method for the Capacitated Multitrip Vehicle Routing Problem with Time Windows

Yu Yang ()
Additional contact information
Yu Yang: Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32603

Transportation Science, 2023, vol. 57, issue 1, 230-251

Abstract: We consider the capacitated multitrip vehicle routing problem with time windows (CMTVRPTW), where vehicles are allowed to make multiple trips. The ability to perform multiple trips is necessary for some real-world applications where the vehicle capacity, the trip duration, or the number of drivers or vehicles is limited. However, it substantially increases the solution difficulty in view of the additional trip scheduling aspect. We propose an exact price-cut-and-enumerate method (EPCEM) that solves a novel superstructure-based formulation inspired by Paradiso et al. (2020) . The EPCEM obtains a tight lower bound by an alternating column and row generation method and computes a valid upper bound in the early stage of the algorithm. It obtains an optimal solution and further proves its optimality by a new multiphase sift-and-cut method. Computationally, the EPCEM significantly outperforms the state-of-the-art exact method that only proves optimality for 9 of the 27 test instances with 50 customers. In particular, the EPCEM solves all test instances with up to 70 customers to optimality for the first time and obtains near-optimal solutions with an average optimality gap of no more than 0.3% for instances with 80 to 100 customers. From a practical point of view, solving the CMTVRPTW by the EPCEM yields a solution that, on average, uses at least 45% fewer vehicles and increases the travel cost by no more than 7% compared with the solution to the standard CVRPTW.

Keywords: multitrip vehicle routing; price cut and enumerate; column and row generation (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1161 (application/pdf)

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:inm:ortrsc:v:57:y:2023:i:1:p:230-251

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().