4 présentations

• 
  10h30 - 10h55

  A Matheuristic for Assembly, Production and Inventory Routing Problems

  • Masoud Chitsaz, prés., 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.

• 
  10h55 - 11h20

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

  • Homero Larrain, prés., 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.

• 
  11h20 - 11h45

  Multiple Depot Vehicle Scheduling Problem with controlled trip shifting

  • Lucie Desfontaines, prés., Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  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.

• 
  11h45 - 12h10

  New path elimination constraints for multi-depot routing problems

  • Luis Gouveia, prés., 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.