HEC Montréal, Canada, May 2 - 4, 2011

2011 Optimization Days

HEC Montréal, Canada, 2 — 4 May 2011

Schedule Authors My Schedule

TB5 Conception de réseaux / Network Design

May 3, 2011 01:30 PM – 03:10 PM

Location: Demers Beaulne

Chaired by Bernard Gendron

4 Presentations

  • 01:30 PM - 01:55 PM

    A Cutting-Plane Method for the Capacitated Multicommodity Fixed-Charge Network Design Problem

    • Mathieu Larose, presenter, Université de Montréal - CIRRELT
    • Bernard Gendron, Université de Montréal, CIRRELT

    We propose a cutting-plane method using column generation for the capacitated multicommodity fixed-charge network design Problem. We present computational results on a large set of instances with various characteristics.

  • 01:55 PM - 02:20 PM

    Planning Multimodal Transportation

    • Jonathan Bellemare, presenter, Université de Montréal
    • Jacques Ferland, Université de Montreal
    • Bernard Gendron, Université de Montréal, CIRRELT

    We present a bimodal freight transportation case from the forest industry. We aim to optimize the overall costs of transporting wood products through trucks and railways. Given known train schedules, weekly time-space networks are introduced for optimization on a monthly basis, giving rise to large-scale service network design models.

  • 02:20 PM - 02:45 PM

    A Path Based Model for a Green Liner Shipping Network Design Problem

    • Berit Løfstedt, presenter, Technical University of Denmark
    • Christian E. M. Plum, Technical University of Denmark
    • Mads Kehlet Jepsen, DTU Management, Technical University of Denmark
    • David Pisinger, Technical University of Denmark
    • Mikkel M. Sigurd, Maersk Line

    Liner shipping networks are the backbone of international trade providing low transportation cost, which is a major driver of globalization. These networks are under constant pressure to deliver capacity, cost effectiveness and environmentally conscious transport solutions.
    Previous models of liner shipping network design are based on a two-tier structure with an IP selecting routes for vessels and an LP flowing the cargo as a multi commodity flow problem. We propose a new path based MIP model for the Liner shipping Network Design Problem where each route is coupled with a cargo loading pattern. The objective of the model is to minimize the cost of vessels and their fuel consumption facilitating a green network.
    The model may be solved using delayed column generation. The sub-problems have similar structure to Vehicle Routing Problems and we explore a dynamic programming algorithm similar to a resource constrained shortest path enabling non simple cycles as routes and transshipment of cargo between routes. The proposed model additionally reduces problem size using a novel aggregation of demands.

  • 02:45 PM - 03:10 PM

    Lower Bounds for the Two-Level Uncapacitated Facility Location Problem

    • Paul-Virak Khuong, presenter, Université de Montréal - CIRRELT
    • Bernard Gendron, Université de Montréal, CIRRELT
    • Frédéric Semet, École Centrale de Lille

    The two-level uncapacitated facility location problem is an extension of the uncapacitated facility location problem in which the set of depots is replaced with a set of major depots and another set of minor depots (located between major depots and clients). We consider a variant of this problem in which an additional constraint ensures that each minor depot can be connected to at most one major depot. We describe the binary programming formulation and specialized lower-bounding methods we developed in order to solve instances with hundreds of potential locations and of clients.