傳統的事前規劃決策模式因無法隨著需求臨時性的出現而改變，使得企業之服務彈性大為降低。此外，因運送車輛的改良，現今貨物運送作業可同時含有配送與撿收兩種作業方式。因此為了可以線上即時處理隨時可能出現之各式需求，本研究以混合型整數規劃方法，建立一個可因應需求改變之含時窗限制與撿收之動態車向途程規劃模式。進而結合禁制搜尋法於此問題之求解演算法中，以兼顧動態問題之求解品質與速度。
本研究修改Solomon(1987)提出之標準測試例題R101~R105，撿收顧客以10％、30％和50％的比例隨機選取，並設計合理之需求出現時間做為需求出現之依據。採用田口方法分析最佳水準因子組合方式，包括禁制搜尋法之參數設定、車輛出發滿載率、貨物門檻率和距離門檻值的應用。最後，比較不同的動態車輛途程規劃演算法之求解效益。研究結果發現：禁制搜尋法運用於含時窗限制與撿收之動態車輛途程規劃問題中，能有效增進求解品質，且有別於靜態研究，禁制表單最佳長度可能有縮短的趨勢，而最佳車輛出發滿載率則為車容量之65％∼75％。
關鍵詞：禁制搜尋法、動態車輛途程規劃、撿收作業、田口方法

目錄
摘要 I
誌謝 II
目錄 III
表目錄 VI
圖目錄 VIII
第一章　緒論 1
1.1　研究動機 1
1.2　研究目的 2
1.3　研究範圍與研究限制 3
1.4　研究流程與論文架構 4
第二章　文獻回顧 8
2.1　含時窗限制之車輛途程規劃問題 8
2.2　含撿收之車輛途程規劃問題 13
2.3　含時窗限制與撿收之車輛途程規劃問題 15
2.4　動態車輛途程規劃問題 16
第三章　含時窗限制與撿收之動態車輛途程規劃模式 19
3.1　問題界定 19
3.2　數學模式 20
3.2.1　符號說明 20
3.2.2　數學模式 23
第四章　動態車輛途程規劃問題之演算法 28
4.1　動態車輛路線建立演算法 34
4.2　禁制搜尋法(Tabu Search) 40
4.3 路線間動態車輛路線改善演算法 43
4.3.1　Or-opt路線改善演算法 43
4.3.2　3-opt 路線改善演算法 47
4.3.3　2-opt 路線改善演算法 50
4.3.4　Cross-opt 路線改善演算法 54
第五章　數值實驗分析 58
5.1　DVRPBTW測試例題 58
5.2　實驗方法介紹 62
5.2.1　田口方法 62
5.2.2　實驗項目說明 64
5.3　禁制搜尋法應用於動態車輛途程規劃問題之探討 66
5.3.1　10％撿收顧客比例 67
5.3.2　30％撿收顧客比例 69
5.3.3　50％撿收顧客比例 71
5.3.4　小結 74
5.4　車輛派遣原則之探討 76
5.5　演算法之效益分析 83
第六章　結論與建議 88
參考文獻 90
附 錄 96
表目錄
表 5.1　R101∼R105之需求時窗特性表 59
表 5.2　禁制搜尋法之10％撿收顧客比例實驗因子配置表 68
表 5.3　禁制搜尋法之10％撿收顧客比例目標輸出值回應表 68
表 5.4　禁制搜尋法之10％撿收顧客比例S/N比回應表 68
表 5.5　禁制搜尋法之10％撿收顧客比例目標輸出值比較 69
表 5.6　禁制搜尋法之30％撿收顧客比例實驗因子配置表 70
表 5.7　禁制搜尋法之30％撿收顧客比例目標輸出回應表 70
表 5.8　禁制搜尋法之30％撿收顧客比例S/N比回應表 71
表 5.9　禁制搜尋法之30％撿收顧客比例目標輸出值比較 71
表 5.10　禁制搜尋法之50％撿收顧客比例實驗因子配置表 72
表 5.11　禁制搜尋法之50％撿收顧客比例目標輸出回應表 73
表 5.12　禁制搜尋法之50％撿收顧客比例S/N比回應表 73
表 5.13　禁制搜尋法之50％撿收顧客比例目標輸出值比較 73
表 5.14　R101∼R105禁制搜尋法之最佳水準因子組合 75
表 5.15　車輛派遣之10％撿收顧客比例實驗因子配置表 79
表 5.16　車輛派遣之30％撿收顧客比例實驗因子配置表 79
表 5.17　車輛派遣之50％撿收顧客比例實驗因子配置表 79
表 5.18　車輛派遣之最佳水準因子組合 81
表 5.19　車輛派遣之目標輸出值比較 82
表 5.20　R101不同演算法間之總成本比較 84
表 5.21　R102不同演算法間之總成本比較 84
表 5.22　R103不同演算法間之總成本比較 85
表 5.23　R104不同演算法間之總成本比較 85
表 5.24　R105不同演算法間之總成本比較 86
表 5.25　不同演算法間之車輛數比較 87
附表一　R101測試資料範例 96
附表二　R102測試資料範例 99
附表三　R103測試資料範例 102
附表四　R104測試資料範例 105
附表五　R105測試資料範例 108
圖目錄
圖 1.1　車輛途程規劃問題類型 6
圖 1.2　研究流程 7
圖 4.1　循序改善型動態途程規劃演算法架構 30
圖 4.2　隨機改善型動態途程規劃演算法架構 31
圖 4.3　動態路線建立演算法流程圖 32
圖 4.4　動態路線改善演算法流程圖 33
圖 4.5　禁制搜尋法應用於車輛途程規劃問題流程圖 42
圖 5.1　R1系列需求節點分佈圖 59
圖 5.3　車輛派遣流程圖 78

