臺灣博碩士論文加值系統

台灣時效性貨物運輸業者提供托運人時效性之貨物遞送服務，業者為了改善效率，逐漸將營運網路轉換成為業界常採用之軸輻式營運網路，以降低營運成本。
在營運層級的規劃中，路線貨運業者必須決定貨物路徑、平衡貨櫃以及決定司機排班，司機排班問題為在司機工作規則限制下，決定最少的司機數目以滿足所有的車輛、貨櫃拖運需求，屬於營運規劃之子問題。於本研究之中，嘗試針對路線貨運業司機排班問題之特性發展兩種演算法：插入啟發式演算法以及以網路為基礎之網路演算法，期能有效率取代傳統業者採用之排班經驗法則。
在啟發式演算法中成功的降低了可行解區間，快速地求得可行解。網路演算法則將問題轉換成為網路問題，不僅求解速率高，求解品質亦較啟發式演算法佳。最後於實證研究之中以國內路線貨運業者為研究對象進行求解，發現本研究設計之演算法均能獲得品質相當優良的可行解，甚至能獲得最佳解。

The time-definite freight delivery common carriers provide door-to-door time guaranteed small shipment delivery services for shippers. To improve efficiency, the carriers in Taiwan try to use pure hub-and-spoke network as their operations network. The pure hub-and-spoke network consolidates partial loads with the result of lower operating cost, is the most common operations configuration for the industry. The operations planning determine freight routes, balanced trailer movements, and feeder schedules to guide daily operations. The feeder scheduling problem is to determine a minimum cost assignment of feeder drivers to planned loaded and empty trailer movements while meeting the work rules. In this research we explored the special characteristics of the problem and design two different algorithms to solve it: insertion heuristics algorithm and network-based algorithm. The insertion heuristics successfully reduces the size of schedule patterns set and solve the problem efficiently. In the second algorithm we introduce a network-based model that can both efficiently and effectively solve feeder scheduling problems for Taiwan time-definite freight common carriers using real constraints. In addition, the problem is modeled as an integer program instead of classic set partitioning problem. We used the operations network of the third largest common carrier in Taiwan with randomly generated demands for numerical testing. A very effective computational result demonstrates the two approaches are capable for practical implementation.

目錄 1
圖目錄 4
表目錄 5
第一章 緒論 6
1-1研究動機與目的 6
1-2研究範圍 6
1-3研究方法與流程 9
1-4本研究結構 10
第二章 文獻回顧 11
2-1路線貨運業 11
2-2組員排班問題 19
2-2-1組員配對問題 21
2-2-2組員名單分派問題 22
2-2-3其他產業組員排班研究彙整 22
2-2-4航空業組員排班常用演算法-變數產生法(column generation) 25
2-3軸輻式營運網路 26
2-4最小流量問題 28
2-5小結 31
第三章 路線貨運業司機排班之數學模式 32
3-1問題特性分析 32
3-1-1站所分類與時窗限制 33
3-1-2貨櫃分類 35
3-1-3車輛調度的特殊狀況：Bob-Tail 35
3-1-4司機工時限制 36
3-2問題定義 37
3-3數學模式 38
3-3-1數學符號定義 39
3-3-2路線貨運業司機排班問題最佳化模式 39
第四章 插入式啟發演算法 42
4-1插入式啟發演算法(Insertion heuristics)設計 42
4-2實例說明 45
第五章 網路演算法之設計 48
5-1產生網路矩陣 49
5-2決定網路原則 51
5-2-1網路時間區段分割 51
5-2-2時間過長貨櫃路段拆解 52
5-2-3決定hot load 與cold load原則 53
5-2-4節線連結方式 54
5-2-5排班規劃網路結構 56
5-3求解演算法 59
5-3-1演算法步驟 60
5-3-2數學模式轉化 65
5-3-3負成本迴圈處理機制 68
5-3-4最晚離開時間計算 72
5-4演算法虛擬碼與流程圖 74
第六章 實證研究 78
6-1實證研究數據 78
6-1-1測試數據一：10營業站所數據 79
6-1-2測試數據二：65營業站所數據 80
6-2正確解：路徑列舉(path enumeration) 80
6-2-1求解結果 80
6-2-2小結 82
6-3插入式啟發演算法 84
6-3-1求解結果 84
6-3-2小結 85
6-4網路演算法 86
6-4-1求解結果 86
6-4-2小結 87
6-5演算法與正確解之比較 88
6-5-1一般性比較 88
6-5-2插入式啟發演算法與正確解的比較 90
6-5-3網路演算法與正確解的比較 92
6-5-4網路演算法與啟發演算法的比較 94
第七章 結論與建議 96
7-1結論 96
7-2建議 97
7-2-1網路產生器 97
7-2-2實務界宜採用最佳化技術 97
7-2-3目標函數的調整 98
7-2-4應用於其他產業上 98
參考文獻 99
中文文獻 99
英文文獻 99
附錄、C語言程式碼 103

