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 (assignments) for the drivers or pilots of vehicles (e.g., buses, trains, boats, or planes) involved in the transportation of passengers or goods,[1][2] within the constraints of various legislative and logistical criteria.
Criteria and modelling
editThis very complex problem involves several constraints related to labour and company rules and also different evaluation criteria and objectives. Being able to solve this problem efficiently can have a great impact on costs and quality of service for public transportation companies.[3] There is a large number of different rules that a feasible duty might be required to satisfy, such as
- 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 provided optimization models and algorithms that lead to efficient solutions for this problem. Among the most common models proposed to solve the DSP are the Set Covering and Set Partitioning Models (SPP/SCP).[4][5] In the SPP model, each work piece (task) is covered by only one duty. In the SCP model, it is possible to have more than one duty covering a given work piece. In both models, the set of work pieces that needs to be covered is laid out in rows, and the set of previously defined feasible duties available for covering specific work pieces is arranged in columns. The DSP resolution, based on either of these models, is the selection of the set of feasible duties that guarantees that there is one (SPP) or more (SCP) duties covering each work piece while minimizing the total cost of the final schedule.
See also
editReferences
edit- ^ 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; Martin Grötschel; Marc E. Pfetsch (2006). "Public transport to the fORe". OR/MS Today. 33 (2): 30–40.
- ^ Lourenço, H.R.; Paixão, J.P.; Portugal, R. (2009). "Driver Scheduling Problem Modelling". Public Transport: Planning and Operations. 1 (2): 103–120. doi:10.1007/s12469-008-0007-0. hdl:10230/303.
- ^ Lourenço, H.R.; Paixão, J.P.; Portugal, R. (2001). "The crew-scheduling module in the GIST system". Economic Working Papers Series, Department of Economics and Business, Universitat Pompeu Fabra. 547.