Driver scheduling problem

The driver scheduling problem is a class of problem studied in operations research and theoretical computer science that asks how to assemble a set of duties, meaning individual work assignments, for the drivers or pilots of vehicles such as buses, trains, boats or planes that carry passengers or goods. A solution must select duties so that, taken together, they cover every piece of transportation work that needs to be performed, while respecting the legislative and logistical constraints that govern crew scheduling, such as maximum working time, required break durations, and rules about where and how a driver may change from one vehicle or route to another. Because the number of ways duties can be combined grows very quickly with the size of a transport network, exact enumeration is impractical for any realistic system, so solutions typically formulate the problem as a mathematical program, commonly a set covering or set partitioning model, and use algorithms built for those models to select a feasible, low cost combination of duties from a large pool of candidate duties.