Premium
The traveling salesman problem with pickup, delivery, and ride‐time constraints
Author(s) -
Bartolini Enrico,
Bodin Lawrence,
Mingozzi Aristide
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21663
Subject(s) - travelling salesman problem , pickup , computer science , constraint (computer aided design) , mathematical optimization , service (business) , vehicle routing problem , travel time , time constraint , operations research , routing (electronic design automation) , mathematics , computer network , algorithm , transport engineering , engineering , economy , artificial intelligence , law , political science , economics , image (mathematics) , geometry
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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(2), 95–110 2016