Tuesday 28
N. Zufferey
› 15:10 - 15:30 (20min)
Solving Crew Scheduling Problems with Metaheuristics : A Comparative Study
Pierre Delisle  1, *@  , Audrey Delévacq  1@  , Édith Naudin  2@  , Bertrand Le Cun  3@  
1 : Centre de Recherche en Sciences et Technologies de l'Information et de la Communication  (CRESTIC)  -  Website
Université de Reims - Champagne Ardenne
UFR Sciences Exactes et Naturelles Moulin de la Housse BP 1039 51687 Reims CEDEX 2 FRANCE -  France
2 : EURODECISION  -  Website
9A rue de la Porte de Buc - 78000 Versailles - FRANCE -  France
3 : Parallélisme, Réseaux, Systèmes d'information, Modélisation  (PRISM)  -  Website
CNRS : UMR8144, Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)
45 avenue des Etats-Unis Bâtiment Descartes 78035 Versailles CEDEX -  France
* : Corresponding author

Crew Scheduling Problems (CSPs) are frequently found in the transportation industry. They are often formulated as Set Partitioning Problems (SPPs) in which additional industrial constraints can be added, and solved by linear programming methods. As they are highly constrained, metaheuristics often struggle in finding feasible and good solutions to these problems. In fact, either as standalone methods or coupled with linear programming, the design of efficient metaheuristics to solve CSPs is still a challenge. The purpose of this paper is to propose and experimentally compare three adaptations of popular metaheuristics to solve the SPP. The proposed methods, based on Genetic Algorithms, Ant Colony Optimization and Iterated Local Search, are tested on the 55 SPP benchmarks of the OR-Library in a common computing environment. They are meant to serve as a guideline in a greater project aimed as solving real-world CSPs on HPC architectures.

Online user: 1 RSS Feed