An Exact Solution Framework for Multitrip Vehicle-Routing Problems with Time Windows

Rosario Paradiso (), Roberto Roberti (), Demetrio Laganá () and Wout Dullaert ()
Additional contact information
Rosario Paradiso: Department of Mathematics and Computer Science, University of Calabria, 87036 Arcavacata di Rende CS, Italy
Roberto Roberti: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands
Demetrio Laganá: Department of Mechanical, Energy and Management Engineering, University of Calabria, 87036 Arcavacata di Rende CS, Italy
Wout Dullaert: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands

Operations Research, 2020, vol. 68, issue 1, 180-198

Abstract: Multitrip vehicle - routing problems (MTVRPs) generalize the well-known VRP by allowing vehicles to perform multiple trips per day. MTVRPs have received a lot of attention lately because of their relevance in real-life applications—for example, in city logistics and last-mile delivery. Several variants of the MTVRP have been investigated in the literature, and a number of exact methods have been proposed. Nevertheless, the computational results currently available suggest that MTVRPs with different side constraints require ad hoc formulations and solution methods to be solved. Moreover, solving instances with just 25 customers can be out of reach for such solution methods. In this paper, we proposed an exact solution framework to address four different MTVRPs proposed in the literature. The exact solution framework is based on a novel formulation that has an exponential number of variables and constraints. It relies on column generation, column enumeration, and cutting plane. We show that this solution framework can solve instances with up to 50 customers of four MTVRP variants and outperforms the state-of-the-art methods from the literature.

Keywords: multitrip vehicle routing; time windows; column generation; exact methods; dynamic programming (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1874 (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:oropre:v:68:y:2020:i:1:p:180-198

Access Statistics for this article

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