Séance TB6 - Conception de réseaux et localisation-routage / Network Design and Location Routing
Jour mardi, le 05 mai 2009 Salle Mary Husny Président Mervat Chouman
Présentations
|
13h30- 13h55 |
A Branch and Cut Algorithm for a Heterogeneous Location Routing Problem: Computational Results |
|
Claudio Contardo, Université de Montréal, Informatique et de recherche opérationnelle/CIRRELT, Montréal, QC, Canada, H3T 1J4 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 Bernard Gendron, Université de Montréal, Informatique et de recherche opérationnelle/CIRRELT, Montréal, Québec, Canada We present a 2-index vehicle flow formulation for the Capacitated Location Routing Problem (CLRP) with homogeneous facility capacities, and extend such a formulation for the heterogeneous case. We also have developed valid inequalities and separations algorithms. Computational results show that the formulation as well as the valid inequalities help to tighten the gaps with respect to previous exact algorithms. |
|
13h55- 14h20 |
The Tree of Hubs Location Problem |
|
Ivan Contreras, CIRRELT, Canada Research Chair in Distribution Management, Université de Montréal, 2920 chemin des Services, Campus de l'Universite de Montreal, Montreal, Quebec, Canada, H3T 1J4 Elena Fernandez, Technical University of Catalonia, Department of Statistics and Operations Research, Jordi Girona 1-3, Barcelona, Catalonia, Spain, 08034 Alfredo Marin, University of Murcia, Department of Statistics and Operations Research, Campus Universitario de Espinardo, Murcia, Murcia, Spain, 30100 We present the Tree of Hubs Location problem. It is a hub location problem with the particularity that it is required that the hubs are connected by means of a tree. Potential applications appear in telecommunications and transportation systems, when set-up costs for links between hubs are so high that full interconnection between hub nodes is prohibitive. |
|
14h20- 14h45 |
A Branch-and-Cut Algorithm for Multicommodity Capacitated Fixed-Charge Network Design |
|
Mervat Chouman, Université du Québec à Montréal, CIRRELT, Montréal, Québec, Canada Teodor Gabriel Crainic, Université du Québec à Montréal, C.P. 8888, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3P8 Bernard Gendron, Université de Montréal, Informatique et de recherche opérationnelle/CIRRELT, Montréal, Québec, Canada We present a branch-and-cut algorithm for solving large-scale instances of the multicommodity capacitated network design problem. The algorithm combines cutting-plane, Lagrangian relaxation and preprocessing techniques, as well as novel branching methods. |
|
14h45- 15h10 |
MIP-Based Tabu Search for Service Network Design with Design-Balance Requirements |
|
Mervat Chouman, Université du Québec à Montréal, CIRRELT, Montréal, Québec, Canada Teodor Gabriel Crainic, Université du Québec à Montréal, C.P. 8888, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3P8 We propose a Tabu search meta-heuristic method combined with an exact method for the service network design where additional constraints such as design-balance requirements are imposed. A new arc-balance cycle move for generating neighboring solutions is introduced. Memories characterizing attributes of solutions are compiled and used to find high-quality feasible solutions. Computational results are presented. |