Daily parking of subway vehicles

The problem of daily parking of subway vehicles is a special type of timetabling problems. It consists of assigning to the railroad lines of the depot of the subway system of Tunis the fleet of vehicles, while respecting a set of capacity and precedence constraints. Each vehicle is assigned daily one or more operating indices characterized by their departure and arrival times, and their itineraries. The objective is to minimize the number of scheduled conflicts. Five two-phase methods based on an exact model, on Genetic Algorithms, Tabu Search, Simulated Annealing and Expert Systems are proposed. The results are compared showing the superiority of the Tabu Search and Genetic Algorithm based heuristics and their capability of assigning all the vehicles in most cases.