Thursday 30
Logistics and transportation
A. Sbihi
› 9:40 - 10:00 (20min)
Decomposition techniques for parking vehicles in depots
Eric D. Taillard  1@  , Thé-Van Luong@
1 : Haute Ecole d'Ingénierie et de Gestion du Canton de Vaud  (HEIG-VD)  -  Website
Rte de Cheseaux 1, CP CH-1401 Yverdon-les-Bains -  Switzerland

This article presents a methodology for decomposing a real life problem of parking the vehicles of a large public transportation company in depots. While the problem looks like a bin packing at first glance, it is much more complex since numerous operational constraints must be taken into account.

For being able to produce acceptable solutions in limited computational time, the problem has been decomposed in several steps. First, the vehicles are clustered by type, independently from their departure hour and placed on lanes, which are composed of vehicles of the same type, if possible. Then a departure hour is assigned to each vehicle, with respect to the timetable and precedence constraints.

Finally, the solution is post-optimized to create blocks of lanes with the same vehicle type, to maximize the number of lanes without vehicles and to take into consideration other specific constraints.

Each of these steps are solved exactly, when possible, or with a local search based meta-heuristic. The software has been used daily and successfully for 1 year. It has simplified a lot the work of the responsible of parking the vehicles in the depots.

Online user: 1 RSS Feed