The pickup and delivery traveling salesman problem with handling costs

Marjolein Veenstra, Kees Jan Roodbergen, Iris F.A. Vis and Leandro C. Coelho

European Journal of Operational Research, 2017, vol. 257, issue 1, 118-132

Abstract: This paper introduces the pickup and delivery traveling salesman problem with handling costs (PDTSPH). In the PDTSPH, a single vehicle has to transport loads from origins to destinations. Loading and unloading of the vehicle is operated in a last-in-first-out (LIFO) fashion. However, if a load must be unloaded that was not loaded last, additional handling operations are allowed to unload and reload other loads that block access. Since the additional handling operations take time and effort, penalty costs are associated with them. The aim of the PDTSPH is to find a feasible route such that the total costs, consisting of travel costs and penalty costs, are minimized. We show that the PDTSPH is a generalization of the pickup and delivery traveling salesman problem (PDTSP) and the pickup and delivery traveling salesman problem with LIFO loading (PDTSPL). We propose a large neighborhood search (LNS) heuristic to solve the problem. We compare our LNS heuristic against best known solutions on 163 benchmark instances for the PDTSP and 42 benchmark instances for the PDTSPL. We provide new best known solutions on 52 instances for the PDTSP and on 15 instances for the PDTSPL, besides finding the optimal or best known solution on 102 instances for the PDTSP and on 23 instances for the PDTSPL. The LNS finds optimal or near-optimal solutions on instances for the PDTSPH. Results show that PDTSPH solutions provide large reductions in handling compared to PDTSP solutions, while increasing the travel distance by only a small percentage.

Keywords: Routing; Pickup and delivery; Packing; Handling costs; Metaheuristics (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171630546X
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:257:y:2017:i:1:p:118-132

DOI: 10.1016/j.ejor.2016.07.009

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