Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

MD2 Tournées de véhicules 2 / Vehicle Routing 2

7 mai 2012 15h30 – 17h10

Salle: KPMG

Présidée par Walter Rei

4 présentations

  • 15h30 - 15h55

    A Branch and Price Approach for a Multi-Attribute Vehicle Routing Problem

    • Iman Dayarian, prés., Université de Montréal
    • Teodor Gabriel Crainic, Université du Québec à Montréal
    • Michel Gendreau, Polytechnique Montréal
    • Walter Rei, Université du Québec à Montréal

    We address a new variant of deterministic multi-attribute vehicle routing problem derived from a real-life milk collection system. This problem is characterized by the presence of a heterogeneous fixed fleet of vehicles, multiple depots and several resource constraints. To tackle the problem, a branch-and-price based algorithm is proposed.

  • 15h55 - 16h20

    A Modeling Language for Vehicle Routing Problem Variants

    • Tuukka Puranen, prés., University of Jyväskylä

    Many logistic problems are formulated as variants of the vehicle routing problem. The ability to express these in a unified way can make the implementation of optimization systems easier. We developed a language for this purpose. In this talk, we present the language, and discuss the advantages and disadvantages of the approach.

  • 16h20 - 16h45

    An Exact "Branch-and-cut-and-price" Algorithm for the Resolution of the Vehicle Routing Problem with Stochastic Demands

    • Charles Gauvin, prés., Polytechnique Montréal

    This presentation covers an exact “branch-and-cut-and-price” resolution method for the VRPSD. We begin by presenting the formulation of Lysgaard and Christiansen (2007). We then compare different strategies used to speed up the resolution process. We namely propose a new dominance criteria used during the resolution of the shortest path elementary sub problem. In addition, we study the impact of ng-route relaxations together with a tabou search algorithm, bidirectional label setting algorithm and use of cutting planes on the total resolution time. Finally, we compare different branching strategies.

  • 16h45 - 17h10

    A Cooperative Parallel Metaheuristic for the Capacitated Vehicle Routing Problem

    • Jiayong Jin, Molde University College, Norway
    • Teodor Gabriel Crainic, Université du Québec à Montréal
    • Arne Løkketangen, prés., Molde University College

    We present a parallel metaheuristic with a solution similarity clustering based guidance mechanism for solving the capacitated vehicle routing problem. Cooperation is by exchanging best found solutions through a solution pool. Solution cluster information is used to guide intensification and diversification of the search. Computational experiments yield highly competitive results.