1. 申生元，時窗限制途程問題，國立交通大學工業工程與管理研究所博士論文(1998)。
2. 易德華，軟時窗車輛巡迴問題之研究，國立中央大學土木工程研究所碩士論文(1998)。
3. 卓裕仁，以聚集啟發式方法求解多車種與週期性車輛路線問題之研究，國立交通大學運輸工程與管理學系所博士論文(2001)。
4. 梅明德，線上型時窗限制車輛路線問題之模式與求解演算法，國立中央大學土木工程研究所博士論文(1999)。
5. 陳日光，二水準田口直交表最高解析度因子配置之研究，中華大學工業工程與管理研究所碩士論文(1997)。
6. 陳惠國、薛哲夫，「含依時性旅行時間之即時車輛途程規劃問題」，第十屆校際運輸學術聯誼研討會論文集，第139-160頁(2002)。
7. 張季娜譯，田口式品質工程導論，台北市中華民國品質管制學會(1996)。
8. 黃聖峰，考量回程撿收之車輛途程問題研究，大葉大學工業工程研究所碩士論文(1999)。
9. 曾維豪，軟性時窗與回程撿收之車輛途程問題研究，元智大學工業工程研究所碩士論文(2001)。
10. 廖亮富，含時窗限制多部車車輛途程問題解算之研究，元智大學工業工程研究所碩士論文(1998)。
11. 劉金維，時依性路段既時窗限制下單一車輛路線問題之研究，國立中央大學土木工程研究所博士論文(2000)。
12. 劉雅魁，運用路線臨域法求解車輛路線含回程取貨問題，國防管理學院資訊管理研究所碩士論文(1998)。
13. Bowerman, R.L., Calamai, P.H. and Hall, G.B. “The Spacefilling Curve with Optimal Partitioning Heuristic for the Vehicle Routing Problem,” European Journal of Operational Research, Vol. 76, pp. 128-142(1994).
14. Box, G.E.P. and Hunter, J.S. “The 2k-p Fractional Factorial Design,Part Ⅰ,”Technometrics, Vol. 3, pp. 311-351(1961).
15. Benton, W.C. and Rossetti, M.D. “The Vehicle Scheduling Problem with Intermittent Customer Demands,” Operations Research, Vol. 19, No. 6, pp. 521-531(1992).
16. Casco, D.O., Golden, B.L. and Wasil, E.A. “Vehicle Routing with Backhauls: Methods, Agorithm and Case Studies,” Vehicle Routing and Studies, pp.127-147(1988).
17. Clarke, G. and Wright, J.W. “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581(1964).
18. Deif, I. And Bodin, L. “Extension of the Clarke and Wright Algorithm for Solving the Vehicle Routing Problem with Backhauling,” Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management, pp. 75-96, Bobson Park, MA(1984).
19. Duhamel, C., Potvin, J.Y. and Rousseau, J.M. “A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows,” Transportation Science, Vol. 31, No. 1, pp. 49-59(1997).
20. Gendreau, M., Guertin, F., Potvin, J.Y. and Taillard, E. “Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching,” Transportation Science, Vol. 33, No. 4, pp. 381-390(1999).
21. Glover, F. and Laguna, M. Tabu Search, Kluwer Academic Pulishers(1997).
22. Gillett, B. and Miller, L. “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, Vol. 22, pp. 340-349(1974).
23. Glover, F. “Tabu Search: Part Ⅰ,” Operations Research Socity of America Journal on Computing, Vol. 1, No. 3, pp. 190-206(1989).
24. Lin, S. and Kernighan, B. “An Effective Heuristics Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498-516(1973).
25. Lysgaard, J. “Dynamic Transportation Networks in Vehicle Routing and Scheduling,” INTERFACES, Vol. 22, No. 3, pp. 45-55(1992).
26. Mole, R.H. and Jameson, S.R. “A Sequential Route-Building Algorithm Employing Generalized Savings Criterion,” Operation Research Quarterly, Vol. 27, pp. 503-527(1976).
27. Or, I. Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking, Ph.D. Thesis, Department of Industrial Engineering and Management Science, Northwestern University(1976).
28. Plackett, R.L. and Purman, J.B.“The Design of Optimum Multifactrial Experiments,”Biomatrika, Vol. 33,pp. 305-325 (1946).
29. Powell, W.B., Carvalho, T.A., Godfrey, and Simon, H.P. “Dynamic Fleet Management as a Logistics Queuing Network,” Annals of Operations Research, Vol. 61, pp. 165-188(1995).
30. Powell, W.B., Jaillet, P. and Odoni, A. “Stochastic and Dynamic Networks and Routing,” Handbook in OR & MS, Vol. 8, Network Routing, pp. 141-295(1995).
31. Psaraftis, H.N. “Dynamic Vehicle Routing— Status and Prospects,” Annals of Operations Research, Vol. 61, pp. 143-164(1995).
32. Potvin, J.Y.,Duhamel, C. and Guertin, F. “A Genetic Algorithm for Vehicle Routing with Backhauling,” Applied Intelligence, Vol. 6, pp. 345-355(1996).
33. Potvin, J.Y., Kervahut, T., Garcia, B.L. and Rousseau, J.M. “The Vehicle Routing Problem with Time Windows, Part Ⅰ:Tabu Search,” INFORMS Journal on Computing, Vol. 8, No. 2, pp. 158-164(1996).
34. Solomon, M.M., Vehicle Routing and Scheduling Problems with Windows Constraints: Models and Algorithms, Ph.D. Dissertation, Department of Decision Science, University of Pennsylvania(1983).
35. Solomon, M.M. “Algorithm for the Vehicle Routing and Scheduling Problems with Time Windows Constraints,” Operations Research, Vol. 35, No. 2, pp. 254-265(1987).
36. Solomon, M.M., Baker, E.K. and Schaffer, J.R. “Vehicle Routing and Scheduling Problems with Time Windows Constraints: Efficient Implementations of Solution Improvement Procedures,”In Golden, B.L. and Assad, A.A. Eds, Vehicle Routing: Methods and Studies, pp. 85-105, Elservier Science Publishers, Amsterdam(1988).
37. Taillard, E., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J.Y. “A Tabu Search Heuristic for the Vehicle Routihg Problem with Soft Time Windows,” Transportation Science, Vol.31, No. 2(1997).
38. Thangiah, S.R., Potvin, J.Y. and Sun, T. “Heuristic Approaches to Vehicle Routing with Backhauls and Time Windows,” Computers and Operations Research, Vol. 23, pp. 1043-1057(1996).
39. Toth, P. and Vigo, D. “An Exact Algorithm for the Vehicle Routing Problem with Backhauls,” Transportation Science, Vol. 31, pp. 372-385(1997).
40. Toth, P. and Vigo, D. “A Heuristic Algorithm for the Symmetric and Asymmetric Vehicle Routing Problems with Backhauls,” European Journal of Operational Research, Vol. 113, pp. 528-543(1999).
41. Yano, T., Chan, L. and Richter, K.M. “Vehicle Routing at Quality Stores,” INTERFACES, Vol. 17, No. 2, pp. 52-63 (1987).