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

TITRE: New algorithms for solving some Traveling Salesman Problems with Pickups and Deliveries

CONFÉRENCIER: Juan José Salazar Gonzaléz, Universidád de la Laguna, Tenerife, Espagne

DATE et ENDROIT: jeudi 25 avril, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE: Gilbert Laporte (343-6143)

RÉSUMÉ: We introduce a new routing problem called "One-commodity Pickup-and-Delivery Traveling Salemans Problems" (1-PDTSP) and defined as follows. Consider a set of customers divided into two groups : the delivery customers ask for a known demand of a product, and the pickup customers provide a known demand of the same product. There is also a depot and a vehicle with a fixed capacity. An example of the product could be "money", while the customers can be thought as bank branches in a city (some requiring money and others providing money), and the depot is the central main office. The problem is to find a Hamiltonian tour for the vehicle minimizing the routing cost and satisfying all customer requirements while respecting vehicle capacity. We provide an ILP model for this problem and use it in a branch-and-cut framework to solve the problem to optimality. We also provide an LP-based heuristic for large instances. The proposed model and algorithms can easily be adapted to solve problems involving two commodities, and therefore to solve the problem known in literature as "TSP with Pickups and Deliveries". Extensive computational results are provided and discussed.