Optimization Days 2017

HEC Montréal, May 8-10, 2017

1st Canadian Healthcare Optimization Workshop (CHOW)

HEC Montréal, May 10-11, 2017



HEC Montréal, 8 — 11 May 2017

Schedule Authors My Schedule

MB6 Problèmes de transport multi-attributs / Multi-attribute vehicle routing problems

May 8, 2017 10:30 AM – 12:10 PM

Location: CPA du Québec

Chaired by Luis Gouveia

4 Presentations

  • 10:30 AM - 10:55 AM

    A Matheuristic for Assembly, Production and Inventory Routing Problems

    • Masoud Chitsaz, presenter, Phd student @ KULeuven and HEC
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
    • Raf Jans, HEC Montréal

    We introduce and formulate the assembly routing problem (ARP). We propose a three-phase matheuristic to solve not only the the ARP, but also the PRP and the IRP. We obtained 818 new best known solutions out of 2,628 standard IRP and PRP test instances.

  • 10:55 AM - 11:20 AM

    A variable MIP neighborhood descent algorithm for an ATM inventory routing problem

    • Homero Larrain, presenter, PUC
    • Leandro C. Coelho, Université Laval

    We introduce the variable MIP neighborhood descent algorithm, a general-purpose algorithm which takes advantage of the MIP formulation of a problem to speed up the solution of a branch-and-cut algorithm. We test this algorithm on an inventory routing problem arising when replenishing a network of ATMs.

  • 11:20 AM - 11:45 AM

    Multiple Depot Vehicle Scheduling Problem with controlled trip shifting

    • Lucie Desfontaines, presenter, Polytechnique Montréal
    • Guy Desaulniers, GERAD and Polytechnique Montreal

    We are interested in improving the classical Vehicle Scheduling problem with multiple depots by allowing a slight modification of departure schedules. By shifting some trips one can indeed expect to cover all trips with fewer vehicles and/or less expensive transit connexions.
    However, reducing operational costs this way should not be detrimental to the overall quality of departure schedules. Therefore our model controls these three criterions: the number of shifted trips, the interval between two same-line consecutive trips and the quality of passengers connexions.
    In order to solve this problem we propose two column generation based algorithms: an exact one and a heuristic one. We also apply several graph reductions which allow solving larger instances.
    Tests on real urban data show that slightly shifting some trips can yield to a significant reduction in the number of vehicles used.

  • 11:45 AM - 12:10 PM

    New path elimination constraints for multi-depot routing problems

    • Luis Gouveia, presenter, University of Lisbon
    • Tolga Bektas, University of Southampton
    • Daniel Santos, DEIO, Faculdade de Ciências, Universidade de Lisboa, CMAFCIO

    Multi-depot routing problems arise in distribution logistics where a set of vehicles based at several depots are used to serve a number of clients. Most variants of this problem have the basic requirement that the route of each vehicle starts and ends at the same depot. This talk describes new inequalities, namely multi-cut constraints (MCC), for multi-depot routing problems that enforce this requirement. The MCCs are exponential in size, and are equivalent to a compact three-index formulation for the problem in terms of the associated linear programming relaxations. In the talk we describe how a generalization of the MCCs can be obtained, in a similar manner, by using a stronger version of the three-index formulation. The connection between the compact and the exponential formulations implies a separation procedure based on max-flow/min-cut computations, which has reduced complexity in comparison with a previously known set of constraints described for the same purpose. The new inequalities are used in a branch-and-cut algorithm. Computational results with instances with 200 clients and up to 20 depots indicate that the algorithm is able to optimally solve the instances generally within a few hundred seconds of computation time.