標題: 結合限制規劃與數學規劃求解捷運系統人員排班問題之研究
Hybrid Methods of CP and MP for MRT Crew Scheduling Problem
作者: 韓復華
HAN ANTHONY FU-WHA
國立交通大學運輸科技與管理學系(所)
關鍵字: 組員(人員)排班;限制規劃;變數產生法;限制滿足問題;捷運系統
公開日期: 2007
摘要: 運輸系統工作人員(組員)的勤務安排,通常分為排班(Scheduling)問題與輪值 (Rostering)問題兩個部份來探討。在都市大眾運輸組員排班問題中,其目標除須考慮 人事成本外,另需考慮駕駛時數差異最小的公平性目標。故雖然在成本結構較航空組 員排班單純,但由於排班時需考慮雙目標,亦增加都市大眾運輸求解時的難度。且在 班次頻率方面,因都市大眾運輸的班次頻率較航空運輸業密集,因此,其排班的規模 亦遠大於航空組員排班的規模。有鑑於司機員排班對台北捷運的重要性與近年來限制 規劃與數學規劃整合的發展,本研究擬應用以限制規劃為基礎之變數產生法來探討求 解台北捷運公司司機員排班的問題。 現實問題中如何產生所有滿足實務要求的可行勤務,是一個極複雜的問題。本研 究將勤務產生視為一個限制滿足問題,並以限制規劃為基礎構建一個勤務產生模式 (CP-Based Duty Generator),簡稱CPDG 模式。該模式除可產生符合各項法規(工時、 休時等)與營運因素(基地、列車接續等)之所有可行勤務集合之外,亦可導入要求勤務 分配公平的考慮因素。本研究依據CPDG 模式架構,將雙目標之排班問題轉換為傳統 單目標之集合分割問題(SPP)模式,再將此SPP 模式放鬆後的線性規劃(LP)問題,做為 變數產生法之主問題,與受限之主問題(RMP, Restricted Master Problem)建立CP-Based 變數產生法的求解架構。本研究將以台北捷運(淡水線)為個案,進行相關模式之構建 與測試,並將與實際班表進行比較,以評估CP 模式方法之績效。
官方說明文件#: NSC96-2221-E009-124
URI: http://hdl.handle.net/11536/88401
https://www.grb.gov.tw/search/planDetail?id=1455138&docId=260216
Appears in Collections:Research Plans


Files in This Item:

  1. 962221E009124.PDF