Journées de l'optimisation 2009 Optimizations days

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.

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.

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.

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.