Séance MB6 - Problème du voyageur de commerce / Traveling Salesman Problem
Jour lundi, le 04 mai 2009 Salle Mary Husny Président Jean-Yves Potvin
Présentations
|
15h30- 15h55 |
An Effective Heuristic for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading and Multiple Stacks |
|
Jean-François Côté, Université de Montréal, DIRO - CIRRELT, 2920 chemin de la Tour, Montréal, QC , Canada, H3T 1J4 Michel Gendreau, Université de Montréal, Informatique et recherche opérationnelle, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7 Jean-Yves Potvin, Université de Montréal, Informatique et recherche opérationnelle, C.P. 6128, succ. Centre-Ville, Montréal, Québec, Canada, H3C 3J7 We consider a pickup and delivery routing problem for a single vehicle where objects can be loaded on one of multiple stacks inside the vehicle. Each object has a length and only the top item of each stack is available for delivery. The cumulative length of the objects on each stack must not exceed at any time some maximal length |
|
15h55- 16h20 |
On a Time-Dependent 2-Path Model for the (Cumulative) ATSP |
|
Luis Gouveia, Universidade de Lisboa, DEIO-CIO Faculdade de Ciências, Cidade Universitaria Bloco C6 Piso 4, Campo Grande, Lisboa, Portugal, 1749-016 Maria Teresa Godinho, Escola Superio de Technolgia e Gestao, Departamento de Matematica, Portugal For the ATSP the so-called 2-path formulations do not improve upon the linear programming bound of the corresponding 1-path formulation. We show that this is not the case when we use a 2-path time-dependent formulation. Computational results show that the new formulation enhanced with the valid inequalities produces very tight linear bounds. |
|
16h20- 16h45 |
Polyhedral Study of a Cumulative One-to-Many Pickup and Delivery Traveling Salesman Problem |
|
Géraldine Heilporn, HEC Montréal, Chaire de recherche du Canada en distributique/CIRRELT, Belgique Jean-François Cordeau, GERAD, HEC Montréal, Chaire de recherche du Canada en logistique et en transport/CIRRELT, 3000 Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7 Gilbert Laporte, GERAD, HEC Montréal, Chaire de recherche du Canada en distributique/GERAD/CIRRELT, 3000 Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7 Consider a variant of the Traveling Salesman Problem where one pickup node must be visited before a set of delivery nodes, each node being associated with a time window. The Cumulative version of the problem aims at minimizing the sum of times between the pickup node and each of the delivery nodes, while satisfying the time windows on nodes. |
|
16h45- 17h10 |
Modelization of Time-Dependent Urban Freight Problems by Using a Multiple Number of Distribution Centers |
|
David Escuin, University of Zaragoza, Department of Mechanical Engineering, Maria de Luna, Zaragoza, Zaragoza, Spain, 50018 Carlos Millán, Technological Institute of Aragon, Maria de Luna, 8, Zaragoza, Zaragoza, Spain, 50018 Emilio Larrodé, University of Zaragoza, Department of Mechanical Engineering, Maria de Luna, Zaragoza, Zaragoza, Spain, 50018 We present a model, based on the Time-Dependent Vehicle Routing Problem with Time Windows, for urban distribution problems by means of hubs in large cities. In this model, a change in the traditional approach is proposed by adopting a system in which some customers are served by urban hubs while remaining customers are served by traditional routes. |