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

2011 Optimization Days

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

Schedule Authors My Schedule

MA3 Tournées de véhicules I / Vehicle Routing I

May 2, 2011 10:30 AM – 12:10 PM

Location: Banque CIBC

Chaired by Jean-François Côté

4 Presentations

  • 10:30 AM - 10:55 AM

    A Column Generation Approach to the Multi-Vehicle Covering Tour Problem

    • Nicolas Jozefowiez, presenter, LAAS-CNRS

    This presentation is about the solution of the multi-vehicle covering tour problem by means of a column generation approach. While the master problem is a simple set covering problem, the subproblem is more complex. A model and a branch-and-cut algorithm for the latter will be presented.

  • 10:55 AM - 11:20 AM

    The Machine Learning and Traveling Repairman Problem

    • Theja Tulabandhula, presenter, Massachusetts Institute of Technology
    • Cynthia Rudin, Massachusetts Institute of Technology
    • Patrick Jaillet, Massachusetts Institute of Technology

    The Machine Learning and Traveling Repairman Problem is to determine a route to repair nodes on a graph. The repair crew aims to minimize the cost of failures at the nodes, while the failure probabilities must also be estimated/learned. We introduce several formulations for this new class of problems.

  • 11:20 AM - 11:45 AM

    A Branch-And-Cut Algorithm for the Pickup and Delivery Traveling Salesman Problem with Multiple Stacks

    • Jean-François Côté, presenter, Université de Montréal
    • Michel Gendreau, Polytechnique Montréal
    • Jean-Yves Potvin, Université de Montréal

    We present a branch-and-cut algorithm for solving a pickup and delivery problem for a single vehicle with multiple capacity-constrained LIFO stacks. Results are reported on our own test instances as well as on benchmark instances for some special cases of the problem.

  • 11:45 AM - 12:10 PM

    A Branch-and-Price-and-Cut Method for a Maritime Pickup and Delivery Problem with Time Windows and Split Loads

    • Magnus Stålhane, presenter, Norwegian University of Science and Technology
    • Henrik Andersson, Norwegian University of Science and Technology
    • Marielle Christiansen, Norwegian University of Science and Technology
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
    • Guy Desaulniers, GERAD - Polytechnique Montréal

    We present a branch-and-price-and-cut method for a maritime pickup and delivery problem with time windows and split loads. The fleet is heterogeneous with each ship having a different load capacity and cost structure. Each cargo may be transported by one or several ships. Computational results will be presented.