Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport

TITRE : Exact Solution of Large-Scale Hub Location Problems with Multiple Capacity Levels

CONFÉRENCIER : Ivan Contreras, Université Concordia, Canada

DATE et ENDROIT : 28 septembre 2011, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Jean-François Cordeau (514 340-6278)

RÉSUMÉ : This talk presents an extension of the classical capacitated hub location problem with multiple assignments in which the amount of capacity installed at the hubs is part of the decision process. An exact algorithm based on a Benders decomposition of a strong path-based formulation is proposed to solve large-scale instances of two variants of the problem: the splittable and non-splittable commodities cases. The standard decomposition algorithm is enhanced through the inclusion of features such as the generation of strong optimality cuts and the integration of reduction tests. Given that in the non-splittable case the resulting subproblem is an integer program, we develop an efficient enumeration algorithm. Extensive computational experiments are reported and analyzed to evaluate the efficiency and robustness of the proposed algorithms. This presentation is the result of a joint project carried out with Gilbert Laporte and Jean-François Cordeau while the author was working at HEC Montréal and CIRRELT.