𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Models and branch-and-cut algorithms for pickup and delivery problems with time windows

✍ Scribed by Stefan Ropke; Jean-François Cordeau; Gilbert Laporte

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
175 KB
Volume
49
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In the pickup and delivery problem with time windows (PDPTW), capacitated vehicles must be routed to satisfy a set of transportation requests between given origins and destinations. In addition to capacity and time window constraints, vehicle routes must also satisfy pairing and precedence constraints on pickups and deliveries. This paper introduces two new formulations for the PDPTW and the closely related dial‐a‐ride problem (DARP) in which a limit is imposed on the elapsed time between the pickup and the delivery of a request. Several families of valid inequalities are introduced to strengthen these two formulations. These inequalities are used within branch‐and‐cut algorithms which have been tested on several instance sets for both the PDPTW and the DARP. Instances with up to eight vehicles and 96 requests (194 nodes) have been solved to optimality. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 258–272 2007

📜 SIMILAR VOLUMES

A branch-and-cut algorithm for the picku
A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks
✍ Jean-François Côté; Claudia Archetti; Maria Grazia Speranza; Michel Gendreau; Je 📂 Article 📅 2012 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB 👁 1 views

This article studies the pickup and delivery traveling salesman problem with multiple stacks. The vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy the last-in-first-out constraint that states that any new item

Approximation algorithms for the capacit
Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries
✍ Shoshana Anily; Julien Bramel 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

We consider the Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSPPD). This problem is characterized by a set of n pickup points and a set of n delivery points. A single product is available at the pickup points which must be brought to the delivery points. A vehicle of limited

A branch-and-cut algorithm for the preem
A branch-and-cut algorithm for the preemptive swapping problem
✍ Charles Bordenave; Michel Gendreau; G. Laporte 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 1 views

## Abstract In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determinin