Article ID: | iaor20115738 |
Volume: | 59 |
Issue: | 2 |
Start Page Number: | 414 |
End Page Number: | 426 |
Publication Date: | Mar 2011 |
Journal: | Operations Research |
Authors: | Mingozzi Aristide, Baldacci Roberto, Bartolini Enrico |
Keywords: | programming: integer |
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.