An Exact Algorithm for the Traveling Salesman Problem With Pickup and Delivery Under Time Windows and Ride‐Time Constraints

ABSTRACT

The Traveling Salesman problem with pickup, delivery, and ride‐time constraints (TSPPD‐RT) requires a depot‐based vehicle to visit multiple known requests. Each request specifies a pickup vertex, corresponding delivery vertex, and maximum travel time between them ( ride‐time ). The goal is to find a tour that (i) starts and finishes at the depot, (ii) visits all requests, (iii) satisfies ride‐time constraints for each request, and (iv) minimizes the vehicle's total travel cost. Additionally, undelivered requests must remain within the vehicle's capacity limit. The TSPPD‐RT is a fundamental optimization problem in logistics and routing. This paper introduces an exact method for solving an extended version of the TSPPD‐RT with time window constraints (TSPPD‐TWRT), incorporating both ride‐time constraints (RTCs) and hard ride‐time constraints (HRTCs). RTCs consider only travel and service times, while in the hard case, they also include waiting times, the former being a relaxation of the latter. This paper presents two mathematical formulations: an arc‐based formulation and a set‐partitioning formulation based on the ‐tour relaxation proposed by [1]. Using these formulations, we develop MIP‐based and branch‐price‐and‐cut solution approaches. Computational experiments on datasets from the Dial‐A‐Ride Problem and the Pickup and Delivery Problem with Time Windows demonstrate the effectiveness of the proposed methods. Results indicate that the ‐tour formulation is particularly efficient, solving instances with up to 60 requests within reasonable computational times.