The Study of Mass Rapid Transit Drivers Scheduling Problems A Case Study of Taipei MRT Company Abstract This paper proposes an algorithm to improve the efficiency for solving the drivers scheduling problem of the Taipei MRT company. We formulate this problem as a set-partitioning problem. A three phases algorithm, column generation, branch-and-bound, and heuristic local search, is then developed for solving this model. We use the real cases of the Taipei MRT company as the numerical examples. The results show that our algorithm could get better solutions with higher operational feasibility than the current one does.
)
r R c r x r a = N i ir x r r R r r R x = K R r x = 0, r R r 4
5
) r R c r x r a = N i ir x r r R x = 0, r R r π k 6
π N i= N a ri π c r R i= π 0 i i i r c r a ri π i < 0 c r a ri π i 0 N i= N i= r R (Node) 7
8-5 7:8 8:0-6 8:0 8:4-5 0 59-9 9:5 0-6 59 4-6 4-4 7:7 7:50-4 7:0 7:40 4-7:06 7:9-5 7:50 8:5-5 7:40 8: 4-7:9 8:0-9 05 055-9 9:59 0 4-7 007 040-00 9-44 6 4-0 5 4-5 44 44-5 9 40 4-5 408-6 44 457-6 40 49 4-4 408 440
Cost(Node_ID) Dual(Node_ID) time_differ W A Cost( ) Dual( ) time_differ Wa Cost( ) Dual( ) time_differ Wa B 0 0 time_differ Wb 0 0 time_differ Wb C Cost( ) Dual( ) 0 Wc D Cost( ) Dual( ) time_differ Wd 9
0 (over-covering task)
4 ) ( ) ( )
. Appelgren, L. H., A Column Generation Algorithm for a Ship Scheduling Problem, Transportation Science,, pp. 5-68 (969).. Bailey R. N., Garner, K. M., Hobbs M. F., Using Simulate Annealing and Genetic Algorithm to Solve Staff-Scheduling Problems, Asia-Pacific Journal of Operational Research, Vol. 4, No., pp.7-4 (997).. Ball, M., Bodin, L. and Dial, R., A Matching Based Heuristics for Scheduling Mass Transit Crews and Vehicles, Transportation Science,7(), pp.4-(98). 4. Ball, M. O., Magnanti, T. L., Monma, C. L., Nemhauser, G. L. Ch. Time Constrained Routing and Scheduling in Handbooks in Operations Research and Management Science Volume 8Network Routing. 5. Bartholdi, John, J., A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering, Operations Research, 9, pp. 50-50 (98). 6. Chu, C. K. Sydney and Chan C. H. Edmond, Crew Scheduling of Light Rail Transit in Hong KongFrom Modeling to Implementation, Computers and Operations Research, Vol. 5, No., pp. 887-894 (998). 7. Crainic, T. G. and Rouseau, J. The Column Generation Principle and the Airline Crew Scheduling Problem INFOR, Vol. 5, No., pp. 6-5 (987). 8. Dantzig, G. B., and P. Wolfe The Decomposition Algorithm for Linear Programming Operations Research, 8, pp. 0- (960). 9. Desrocheds, Martin and Soumis, Francois, A Column Generation Approach to the Urban Transit Crew Scheduling Problem, Transportation Science, Vol., No., pp. - (989). 0. Desrochers, M., Gilbert, J., Sauve, M., Soumis, F. Crew-OptSubproblem Modeling in a Column Generation Approach to Urban Crew Scheduling in Computer-Aided Transit Scheduling, pp. 95-406. Lecture Notes in Economics and Mathematical System 86. Springer-Verlag, Berlin, 99.. Gilmore, P. C. and Gomory, R. E., A Linear Programming Approach to the Cutting-Stock Problem, Operations Research, Vol. 9, pp. 849-859 (96).. Heurgon, H., Preparing Duty Roster for Bus Routes by Computer, in Preprint Workshop on Automated Technique for Scheduling of Vehicle Operations for Urban Public Transportation Service (975).. Lavoie, S., M. Minoux and E. Odier, A new Approach for Crew Pairing 5
Problems by Column Generation with an Application to Air Transportation European Journal of Operational Research, Vol. 5, pp. 45-58 (998). 4. Lessard, R., Rousseau, J. M. and Dupuis, D., HASTUS IA Mathematical Programming Approach to the Bus Driver Scheduling Problem, in Computer Scheduling of Public TransportUrban Passenger Vehicle and Crew Scheduling, ed. A. Wren. North-Holland, Amsterdam, pp. 55-68, (98). 5. Levine, D. and Argonne, Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling, Computers and Operations Research, Vol., pp. 547-558, 996. 6. Mitra, G. and Darby-Dowman, K, CRU-SHEDA Computer Based Bus Crew Scheduling System Using Integer Programming, in Computer Scheduling of Public Transport, Elsevier, Amsterdam, 985. 7. Rosseau, J. M., Lessard, R. and Blais, J. Y., Enhancements to the HASTUS Crew Scheduling Algorithm, in Computer Scheduling of Public Transport, Vol., ed. J. M. Rousseau. North-Holland, Amsterdam, pp. 95-0 (985). 8. Shepardson, F. and Marsten, R. E., A Lagrangean relaxation Algorithm for the Two Duty Period Scheduling Problem, Management Science,6,pp.74-8 (980). 9. Vance, P. H., Barnhart, C., Johnson, E. L., Nemhauser, G. L., Airline Crew SchedulingA New Formulation and Decomposition Algorithm, Operations Research, Vol. 45, No. (997). 0. Wren, A., Smith, B. M. and Miller, A. J., Complementary Approach to Scheduling, in Computer Scheduling of Public Transport, Elsevier, Amsterdam, 985.., (996).., pp. 7-84 (996). 6