Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : An Exact Algorithm for the Pickup and Delivery Problem with Time Windows
CONFÉRENCIER : Enrico Bartolini, Università di Bologna, Italy
DATE et ENDROIT : 16 février, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Gilbert Laporte (514-343-6143)
RÉSUMÉ : We consider the Pickup and Delivery Problem with Time Windows (PDPTW) where a set of m identical vehicles, located at a central depot, must be optimally routed to service a set of customers. Each customer requires that a given quantity is transported by one vehicle from a pickup location to a corresponding delivery location, and with each location is associated a time window. Each vehicle route must start and end at the depot and service a subset of the customers while satisfying capacity and time window constraints. We present an exact algorithm for the PDPTW based on a set partitioning-like formulation with additional cuts, and we describe a bounding procedure that uses column-and-cut generation to find a near-optimal dual solution of its LP-relaxation. This dual solution is used to attempt to generate all variables having reduced cost smaller than the gap between a known upper bound and the lower bound achieved. If the attempt succeeds, the resulting reduced problem is solved by an integer programming solver; otherwise, a branchand- cut-and-price algorithm is used to close the integrality gap. Computational results on benchmark instances from the literature show the effectiveness of the proposed method.