A Branch-and-cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem

Hipólito Hernández-Pérez and Juan-José Salazar-González

European Journal of Operational Research, 2022, vol. 297, issue 2, 467-483

Abstract: This paper deals with the problem of designing a minimum-cost route for a capacitated vehicle moving a commodity between a set of customers, allowing two features uncommon in the pickup-and-delivery literature. One feature is that a customer accepts to be visited several times, i.e., splitting a customer demand is allowed. The other feature is that a customer may be used as an intermediate location to collect and deliver commodity temporarily. The problem is called Split-Delivery One-Commodity Pickup-and-Delivery Travelling Salesman Problem, and finds applications in bike sharing systems where a single vehicle moves bikes between bike stations of a city district during the night to set the network to an initial configuration. The paper proposes a new branch-and-cut algorithm to find optimal solutions. A master problem solves a relaxed Mixed Integer Programming model, i.e., a model allowing all feasible solutions and also some invalid ones. A subproblem checks the feasibility of the master solutions and generates valid cuts when they are infeasible. Computational results on benchmark instances demonstrate the good performance of the algorithm compared with others in the literature. In particular, it solves benchmark instances with 60 customers that were unsolved.

Keywords: Travelling salesman; Vehicle routing problem; Split demand; Pickup-and-delivery; Bike shared system (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721004689
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:297:y:2022:i:2:p:467-483

DOI: 10.1016/j.ejor.2021.05.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 ().