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

Enrico Bartolini*, Lawrence Bodin, Aristide Mingozzi

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)95-110
Number of pages16
JournalNETWORKS
Volume67
Issue number2
DOIs
Publication statusPublished - 1 Mar 2016
MoE publication typeA1 Journal article-refereed

Keywords

  • branch-and-price
  • cut-and-column generation
  • dual ascent

Fingerprint Dive into the research topics of 'The traveling salesman problem with pickup, delivery, and ride-time constraints'. Together they form a unique fingerprint.

Cite this