3 Presentations

• 
  09:00 AM - 09:25 AM

  A large neighborhood search for multi-job shift scheduling of multi-skilled employees

  • Dalia Attia, presenter, PhD student
  • Francois Soumis, GERAD et Polytechnique
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  Multi-job shift scheduling of multi-skilled employees consists of finding schedules of employees with different skills, to fulfill the demand in employees for multiple jobs. This problem can be modelled and solved as a mathematical mixed integer problem. We propose a fast large neighborhood search to solve the problem. For the LNS destroy procedure, we choose sub-scopes of job-day-employees causing high penalty on the cost function and remove the shift assignment of the employees in the selected sub-scopes. Then the repair procedure re-optimize the selected destroyed sub-scopes with the formal MIP. Preliminary results show good convergence for the metaheuristic.
• 
  09:25 AM - 09:50 AM

  Integral column generation for the set partitioning problems with side constraints

  • Adil Tahir, presenter,
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  We present a new version of integral column generation (ICG) heuristic that combines the integral simplex and column generation to solve set partitioning problems with side constraints and very large number of variables. ICG finds a sequence of integer solutions, with non-increasing cost, leading to high quality solutions in reasonable times. Computational experiments on instances of the airline crew pairing problem involving up to 1700 flights show that ICG clearly outperforms two popular column generation heuristics (the restricted master heuristic and the diving heuristic).
• 
  09:50 AM - 10:15 AM

  Integral column generation for a real-world rich vehicle routing problem : First application, challenges and issues

  • Mayssoun Messaoudi, presenter, Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal
  • Louis-Martin Rousseau, Polytechnique Montréal

  We present a real-life transportation problem arising in a third-party logistics (3PL) actor, who aims to optimize the last-mile delivery. Through this work, we present the first application of the primal-based approach to solve Rich Vehicle Routing Problems, namely the Integral Column Generation (ICG). The computational study, based on real instances reaching 199 customers, compare the ICG algorithm with a well-known column generation based Diving Heuristic (DH).