Séance WA3 - Routage et transport / Routing and Transportation
Jour mercredi, le 9 mai 2007 Salle Gérard Parizeau Président Marcus V. Poggi de Aragão
Présentations
|
10h30- 10h55 |
Decomposition of a Liquefied Natural Gas Inventory Routing Problem |
|
Roar Grønhaug, Norwegian University of Science and Technology, Industrial Economics and Technology Management, Alfred Getz veg 3, Trondheim, Norway, NO-7491 Marielle Christiansen, Norwegian University of Science and Technology, Industrial Economics and Technology Management, Alfred Getz veg 3, Trondheim, Norway, NO-7491 Guy Desaulniers, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7 Jacques Desrosiers, HEC Montréal, GERAD et Méthodes quantitatives de gestion, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7 We consider a complex maritime inventory routing problem in the liquefied natural gas business with several complicating aspects. The problem is solved by a branch-and-price method. The column generation master problem is rich, and handles the inventory management and the port capacity, while the subproblems generate the ship route columns. Different accelerating strategies will be presented. We will also report preliminary results. |
|
10h55- 11h20 |
A Comparison of Toll and Design Models for a Hazardous Materials Transportation Problem |
|
Anne Mercier, Université de Montréal, CIRRELT, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7 Patrice Marcotte, Université de Montréal, Informatique et recherche opérationnelle, CIRRELT, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7 Gilles Savard, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7 Vedat Verter, McGill University, Desautels Faculty of Management, 1001 Sherbrooke Ouest, Montréal, Québec, Canada The population exposed to hazardous materials transportation can be reduced by specifying the set of road segments allowed for such use. Alternatively, one can induce carriers into using the safest links of the network through a toll policy. In this paper, we contrast both approaches, the latter being more flexible and easier from the computational point of view. This analysis is conducted with respect to an objective that takes into account both the risk factors and the cost to the carriers. Finally, we show how the solution of the toll problem can be used to warm start the design problem and consequently help in its numerical resolution. |
|
11h20- 11h45 |
Routing with Branch-Cut-and-Price: Robust and Non-Robust Improvements |
|
Marcus V. Poggi de Aragão, PUC-RIO, Informatics, Rua M. S. Vicente 225, Gávea, Rio de Janeiro, Brazil, 22451-900 Artur A. Pessoa, UFF, Engenharia de Produção, Niteroi, Rio de Janeiro, BRAZIL Eduardo Uchoa, UFF, Engenharia de Produção, Rua Passo da Pátria 156, Niterói, RJ, BRAZIL, 24210-240 This talk presents a branch-cut-and-price algorithm for a wide class of routing problems, including CVRP, ACVRP, COVRP, HFVRP, among others. Next, we discuss how lower bounds can be consistently improved in a robust way, i.e. without shifting the complexity of the pricing subproblem beyond pseudo-polynomial. We also show how non-robust improvements can take place within the algorithm framework avoiding its recurrent combinatorial explosion. Computational results are presented for several routing problems. |