Valid inequalities and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks

Armando Honorio Pereira, Geraldo Robson Mateus and Sebastián Alberto Urrutia

European Journal of Operational Research, 2022, vol. 300, issue 1, 207-220

Abstract: The focus of this work is the study of valid inequalities and exact algorithms for the pickup and delivery traveling salesman problem with multiple stacks. In the problem, a single vehicle must fulfill a set of client requests. Each request states that the vehicle must pick up an item at a given location, and later deliver it to another particular location. Inside the vehicle, items are stored in horizontal stacks of limited capacity. The loading and unloading operations of items follow the last-in-first-out policy. Every item is picked up on top of a stack and can only be delivered if it is also on top of its stack. The goal of this problem is to find a vehicle route of minimum cost. We propose a new formulation along with new valid inequalities for the problem. Several of these valid inequalities are lifted versions of inequalities previously proposed in the literature. The branch-and-cut algorithm based on the formulation and the valid inequalities is compared with the state-of-the-art solution methods for the problem. Computational experiments performed on benchmark instances show that the implemented algorithm outperforms all other competing exact algorithms for this problem.

Keywords: Combinatorial optimization; Branch-and-cut; Traveling salesman; Pickup and delivery; Multiple stacks (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721006615
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:300:y:2022:i:1:p:207-220

DOI: 10.1016/j.ejor.2021.07.051

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 ().