Full metadata record
DC FieldValueLanguage
dc.contributor.author盧宗成en_US
dc.contributor.authorJason Chung-Cheng Luen_US
dc.contributor.author王晉元en_US
dc.contributor.authorJin-Yuan Wangen_US
dc.date.accessioned2014-12-12T02:23:02Z-
dc.date.available2014-12-12T02:23:02Z-
dc.date.issued1999en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#NT880423007en_US
dc.identifier.urihttp://hdl.handle.net/11536/65615-
dc.description.abstract本研究之目的在於提出一有效的演算法以提升台北捷運公司司機員排班之效率。在研究中,將捷運司機員排班問題建構為集合分割(Set Partitioning)問題模式,並針對此模式設計求解演算法。演算法包含變數產生法(Column Generation)、分支定限法(Branch and Bound)與啟發式解法三階段。 在變數產生法求解階段,將主問題定式為集合涵蓋(Set Covering)問題放鬆整數限制與司機員個數限制後之線性規劃問題,子問題為有限制之最短路徑問題,求解目標主要在產生所有可行之工作班,以找到一較佳之起始可行解。接下來,對於變數產生法求解所得之非整數解結果,利用分支定限法求得整數解。最後,設計一啟發式解法以解決因變數產生法之主問題定式為集合涵蓋問題與放鬆司機員個數限制後,所可能產生之求解結果中任務卡過多,與部份任務卡中有重複涵蓋(Over-Cover)任務之問題。 利用演算法實際求解台北捷運公司司機員排班問題,所需求解時間相較於目前人工方式排班而言已大幅減少,將可提升司機員排班效率。在求解結果中,雖然可能會有少數任務無法排進班表中,但是可比照人工排班現況由領班或助理以備班方式執行。此外,本研究結果可改善人工排班時午班司機員用餐時間過短,而且無法排進班表之任務皆集中在午班用餐時段,所帶給司機員與排班人員的困擾。最後,在需要相同人數的備班司機員來執行那些無法排進班表之任務的情況下,演算法求解結果之總任務卡成本將較人工排班之總任務卡成本為低。zh_TW
dc.description.abstractThis thesis 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. First, We use column generation technique to generate all possible promising tasks. Then, branch and bound method is applied to obtain the integer. Finally, we develop a heuristic local search method to eliminate excess workdays and over-cover tasks, since we use the set-covering problem model in the first phase instead of the set-partitioning problem due to the difficulties of obtaining the feasible solution. 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.en_US
dc.language.isozh_TWen_US
dc.subject捷運司機員排班zh_TW
dc.subject變數產生法zh_TW
dc.subject分支定限法zh_TW
dc.subject啟發式解法zh_TW
dc.subject集合分割zh_TW
dc.subject集合涵蓋zh_TW
dc.subjectMass Rapid Drivers' Schedulingen_US
dc.subjectColumn Generationen_US
dc.subjectBranch and Bounden_US
dc.subjectHeuristicsen_US
dc.subjectSet Partitioningen_US
dc.subjectSet Coveringen_US
dc.title捷運司機員排班問題之研究 - 以台北捷運公司為例zh_TW
dc.titleThe Study of Mass Rapid Transit Drivers' Scheduling Problems - A Case Study of Taipei MRT Companyen_US
dc.typeThesisen_US
dc.contributor.department運輸與物流管理學系zh_TW
Appears in Collections:Thesis