3 Presentations

• 
  10:30 AM - 10:55 AM

  Clustering Methods for Vehicle Routing Problems

  • Mona Hamid, presenter, University of Edinburgh
  • Jamal Ouenniche, University of Edinburgh

  VRP is a core routing problem in logistics. Both optimal and heuristic solution methodologies have been proposed to address it. Somehow the success of generic solution frameworks such as metaheuristics has led to less research on the design of problem specific heuristics – whether construction heuristics or decomposition heuristics. For some problems, however, metaheuristics could be very time consuming. In this research, we show that Cluster First-Route Second Decomposition Procedures could deliver high quality solutions much faster than metaheuristics – if designed properly

• 
  10:55 AM - 11:20 AM

  Un algorithme de type séparation locale pour le problème de tournées de véhicules avec demandes stochastiques

  • Sahbi Khtatfa, presenter, UQAM

  Nous proposons une métaheuristique pour résoudre le problème de tournées de véhicules avec demandes stochastiques. Cet algorithme applique des stratégies de diversification et d'intensification, fondées sur les principes de la séparation locale, de façon à résoudre le problème considéré. Les sous-problèmes traités par l'algorithme sont résolus de façon exacte en utilisant la méthode L-Shaped.

• 
  11:20 AM - 11:45 AM

  Branch-Cut-and-Price for the Pickup and Delivery Problem with Time Windows and LIFO Loading

  • Marilène Cherkesly, presenter, GERAD - Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Gilbert Laporte, HEC Montréal

  In this presentation, we focus on the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading (PDPTWL). LIFO loading ensures that no handling is required while unloading objects from the vehicle: a linear stack loading structure is assured and an object can only be delivered if it is the one closest to the door. To solve this problem, we propose three exact branch-cut-and-price algorithms. The first algorithm incorporates the LIFO constraints in the master problem. The second algorithm handles the LIFO constraints directly in the shortest path subproblem. To solve it, a dynamic programming algorithm relying on an ad hoc dominance criterion is developed. The third algorithm is a hybrid between the first two methods. We adapt known valid inequalities to the PDPTWL and study the impact of different path relaxations on the total computation time. Computational results will be presented.