中文文獻
1.交通部運研所 (1999)，公路汽車貨運運價準則檢討修訂之研究
2.李宇欣，楊承道 (1999)，雙勤務人員排班問題，運輸計畫季刊，第28卷第3期， 409-420
3.杜宇平，顏上堯 (2000)，空服員排班網路模式與求解演算法之研究，中華民國第五屆運輸網路研討會論文集
4.林正章，劉志遠 (1999)，路線貨運業貨物整體運輸網路設計之研究，運輸計畫季刊，第28卷第4期，535-564
5.高玉明 (1996)，路線貨運業貨物排程問題之研究，國立成功大學交通管理科學系碩士論文
6. 顏上堯，林錦翌(1997)，空服員排班組合最佳化之研究，中國土木水利工程學刊，第9卷第2期， 303-313
英文文獻
7.Abara, Jeph (1989), Applying integer linear programming to the fleet assignment problem, Interface 19, 20-29
8.Adlakha V., B. Gladysz, J. Kamburowski(1991), Minimum flows in (s,t) plannar network, Networks 21,767-773
9. Adlakha V. (1999), An Alternate linear algorithm for the minimun flow problem, Journal of the Operational Research Society 50, 177-182
10. Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993) Network Flows: Theory, Algorithms and Applications. Prentice Hall, New Jersey.
11. Akyilmaz, M.O. (1994) An algorithmic framework for routing LTL shipments, Journal of Operational Research 45(5), 529-538.
12. Alberto Caprara, Matteo Fischetti, Paolo Toth, Daniele Vigo and Pier Luigi Guida (1997), Algorithms for railway crew management, Mathematical Programming 79, 125-141
13. Angelo Monfroglio (1998), Hybrid heuristic algorithms for set covering, Computers Operation Research 25(6) 441-455
14. Bryan, D. L. and O’Kelly, M. E. (1999) Hub-and-spoke networks in air transportation: An analytical review, Journal of Regional Science 39(2), 275-295.
15. Beasley J.E.and Cao B. (1996), A tree search algorithm for the crew scheduling problem, European Journal of Operational Research 94, 517-526
16. Beasley J.E.and Cao B. (1998), A dynamic programming based algorithm for the crew scheduling problem, Computers Operation Research 25(7), 567-582
17. Chestler, L. (1985) Overnight air express: spatial pattern, competition and the future of small package delivery services, Transportation Quarterly 39, 59-71
18. Chu H. D., Eric Gelman and Johnson E. L. (1997), Solving large scale crew scheduling problems, European Journal of Operational Research 97, 260-268
19. Crainic T. G and Laporte G. (1997), Planning models for freight transportation, European Journal of Operational Research 97, 409-438
20. Crainic T. G and Laporte G. (1998), Fleet management and logistics, Kluwer, Boston
21. Dawid H., Johannes Konig and Christine Strauss(2001), An enhanced rostering model for airline crews, Computers & Operations Research 28 671-688
22. Feo, Thomas A.; Bard and Jonathan F. (1989), Flight Scheduling And Maintenance Base Planning, Management Science 35, 1415-1433
23.G. B. Dantzig, D. R. Fulkerson(1954), Minimizing the number of tankers to meet a fixed schedule, Naval. Res. Log. Quart 1, 217-222
24. Irina Ioachim, Jacques Desrosiers, Francois Soumis, Nicolas Belanger (1999), Fleet assignment and routing with schedule synchronization constraints, European Journal of Operational Research, 119 75-90
25.L. Bodin(1983), Routing and scheduling of the vehicles and crews-The state of the art, Computers & Operations Research 10(2), 63-211
26. Levine D. (1996), Application of a hybrid genetic algorithm to airline crew scheduling, Computers Operation Research 23(6), 547-558
27.M. Bellmore, G. Bennington, S.Lubore (1969), A multivehicle tanker scheduling problem, Transportation Science 5, 36-47
28. Radhika S.;Scheff, Richard P Jr, Quillinan, John D; Wiper, D Steve, Marsten and Roy E (1994), Fleet assignment at Delta Air Lines, Interfaces, 24, 104-121
29. Sebastian Ceria, Paolo Nobili, Antonio Sassano (1998), A Lagragian-based heuristic for large-scale set covering problems, Mathematical Programming 81, 215-228
30. Sydney C. K. Chu, Edmond C. H. Chan (1998), Crew scheduling of light rail transit in Hong Kong: from modeling to implementation, Computers Operation Research 25(11), 887-894
31. Vance, P. H., Barnhart, C., Johnson, E. L. and Nemhauser, G. L. (1997) Airline crew scheduling: A new formulation and decomposition algorithm, Operations Research 45(2), 188-200.
32. Wark P., Holt J., .Ronnqvist M.and Ryan D. (1997), Aircrew schedule generation using repeated matching, European Journal of Operational Research ,102, 21-35
33. Wedelin D. (1995), The design of 0-1 integer optimizer and its application in the Carmen system, European Journal of Operational Research 87, 722-730
34. Yan S., Tung T.-T. and Tu Y.-P. (2001), Optimal construction of airline individual crew pairings, CAOR(in press)