An Exact Algorithm for the Pickup and Delivery Problem with Time Windows

TLDR

The pickup and delivery problem with time windows (PDPTW) extends the vehicle routing problem with time windows by routing identical vehicles from a central depot to satisfy transportation requests under capacity, time window, pairing, and precedence constraints. This study introduces an exact algorithm for the PDPTW that employs a set‑partitioning‑like integer formulation and a bounding procedure combining dual‑ascent heuristics with cut‑and‑column generation to obtain a near‑optimal dual solution. The derived dual solution is used to generate a reduced problem containing only routes whose reduced costs fall below the gap between a known upper bound and the lower bound, which is then solved by an IP solver for moderate instances or by a branch‑and‑cut‑and‑price algorithm for larger ones. Computational experiments on benchmark instances demonstrate the effectiveness of the proposed exact method.

Abstract

The pickup and delivery problem with time windows (PDPTW) is a generalization of the vehicle routing problem with time windows. In the PDPTW, a set of identical vehicles located at a central depot must be optimally routed to service a set of transportation requests subject to capacity, time window, pairing, and precedence constraints. In this paper, we present a new exact algorithm for the PDPTW based on a set-partitioning–like integer formulation, and we describe a bounding procedure that finds a near-optimal dual solution of the LP-relaxation of the formulation by combining two dual ascent heuristics and a cut-and-column generation procedure. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between a known upper bound and the lower bound achieved. If the resulting problem has moderate size, it is solved by an integer programming solver; otherwise, a branch-and-cut-and-price algorithm is used to close the integrality gap. Extensive computational results over the main instances from the literature show the effectiveness of the proposed exact method.