Journées de l'optimisation 2007 Optimizations days

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.

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.

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.