The traditional crew-scheduling problem is solved with a new bin-packing approach in polynomial time. On the basis of extensive research from the past 40 years, an algorithm that has been proven to be the most efficient for solving most bin-packing problems is selected and modified for application in the crew-scheduling problem. A modified best-fit-decreasing algorithm is proposed and discussed. A case study is conducted with the proposed algorithm and the results are discussed.
Get full access to this article
View all access options for this article.
References
1.
HartleyT.A Glossary of Terms in Bus and Crew Scheduling. In Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling: Proceedings of the Second International Workshop on Computer-Aided Scheduling of Public Transport (WrenA., ed.), Leeds, United Kingdom, 1981.
2.
DesaulniersG., DesrosiersJ., DumasY., MarcS., RiouxB., SolomonM., and SoumisF.Crew Pairing at Air France. European Journal of Operational Research, Vol. 97, 1997, pp. 245–259.
3.
CordeauJ., StojkovidG., SoumisF., and DesrosiersJ.Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling.GERAD, Ecole Polytechnique de Montreal, Montreal, Quebec, Canada, 2000.
4.
KroonL. G., and FischettiM.Crew Scheduling for Netherlands Railways, Destination: Customer. In Computer-Aided Scheduling of Public Transport (VossS., and DadunaJ. R., eds.), Springer, Berlin, 2001, pp. 181–201.
5.
AbbinkE., FischettiM., KroonL., TimmerG., and VromansM.Reinventing Crew Scheduling at Netherlands Railways. Interfaces, Vol. 35, 2005, pp. 393–401.
6.
BodinL. D., GoldenB., AssadA., and BallM. O.Routing and Scheduling of Vehicles and Crews: The State of the Art. Computers and Operations Research, Vol. 10, 1983, pp. 63–211.
7.
WrenA., and RousseauJ. M.Bus Driver Scheduling: An Overview. In Computer-Aided Transit Scheduling (DadunaJ. R., BrancoI., and PaixaoJ. M. P., eds.), Springer-Verlag, Berlin, 1995, pp. 173–187.
8.
CaviqueL., RegoC., and ThemidoI.Subgraph Ejection Chains and Tabu Search for the Crew Scheduling Problem. Journal of the Operational Research Society, Vol. 50, 1999, pp. 608–616.
9.
BlaisJ. Y., and RousseauJ. M.Overview of HASTUS Current and Future Versions. Proc. Fourth International Workshop on Computer-Aided Scheduling of Public Transport, Hamburg, Germany, 1987.
10.
BallM. O., BodinL., and DialR.A Matching Based Heuristic for Scheduling Mass Transit Crews and Vehicles. Transportation Science, Vol. 17, No. 1, 1983.
11.
MitraG., and Darby-DowmanK.CRU-SCHED: A Computer-Based Bus Crew Scheduling System Using Integer Programming. In Computer Scheduling of Public Transport, Vol. 2 (RousseauJ. M., ed.), 1985, pp. 223–232.
12.
DesrochersM., and SoumisF.A Column Generation Approach to the Urban Transit Crew Scheduling Problem. Transportation Science, Vol. 23, 1989, pp. 1–13.
13.
BeasleyJ. E., and CaoB.A Tree Search Algorithm for the Crew Scheduling Problem. European Journal of Operational Research, Vol. 94, 1996, pp. 517–526.
14.
HuismanD., FrelingR., AlbertP., and WagelmansM.Multiple-Depot Integrated Vehicle and Crew Scheduling. Transportation Science, Vol. 39, No. 4, 2005, pp. 491–502.
15.
BanihashemiM., and HaghaniA.A New Model for the Mass Transit Crew Scheduling Problem. In Computer-Aided Scheduling of Public Transport: Lecture Notes in Economics and Mathematical Systems, Vol. 505 (VossS., and DadunaJ. R., eds.), Springer-Verlag, Berlin, 2001, pp. 1–15.
16.
PaixaoJ. M. P.Transit Crew Scheduling on a Personal Workstation. Operational Research, Vol. 90, 1990, pp. 421–432.
17.
ClementR., and WrenA.Greedy Genetic Algorithms, Optimizing Mutations and Bus Driver Scheduling. In Computer-Aided Transit Scheduling: Lecture Notes in Economics and Mathematical Systems, Vol. 430 (DadunaJ. R., BrancoI., and PaixaoJ. M. P., eds.), Springer-Verlag, Berlin, 1995, pp. 213–235.
18.
LiJ., and KwanR. S. K.A Fuzzy Genetic Algorithm for Driver Scheduling. European Journal of Operational Research, Vol. 147, 2003, pp. 334–344.
19.
Darby-DowmanK., JachnikJ. K., LewisR. L., and MitraG.Integrated Decision Support Systems for Urban Transport Scheduling: Discussion of Implementation and Experience. In Computer-Aided Transit Scheduling: Proceedings of the Fourth International Workshop (DadunaJ. R., and WrenA., eds.), Springer Verlag, Berlin, 1988, pp. 226–239.
20.
GaffiA., and NonatoM.An Integrated Approach to Extra-Urban Crew and Vehicle Scheduling. In Computer-Aided Transit Scheduling (WilsonN. H. M., ed.), Springer-Verlag, Berlin, 1999, pp. 103–128.
21.
HaaseK., DesaulniersG., and DesrosiersJ.Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems. Transportation Science, Vol. 35, 2001, pp. 286–303.
22.
FrelingR., WagelmansA. P. M., and PaixaoJ. M. P.An Overview of Models and Techniques for Integrating Vehicle and Crew Scheduling. In Computer-Aided Transit Scheduling (WilsonN. H. M., ed.), Springer-Verlag, Berlin, 1999, pp. 441–460.
23.
FrelingR., HuismanD., and WagelmansA. P. M.Models and Algorithms for Integration of Vehicle and Crew Scheduling. Journal of Scheduling, Vol. 6, 2003, pp. 63–85.
24.
CoffmanE. G. (ed.). Computer and Job-Shop Scheduling Theory.John Wiley and Sons, New York, 1976.
25.
CoffmanE. G., GareyM. R., and JohnsonD. S.Approximation Algorithms for Bin Packing: A Survey. In Approximation Algorithms for NP-Hard Problems (HochbaumD., ed.), PWS Publishing, Boston, 1996, pp. 46–93.
26.
JohnsonD. S., DemersA., UllmanJ. D., GareyM. R., and GrahamR. L.Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM Journal on Computing, Vol. 3, 1974, pp. 299–326.
27.
PineR., NiemeyerJ., and ChisholmR.TCRP Report 30: Transit Scheduling: Basic and Advanced Manuals, TRB, National Research Council, Washington, D.C., 1998.
28.
FischettiM., MartelloS., and TothP.The Fixed Job Schedule Problem with Working-Time Constraints. Operations Research, Vol. 37, 1989, pp. 395–403.
