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.