A branch‐and‐cut algorithm for the pickup‐and‐delivery traveling salesman problem with handling costs. Issue 3 (9th April 2022)

• Record Type: Journal Article
• Authors: Radha Krishnan, Devaraj; Liu, Tieming
• Is Part Of: Networks. Volume 80:Issue 3(2022)
• Page Start: 297
• Page End: 313
• Publication Date: 2022-04-09
• Subjects: branch‐and‐cut -- handling cost -- last‐in‐first‐out -- pickup‐and‐delivery -- precedence constraints -- traveling salesman problem; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22096
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: In the Pickup‐and‐Delivery Traveling Salesman Problem with Handling Costs (PDTSPH), a single vehicle has to satisfy multiple customer requests, each defined by a pickup location and a delivery location. Cargo handling is performed at the rear end of the vehicle, in a Last‐In‐First‐Out (LIFO) order for PDTSPH. However, additional handling operations are permitted with a penalty if other loads that block the access to the delivery have to be unloaded and reloaded. The objective of PDTSPH is to minimize the total transportation and handling cost. In this paper, we present a new Mixed Integer Programming (MIP) model and a branch‐and‐cut algorithm to solve PDTSPH. We also present new integral separation procedures to effectively handle the exponential number of constraints in our MIP model. A family of inequalities are introduced to enhance the scalability of our implementation. The performance of our approach is compared with a compact formulation from the literature (Veenstra et al. [21]) in instances ranging from 9 to 21 customer requests. Computational results show our algorithm outperforming the compact formulation in 69% of instances with an average runtime improvement of 57%.