Exact algorithms for the multi-pickup and delivery problem with time windows

Imadeddine Aziez, Jean-François Côté and Leandro C. Coelho

European Journal of Operational Research, 2020, vol. 284, issue 3, 906-919

Abstract: In the multi-pickup and delivery problem with time windows (MPDPTW) a set of vehicles must be routed to satisfy a set of client requests between given origins and destinations. A request is composed of several pickups of different items, followed by a single delivery at the client location. This paper introduces two new formulations for the MPDPTW, the 2-index formulation, and the asymmetric representatives formulation. In addition, we also present an existing 3-index formulation for this problem and improve it by means of several preprocessing and valid inequalities. We solve the problem exactly via a branch-and-cut algorithm. We introduce several families of valid inequalities to strengthen the LP relaxations of the proposed formulations. Computational results are reported on different types of instances to firstly highlight the advantage of adding different families of valid inequalities then to compare the performance of the different formulations presented in this paper. While the heuristic and exact algorithms of the literature prove optimality for 16 instances containing up to 50 nodes, we prove optimality for 41 instances for cases containing up to 100 nodes from the existing benchmark set.

Keywords: Vehicle routing problem; Multi-pickup and delivery problem; Sequential ordering problem; Branch-and-cut (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720300771
Full text for ScienceDirect subscribers only

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:eee:ejores:v:284:y:2020:i:3:p:906-919

DOI: 10.1016/j.ejor.2020.01.040

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().