4 présentations

• 
  15h30 - 15h55

  A column-generation based model to pickup and delivery problem with transfers

  • Cristiam Gil, prés., Universidad de Chile

  Exact methods in the PDP-T literature were only employed for solving small instances with larges computational times: the best is no more than 75 requests and 4 transfer points running up to 1 CPU time hours (an imposed limit) with average gaps of 33.84% (Masson et al., 2014), showing an existing gap in real applications. Some recent promising works have improved gaps in reasonable computational times. Cortes et al. (2010) proved the computational benefits of implementing a branch-and-cut algorithm (based on Benders decomposition) to solve PDP-T problems. They reported savings of around 90% in CPU time when compared to standard MIP solvers. Ghilas et al. (2017) solves the PDPTW-T, through a Branch-and-Price methodology mainly consider for the PDPTW with scheduled lines, with up to 40 requests on the considered instances. Gschwind (2015) evidenced the effectiveness of column generation approaches for the PDP (with no transfer), solving 91% small and medium size instances and 66% of large size instances to optimality. It could be worth to explore this approach for the problem for the problem with transfers. Currently, we are developing of cutting-edge solution methods to Pickup and Delivery problem with transfers, specifically methodologies based in Column Generation. The purpose of this work is to show our ongoing progress in this problem: to propose a three and a two index formulations including precedence, route synchronization and capacity constraints, which present difficulties deal.

• 
  15h55 - 16h20

  Selection step impact on the genetic algorithm for the bi-objective vehicle routing problem with time windows

  • Meriem Akli, prés., USTHB

  This paper proposes a Genetic Algorithms for the Vehicle Routing Problem with Time Windows, where both total length traveled by the vehicles and the number of vehicles are minimized. The main topic of this work is to evaluate the selection step impact and to detect the appropriate procedure of selection to balance between intensification and diversification.

• 
  16h20 - 16h45

  Optimizing drone routing for rapid needs assessment in post sudden-onset disasters

  • Sean Grogan, prés., Polytechnique Montreal
  • Robert Pellerin, École Polytechnique de Montréal
  • Michel Gamache, Polytechnique Montréal

  In the aftermath of a sudden-onset disaster (earthquakes, etc.), rescuers often are tasked in assessing the needs of an affected population and locating those in need of aid. Using drones equipped with wireless sensors, we use a self-organizing map and simulated annealing to optimize the flight operations of the drones.

• 
  16h45 - 17h10

  Two-arc sequence variable fixing in branch-price-and-cut algorithms for vehicle routing

  • Guy Desaulniers, prés., GERAD - Polytechnique Montréal
  • Timo Gschwind, Johannes Gutenberg Universität Mainz
  • Stefan Irnich, Johannes Gutenberg Universität Mainz
  • Claudio Contardo, GERAD - ESG UQÀM

  In branch-price-and-cut algorithms for vehicle routing, variable fixing based on path reduced cost is a well-known speedup technique that allows to eliminate arcs after solving a linear relaxation. In this talk, we extend this technique to also eliminate sequences of two arcs. This requires modifying the labeling algorithm used to solve the pricing problem. Computational results on the vehicle routing problem with time windows will be reported.