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

Roberto Baldacci (), Enrico Bartolini () and Aristide Mingozzi ()
Additional contact information
Roberto Baldacci: Department of Electronics, Computer Science, and Systems (DEIS), University of Bologna, 47521 Cesena, Italy
Enrico Bartolini: Department of Computer Science, University of Bologna, 40127 Bologna, Italy
Aristide Mingozzi: Department of Mathematics, University of Bologna, 47521 Cesena, Italy

Operations Research, 2011, vol. 59, issue 2, 414-426

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.

Keywords: pickup and delivery; set partitioning; dual ascent; column generation (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (62)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0881 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:2:p:414-426

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().