簡易檢索 / 詳目顯示

回結果列表
研究生： 許靖嵐
Hsu, Ching-Lan
論文名稱： 以變數產生法求解公車司機員排班問題之研究
A Column Generation Algorithm for the Bus Driver Scheduling Problem
指導教授： 林東盈
Lin, Dung-Ying
學位類別： 碩士
Master
系所名稱： 管理學院 - 交通管理科學系
Department of Transportation and Communication Management Science
論文出版年： 2016
畢業學年度： 104
語文別： 英文
論文頁數： 56
中文關鍵詞： 公車司機員排班 、變數產生法 、含額外限制式的最短路徑
外文關鍵詞： bus driver scheduling, column generation, constrained shortest path
相關次數： 點閱：235  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 市區公車為各縣市政府發展都會公路運輸之重點規劃。在公車營運系統之中，人力資源分配乃重要課題，人力資源問題又分成司機員排班問題與輪班問題，求解複雜度高，然而大部分客運業者在處理人力資源調度仍以人工為主，在人事成本考量下，該方法較缺乏效率且傳承不易，故本論文針對司機員排班問題建構數學模式並發展演算法進行求解。
    為有效率求解此問題，本論文採用變數產生法(Column Generation)將司機員排班問題分成主問題與一系列子問題進行求解，主問題從已知可行的勤務中選出最佳勤務組合來滿足班表，子問題建構成含額外限制式的最短路徑問題(Constrained Shortest Path)，用以產生可行且改善主問題求解之勤務，反覆求得滿足各市政府交通局公布班表之最小勤務組合數。
    數據測試結果顯示，本演算法能有效率的求解實際問題，與現行班表相比，亦減少使用之勤務數，改善客運業者人力資源有限之問題。

    Bus driver scheduling is aimed toward finding the minimum number of bus drivers to cover a published timetable of a bus company. When scheduling bus drivers, contractual work rules must be enforced, thus complicating the problem. In this research, we develop a column generation algorithm that decomposes this complicated problem into a master problem and a series of pricing subproblems. The master problem selects optimal duties from a set of known feasible duties, and the pricing subproblem augments the feasible duty set to improve the solution obtained in the master problem. The proposed algorithm is empirically applied to the realistic problems of several bus companies. The numerical results show that the proposed column generation algorithm can solve real-world problems and obtain bus driver schedules that are better than those developed and used by the bus companies.

    LIST OF CONTENTS LIST OF TABLES ii LIST OF FIGURES ii 1. INTRODUCTION 1 1.1 Motivation 1 1.2 Objective 2 1.3 Research Scope 2 1.4 Research Methodology 2 1.5 Research Content with Research Flow Chart 4 2. LITERATURE REVIEW 6 2.1 Heuristic-based Approach 6 2.2 Meta-heuristic Approach 7 2.3 Column Generation-based Approach 8 2.4 Summary 16 3. MATHEMATICAL FORMULATION 17 3.1 Problem Statement 17 3.2 The Notation 19 3.3 The Mathematical Formulation 21 4. SOLUTION ALGORITHM 24 4.1 Column Generation Procedure 24 4.2 The Overall Solution Procedure 33 5. EMPIRICAL STUDIES 36 5.1 A Subset of the GD Bus Company 36 5.2 The Realistic Case: GD Bus Company 43 5.3 The Realistic Case: FY Bus Company 48 6. CONCLUDING REMARKS AND DIRECTIONS OF FUTURE RESEARCH 52 REFERENCES 54

    1. Ahuja, R. K., T. L. Magnanti and J. B. Orlin (1993). Network flows : theory, algorithms, and applications. Englewood Cliffs, N.J., Prentice Hall.
    2. Barnhart, C., et al.(1998). "Branch-and-price: Column generation for solving huge integer programs." Operations Research 46(3): 316-329.
    3. Bront, J. J. M., I. Mendez-Diaz, and G. Vulcano(2009). "A Column Generation Algorithm for Choice-Based Network Revenue Management." Operations Research 57(3): 769-784.
    4. Carraresi, P., G. Gallo, and J. M. Rousseau(1982). "Relaxation Approaches to Large-Scale Bus Driver Scheduling Problems." Transportation Research Part B-Methodological 16(5): 383-397.
    5. De Leone, R., P. Festa, and E. Marchitto(2011a). "A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solution." Journal of Heuristics 17(4): 441-466.
    6. De Leone, R., P. Festa and E. Marchitto (2011b). "Solving a bus driver scheduling problem with randomized multistart heuristics." International Transactions in Operational Research 18(6): 707-727.
    7. de Silva, A.(2001). "Combining constraint programming and linear programming on an example of bus driver scheduling." Annals of Operations Research 108(1-4): 277-291.
    8. Desrochers, M., and F. Soumis(1989). "A Column Generation Approach to the Urban Transit Crew Scheduling Problem." Transportation Science 23(1): 1-13.
    9. Desrosiers, J. and M. E. Lübbecke (2005). A Primer in Column Generation, Springer.
    10. Dias, T. G., J. P. de Sousa, and J. F. Cunha(2002). "Genetic algorithms for the bus driver scheduling problem: a case study." Journal of the Operational Research Society 53(3): 324-335.
    11. Freling, R., D. Huisman, and A. P. M. Wagelmans(2003). "Models and algorithms for integration of vehicle and crew scheduling." Journal of Scheduling 6(1): 63-85.
    12. Gabriel Crainic, T., and J.-M. Rousseau(1987). "The Column Generation Principle And The Airline Crew Scheduling Problem." INFOR 25(2): 136-151.
    13. Huisman, D.(2007). "A column generation approach for the rail crew re-scheduling problem." European journal of operational research 180(1): 163-173.
    14. Huisman, D., R. Freling, and A. P. M. Wagelmans(2005). "Multiple-Depot Integrated Vehicle and Crew Scheduling." Transportation Science 39(4): 491-502.
    15. Lavoie, S., M. Minoux, and E. Odier(1988). "A new approach for crew pairing problems by column generation with an application to air transportation." European journal of operational research 35(1): 45-58.
    16. Li, H., et al.(2015). "A Column Generation Based Hyper-Heuristic to the Bus Driver Scheduling Problem." Discrete Dynamics in Nature and Society):
    17. Lin, D. Y.(2014). "A Dantzig-Wolfe decomposition algorithm for the constrained minimum cost flow problem." Journal of the Chinese Institute of Engineers 37(5): 659-669.
    18. Lourenco, H. R., J. P. Paixao, and R. Portugal(2001). "Multiobjective metaheuristics for the bus-driver scheduling problem." Transportation Science 35(3): 331-343.
    19. Martello, S., and P. Toth(1986). "A Heuristic Approach to the Bus Driver Scheduling Problem." European Journal of Operational Research 24(1): 106-117.
    20. Mesquita, M., et al.(2011). "A new model for the integrated vehicle-crew-rostering problem and a computational study on rosters." Journal of Scheduling 14(4): 319-334.
    21. Mindy Liu, A. H., and Shahabeddin Toobaie(2010). "Genetic Algorithm-Based Column Generation Approach to Passenger Rail Crew Scheduling." Transportation research record):
    22. Muter, İ., et al.(2013). "Solving a robust airline crew pairing problem with column generation." Computers & operations research 40(3): 815-830.
    23. Paias, A., and J. Paixao(1993). "State-Space Relaxation for Set Covering Problems Related to Bus Driver Scheduling." European Journal of Operational Research 71(2): 303-316.
    24. Paixao, J., and M. Pato(1989). "A Structural Lagrangean Relaxation for 2-Duty Period Bus Driver Scheduling Problems." European Journal of Operational Research 39(2): 213-222.
    25. Potthoff, D., D. Huisman, and G. Desaulniers(2010). "Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling." Transportation Science 44(4): 493-505.
    26. Ramli, R., H. Ibrahim, and L. T. Shung(2013). "Innovative Crossover and Mutation in a Genetic Algorithm Based Approach to a Campus Bus Driver Scheduling Problem with Break Consideration and Embedded Overtime." Applied Mathematics & Information Sciences 7(5): 1921-1928.
    27. Toth, A., and M. Kresz(2013). "An efficient solution approach for real-world driver scheduling problems in urban bus transportation." Central European Journal of Operations Research 21: S75-S94.
    28. Vance, P., et al.(1997). "Airline Crew Scheduling: A New Formulation and Decomposition Algorithm." Operations Research 45(2): 188-200.
    29. Yunes, T., A. Moura, and C. de Souza(2005). "Hybrid Column Generation Approaches for Urban Transit Crew Management Problems." Transportation science 39(2): 273-288.

    無法下載圖示
    校外：不公開
    電子論文及紙本論文均尚未授權公開
    QR CODE