Retour

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.


Retour