CRIS Current Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishThe 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.
| Titolo: | An Exact Algorithm for the Pickup and Delivery Problem with Time Windows |
| Autore/i: | BALDACCI, ROBERTO; BARTOLINI, ENRICO; MINGOZZI, ARISTIDE |
| Autore/i Unibo: | |
| Anno: | 2011 |
| Rivista: | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1287/opre.1100.0881 |
| 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. |
| Data prodotto definitivo in UGOV: | 2013-05-16 13:12:44 |
| Appare nelle tipologie: | 1.01 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11585/96285
Copyright © 2021