結合限制規劃與數學規劃求解捷運系統人員排班問題之研究

Abstract

運輸系統工作人員(組員)的勤務安排，通常分為排班(Scheduling)問題與輪值 (Rostering)問題兩個部份來探討。在都市大眾運輸組員排班問題中，其目標除須考慮 人事成本外，另需考慮駕駛時數差異最小的公平性目標。故雖然在成本結構較航空組 員排班單純，但由於排班時需考慮雙目標，亦增加都市大眾運輸求解時的難度。且在 班次頻率方面，因都市大眾運輸的班次頻率較航空運輸業密集，因此，其排班的規模 亦遠大於航空組員排班的規模。有鑑於司機員排班對台北捷運的重要性與近年來限制 規劃與數學規劃整合的發展，本研究擬應用以限制規劃為基礎之變數產生法來探討求 解台北捷運公司司機員排班的問題。 現實問題中如何產生所有滿足實務要求的可行勤務，是一個極複雜的問題。本研 究將勤務產生視為一個限制滿足問題，並以限制規劃為基礎構建一個勤務產生模式 (CP-Based Duty Generator)，簡稱CPDG 模式。該模式除可產生符合各項法規(工時、 休時等)與營運因素(基地、列車接續等)之所有可行勤務集合之外，亦可導入要求勤務 分配公平的考慮因素。本研究依據CPDG 模式架構，將雙目標之排班問題轉換為傳統 單目標之集合分割問題(SPP)模式，再將此SPP 模式放鬆後的線性規劃(LP)問題，做為 變數產生法之主問題，與受限之主問題(RMP, Restricted Master Problem)建立CP-Based 變數產生法的求解架構。本研究將以台北捷運(淡水線)為個案，進行相關模式之構建 與測試，並將與實際班表進行比較，以評估CP 模式方法之績效。