Driver scheduling problem

Driver Scheduling Problem

The Driver Scheduling Problem (DSP) consists of selecting a set of duties for vehicle drivers, for example buses, trains, plane or boat drivers or pilots, for the transportation of passengers or goods. This real complex problem involves several constraints related to labour and company rules and also different evaluation criteria and objectives. Being able to solve efficiently this problem has a great impact in cost and service in Public Transportation Companies . There are a huge number of different rules that a feasible duty should verify like, for example: • Minimum and maximum stretch duration; • Minimum and maximum break duration; • Minimum and maximum work duration; • Minimum and maximum total duration; • Maximum extra work duration; • Maximum number of vehicle changes; • Minimum driving duration of a particular vehicle. The Operations Research area makes a great contribution to solve this problem by proposing optimization models and algorithm that lead to an efficient system to solve this problem. One of the most common models proposed to solve the DSP is the Set Covering or Set Partitioning Models (SPP/SCP) . In the SPP model each work piece is cover by only one duty. In SCP model it is possible to have more that one duty covering each work piece. In the SPP/SCP models there is a set of work pieces or rows that needs to be covered and a set of previous defined feasible duties or columns that covers specific work pieces. The DSP resolution, based on this two models, is the selection of the feasible duties that guarantee that there is one (SPP) or more (SCP) duties covering each work piece minimizing the total cost of the final schedule.