Back

Session TB6 - Conception de réseaux et localisation-routage / Network Design and Location Routing

Day Tuesday, May 05, 2009
Room Mary Husny
President Mervat Chouman

Presentations

01h30 PM-
01h55 PM
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.


01h55 PM-
02h20 PM
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.


02h20 PM-
02h45 PM
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.


02h45 PM-
03h10 PM
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.


Back