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

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

Enrico Bartolini;Aristide Mingozzi
2016

Abstract

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
Enrico Bartolini, Lawrence Bodin, Aristide Mingozzi
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/629957
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact