Public-transit vehicle schedules using a minimum crew-cost approach

• Autorzy: Ceder A.
• Języki publikacji: EN

Abstrakty

EN

Commonly, public transit agencies, with a view toward efficiency, aim at minimizing the number of vehicles in use to meet passenger demand, and therefore at reducing crew cost. This work contributes to achieving these two objectives by proposing the use of two predominant characteristics of public-transit operations planning: (a) different resource requirements between peak and off-peak periods, and (b) working during irregular hours. These characteristics result in split duties (shifts) with unpaid in-between periods. The outcome of this work is an optimal solution for maximizing the unpaid shift periods with the assurance of complying with the minimum number of vehicles attained. The optimization problem utilizes a highly informative graphical technique (deficit function) for finding the least number of vehicles; this enables the construction of vehicle chains (blocks) that take into account maximum unpaid shift periods. The latter consideration is intended to help construct crew schedules at minimum cost. The methodology developed was implemented by two large bus companies and resulted in a significant cost reduction.

Słowa kluczowe

EN

public transportation; vehicle scheduling; crew scheduling; deficit function

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Total Logistic Management
• Rocznik: 2011
• Tom: no. 4
• Strony: 21--42
• Opis fizyczny: Bibliogr. 34 poz., tab., rys.

Twórcy

autor

Ceder A.

• Transportation Research Centre, Dept. of Civil and Environmental Engineering, Faculty of Engineering, University of Auckland, Auckland 1142, New Zealand,

Bibliografia

