The traveling salesman problem with pickup, delivery, and ride-time constraints

In the traveling salesman problem with pickup, delivery, and ride-time constraints (TSPPD-RT), a vehicle located at a depot is required to service a number of requests where the requests are known before the route is formed. Each request consists of (i) a pickup location (origin), (ii) a delivery location (destination), and (iii) a maximum allowable travel time from the origin to the destination (maximum ride-time). The problem is to design a tour for the vehicle that (i) starts and ends at the depot, (ii) services all requests, (iii) ensures that each request's ride-time does not exceed its maximum ride-time, and (iv) minimizes the total travel time required by the vehicle to service all requests (objective function). A capacity constraint that may be present is that the weight or volume of the undelivered requests on the vehicle must always be no greater than the vehicle's capacity. In this article, we concurrently analyze the TSPPD-RT with capacity constraints and without capacity constraints. We describe two mathematical formulations of the problem. These formulations are used to derive new lower bounds on the solution to the problem. Then, we provide two exact methods for finding the optimal route that minimizes the total travel cost. Our extensive computational analysis on both versions of the TSPPD-RT shows that the proposed algorithms are capable of solving to optimality instances involving up to 50 requests