A multi-level graph coloring approach for the Bus driver´s timetables: A real case study of the public transport of Sfax

Scheduling and human resources management have an important role in the productivity and competitiveness of a company. Timetabling is an essential task in such filed to compete in many sectors. The conventional method which is traditionally done manually for solving timetabling problem is often inaccurate. This paper move toward automated software to solve the timetabling problem for the SORETRAS Company, which is a public transport company in Sfax city, TUNISIA, to affect all their travel services into groups, called also classes. Each group represents the daily work for a driver. A graph coloring approach is presented. Then, a heuristic based this approach is applied to solve the problem. This approach replaces the intuitive procedure currently used by the SORETRAS decision makers. This procedure consists in solving manually this relevant problem. Hence, with the proposed procedure, the obtained groups were greatly improved in quality of service compared to the current practice.