• [1] Banihashemi, M. and Haghani, A., (2000). Optimization model for large-scale bus transit scheduling problems. Transportation Research Record, 1733, pp. 23–30
• [2] Beasley, J. E. and Cao, E. B., (1996). A tree search algorithm for the crew scheduling problem. European Journal of Operational Research, 94, pp. 517–526
• [3] Beasley, J. E. and Cao, E. B., (1998). A dynamic programming based algorithm for the crew scheduling problem. Computers & Operations Research, 25, pp. 567–582
• [4] Borndorfer, R., Lobel,A., and Weider, S., (2008). A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit. Computer-Aided Systems in Public Transport (M. Hickman, P. Mirchandani, S. Voss, eds). Lecture notes in economics and mathematical systems, Vol. 600, Springer, pp. 3–24
• [5] Carraresi, P., Nonato, M., and Girard, L., (1995). Network models, lagrangean relaxation and subgradients bundle approach in crew scheduling problems. In Computer-aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, 430 (J. R. Daduna, I. Branco, and J. M. P. Paixao, eds.), pp. 188–212, Springer-Verlag
• [6] Ceder, A., (2002) A step function for improving transit operations planning using fixed and variable scheduling, in Transportation and Traffic Theory, M.A.P. Taylor, (ed), pp. 1–21, Elsevier Science
• [7] Ceder, A., (2003). Public transport timetabling and vehicle scheduling. Chapter 2 in Advanced Modeling for Transit Operations and Service Planning (W. Lam and M. Bell, eds.), pp 31–57, Pergamon Imprint, Elsevier Science
• [8] Ceder, A., (2007a). Optimal Single-Route Transit Scheduling. Transportation & Traffic Theory (R. Allsop, M. Bell, B. Heydecker, eds), ISTTT-17, Elsevier Science & Pergamon Pub., pp. 385–405
• [9] Ceder, A., (2007b). Public Transit Planning and Operation: Theory, Modeling and Practice, Elsevier, Butterworth-Heinemann, Oxford, UK, 640 p.
• [10] Ceder, A. and Stern, H.I., (1981). Deficit function bus scheduling with deadheading trip insertion for fleet size reduction. Transportation Science, 15 (4), pp. 338–363
• [11] Clement, R. and Wren, A., (1995). Greedy genetic algorithms, optimizing mutations and bus driver scheduling. In Computer-Aided Transit Scheduling. LectureNotes in Economics and Mathematical Systems, 430 (J. R. Daduna, I. Branco, and J. M. P. Paixao, eds.), pp. 213–235, Springer-Verlag
• [12] Fores, S., Proll, L., and Wren, A., (1999). An improved ILP system for driver scheduling. In Computer-Aided Transit Scheduling. LectureNotes in Economics and Mathematical Systems, 471 (N. H. M.Wilson, ed.), pp. 43–61, Springer-Verlag
• [13] Fores, S., Proll, L., and Wren, A., (2001). Experiences with a flexible driver scheduler. In Computer-Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems, 505 (S. Voss and J. R. Daduna, eds.), pp. 137–152, Springer-Verlag
• [14] Freling, R., Huisman, D., and Wagelmans, A. P. M., (2001). Applying an integrated approach to vehicle and crew scheduling in practice. In Computer-Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems, 505 (S. Voss and J. R. Daduna, eds.), pp. 73–90, Springer-Verlag.
• [15] Gertsbach, I. and Gurevich, Y., (1977). Constructing an optimal fleet for transportation schedule. Transportation Science, 11, pp. 20–36
• [16] Gintner, V., Kliewer, N. and Suhl, L., (2008). A Crew Scheduling Approach for Public Transit Enhanced with Aspects from Vehicle Scheduling. Computer-Aided Systems in Public Transport (M. Hickman, P. Mirchandani, S. Voss, eds). Lecture notes in economics and mathematical systems, Vol. 600, Springer, pp. 25–42
• [17] Haase, K., Desaulniers, G., and Desrosiers, J., (2001). Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Science, 35(3), pp. 286–303
• [18] Haghani, A. and Banihashemo, M., (2002). Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints. Transportation Research, 36A, pp. 309–333
• [19] Haghani, A., Banihashemi, M., and Chiang, K. H., (2003). A comparative analysis of bus transit vehicle scheduling models. Transportation Research, 37B, pp. 301–322
• [20] Huisman, D., Freling, R., andWagelmans, A.O.M., (2004). A robust solution approach to the dynamic vehicle scheduling problem. Transportation Science, 38 (4), pp. 447–458
• [21] Huisman, D., Freling, R., and Wagelmans, A. P. M., (2005). Models and algorithms for integration of vehicle and crew scheduling. Transportation Science, 39, pp. 491–502
• [22] Kroon, L. and Fischetti M., (2001). Crew scheduling for Netherlands railways “destination: customer.” In Computer-Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems, 505 (S. Voss and J. R. Daduna, eds.), pp. 181–201, Springer- Verlag
• [23] Kwan, A. S. K., Kwan R. S. K., and Wren, A., (1999). Driver scheduling using genetic algorithms with embedded combinatorial traits. In Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, 471 (N. H. M. Wilson, ed.), pp. 81–102, Springer-Verlag
• [24] Kwan R.S.K and Kwan A.S.K., (2007). Effective Search Space Control for Large and/or Complex Driver Scheduling Problems. Annals of Operations Research 155, pp. 417–435
• [25] Laplagne, I.,Kwan R.S.K., andKwanA.S.K., (2009). Critical TimeWindow Train Driver Relief Opportunities. Public Transport planning and Operations 1(1), pp. 73–85
• [26] Lobel, A., (1998), Vehicle scheduling in public transit and lagrangean pricing. Management Science, 44 (12), pp. 1637–1649
• [27] Lobel, A., (1999). Solving large-scale multiple-depot vehicle scheduling problems. In Computer- Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, 471 (N. H. M.Wilson, ed.), pp. 193–220, Springer-Verlag
• [28] Lourenco, H. R., Paixao, J. P., and Portugal, R., (2001). Multiobjective metaheuristics for the bus-driver scheduling problem, Transportation Science, 35(3), pp. 331–343
• [29] Mesquita, M. and Paixao, J.M.P., (1999). Exact algorithms for the multi-depot vehicle scheduling problem based on multicommodity network flow type formulations. In Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, 471 (N. H. M. Wilson, ed.), pp. 221–243, Springer-Verlag
• [30] Mesquita, M., Paias, A., and Respicio, A., (2009). Branching Approaches for Integrated Vehicle and Crew Scheduling. Public Transport Planning and Operations 1(1), pp. 21–37
• [31] Mingozzi, A., Boschetti, M. A., Ricciardelli, S, and Bianco, L., (1999). A set partitioning approach to the crew scheduling problem. Operations Research, 47, pp. 873–888
• [32] Paias, A. and Paixao, J.M.P., (1993). State space relaxation for set-covering problems related to bus driver scheduling. European Journal of Operational Research, 71, pp. 303–316
• [33] Shen, Y. and R. S. K. Kwan., (2001). Tabu search for driver scheduling. In Computer-Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems, 505 (S. Voss and J. R. Daduna, eds.), pp. 121–135, Springer-Verlag
• [34] Stern, H.I. and Ceder, A., (1983). An improved lower bound to the minimum fleet size problem. Transportation Science, 17 (4), pp. 471–477