Driver scheduling problem
 | This article contains no links to other Wikipedia articles. (May 2013) |
 | This article may require copy editing for flow, punctuation. (May 2013) |
The driver scheduling problem (DSP) is type of problem in operations research and theoretical computer science.
The 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.[1][2]
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[3] . 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.
Operations research has proposed optimization models and algorithms that lead to an efficient solutions for this problem. One of the most common models proposed to solve the DSP is the Set Covering or Set Partitioning Models (SPP/SCP)[4] [5] . 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.
References
- ^ Voß, Stefan; Daduna, Joachim R. (2001). Computer Aided Scheduling of Public Transport. Springer. pp. 122–. ISBN 9783540422433. Retrieved 22 May 2013.
- ^ Salvendy, Gavriel (2001-05-25). Handbook of Industrial Engineering: Technology and Operations Management. John Wiley & Sons. pp. 813–. ISBN 9780471330578. Retrieved 22 May 2013.
- ^ Borndörfer, Ralf (2006). "Public transport to the fORe". OR/MS Today. 33 (2): 30–40.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ Lourenço, H.R. (2009). "Driver Scheduling Problem Modelling". Public Transport: Planning and Operations. 1 (2): 103–120. doi:10.1007/s12469-008-0007-0.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ Lourenço, H.R. (2001). "The crew-scheduling module in the GIST system". Economic Working Papers Series, Department of Economics and Business, Universitat Pompeu Fabra. 547.
{{cite journal}}: Unknown parameter|coauthors=ignored (|author=suggested) (help)
 | This article needs additional or more specific categories. (May 2013) |