Strong cutting planes for the capacitated multi-pickup and delivery problem with time windows

Amit Kohar, Suresh Kumar Jakhar and Yogesh K. Agarwal

Transportation Research Part B: Methodological, 2023, vol. 176, issue C

Abstract: In this paper, we propose an improved 2-index mixed integer linear programming formulation for capacitated multi-pickup and delivery problems with time windows. We develop new families of valid inequalities, present some simple separation heuristics and solve the benchmark problems using a cutting plane approach. Specifically, we propose and demonstrate the effectiveness of incompatible request sets based valid inequalities, exploiting thereby the time window and capacity constraints. Further, we introduce two sub-families of these inequalities: node-based and request-based incompatible request set cuts, along with their separation heuristics. The computational results show that the incompatible request set cuts are highly useful as cutting planes for the benchmark instances. Overall, there is a marked improvement in solution performance vis-à-vis the different formulations and solution approaches used in extant literature. The approach in this paper is able to solve 12%, 37% and 43% more instances to optimality, improve the root gap by 18%, 33% and 36%, and final gap by 36%, 45% and 43% vis-à-vis the asymmetric representative formulation, three-index and the two-index formulations respectively.

Keywords: Valid inequalities; Multi pickup and delivery problem; Branch-and-bound algorithm; Vehicle routing problem; Time windows; Cutting Plane approach (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261523001315
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:transb:v:176:y:2023:i:c:s0191261523001315

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2023.102806

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().