Séminaire conjoint CRT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport

TITRE : The Preemptive and Non-preemptive Swapping Problem

CONFÉRENCIER : Charles Bordenave, DIRO, Université de Montréal

DATE et ENDROIT : 18 janvier, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Gilbert Laporte (514-343-6143)

RÉSUMÉ : In this talk I will investigate the Swapping Problem on a complete graph. The Swapping Problem is a routing problem defined as follows. Each vertex of a graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for transporting objects among vertices. The Swapping Problem consists in determining a route of minimum total length that allows the vehicle to satisfy all supplies and demands by following the arcs of the route. When objects are permitted to be temporarily dropped at some intermediate vertices before being moved to their destination, the problem is called preemptive Swapping Problem. For both versions I will describe some structural properties of optimal solutions, a mathematical model and a Branch-and-Cut algorithm that allowed us to solve instances with up to 200 vertices for the non-preemptive case and up to 100 vertices for the preemptive case.