4 Presentations

• 
  03:30 PM - 03:55 PM

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

  • Iman Dayarian, presenter, 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.

• 
  03:55 PM - 04:20 PM

  A Modeling Language for Vehicle Routing Problem Variants

  • Tuukka Puranen, presenter, 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.

• 
  04:20 PM - 04:45 PM

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

  • Charles Gauvin, presenter, 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.

• 
  04:45 PM - 05:10 PM

  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, presenter, 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.