臺灣博碩士論文加值系統

物流中心在商品流通的過程中，為滿足客戶的配送需求及追求合理的運輸成本，必須快速地做出最佳配送路線的決策。以往時窗限制之車輛途程問題，只需考慮車輛的載重、全程時間以及各顧客點時窗的限制，以最小的運輸成本來安排車輛配送的路徑。然而在交通流量愈來愈大的今日，商品於時窗限制內準時配送將愈來愈難，因此將違反時窗限制的拒收處分，以合理的處罰成本取而代之，即為軟性時窗限制之車輛途程問題。本研究針對軟性時窗限制的考量，並利用最鄰近法、掃描法及節省法來求得初始解，再以數種不同搜尋規則之禁制搜尋法來改善初始解。最後本研究利用Solomon之車輛途程硬性時窗的題庫 (Solomon, 1987) 進行測試，以三種初始解利用禁制搜尋法改善後，發現以最鄰近法所建構的初始途程經改善後最佳。同時，以所得之最佳解與歷年來使用相同題庫所出版的最佳解相互比較，結果發現本研究對於題型R2及RC2的改善有較佳的結果。

The distribution center has to make optimal daily vehicle routing decisions to satisfy the customers’ demands and search for the reasonable transportation cost during the business flow process. Previous vehicle routing problem with time windows (VRPTW) only considers the vehicle capacity, total available time and customer’s time window constraints, and the search for the best vehicle routing decisions is based on the minimum transportation cost. However, as the traffic flow grows, the on-time delivery is getting difficult to achieve under the time constraints. Hence, the vehicle routing problem with soft time windows (VRPSTW) emerges as the penalty cost approach substitutes the reject acceptance, which violates the time window constraints. This study dealt with the VRPSTW, and utilized nearest-neighbor, sweep, and saving methods to find the initial solution. Then, the tabu search rules were utilized to improve the initial solutions. The approach was tested by the data sets of Solomon’s (1987) vehicle routing problem. The results show that the use of nearest-neighbor method as initial solution performs best in getting the best improved solutions. This approach also performs best in data sets of R2 and RC2 then previous solution.

第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍及假設 2
1.4 研究流程 3
第二章 文獻探討 5
2.1 車輛途程問題之概論 5
2.2 車輛途程問題之分類 5
2.3 含時窗限制之車輛途程問題的求解方法 7
2.3.1 含時窗限制之車輛途程問題之初始解法 11
2.3.2 初始解之改善 12
2.4 相關文獻之探討 14
2.4.1 國外相關文獻 14
2.4.2 國內相關文獻 16
2.5 禁制搜尋法簡介 17
2.6 禁制搜尋法之主要組成要素 18
第三章 模式設定與方法研究 22
3.1 模式設定 22
3.1.1 符號定義 22
3.1.2 模式建立 23
3.2 初始解的構建 24
3.3 交換法 27
3.4 鄰近解之定義 29
3.4.1 途程內鄰近解之定義 30
3.4.2 途程間鄰近解之定義 32
3.6 方法研究 34
第四章 實例驗證 36
4.1 測試題型之介紹 36
4.2 途程問題之基本資料 37
4.3 輸出結果顯示及說明 39
第五章 結果分析與實驗設計 46
5.1 結果分析 46
5.2 實驗設計 48
第六章 結論與未來研究 52
6.1 結論 52
6.2 未來研究 52
參考文獻 54
附錄ㄧ 初始解數據 57
附錄二 改善解數據 59
附錄三 改善解之題庫比較數據 65
附錄四 變異數分析表 67
附錄五 實驗設計相關圖表 71

曾國雄，「現代化儲運系統-理論與實務應用」，鴻儒堂出版社，1983
黃文昌，「時窗限制下貨物配送問題求解方式之研究時空雙準則平行節省法之研擬」，交通大學運輸研究所，碩士論文，1992.
杜世文，「多目標與模糊時窗貨物配送啟發式解法之研究」，交通大學運輸研究所，碩士論文，1992.
楊能舒，吳淵齊，「物流中心運輸成本及短缺罰金之最佳化模式」，第八屆全國自動化科技研討會論文集（一），1994，PP. 578-584
廖忠雄，黃敏亮，王淑娟，陳煌儒，王銘宗，「物流中心之多目標與混合型時窗限制配送車輛途程問題之研究」，中華民國工業工程學會八十四年會論文集，1995，pp. 625-632.
王木坤，「時間限制條件下配銷系統路徑與途程問題之研究」，中原大學工業工程所，碩士論文，1997.
廖亮富，「含時窗限制多部車車輛途程問題解算之研究」，元智大學工業工程所，碩士論文，1998.
Balakrishnan, N., “Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows”, Journal of the Operational Research Society, 1993, Vol. 44, pp. 297-287.
Beasley, J., “Route First-Cluster Second Methods for Vehicle Routing”, Omega, Vol. 118, pp. 403-408.
Bodin, L., B. Golden, A. Assad and D. Bull, “Routing and Scheduling of Vehicles and Crews: The State of The Art”, Computers & Operations Research, 1983, Vol. 10, pp.63-211.
Bowerman, R., P. Calamai and G. Hall, “The Spacefilling Curve with Optimal Partitioning Heuristic for the Vehicle Routing Problem,” European Journal of Operational Research, 1994, Vol. 76., pp.128-142.
Clark, G. and J. Wright, “Scheduling of Vehicles from a Central Depot to Number of Delivery Points”, Operation Research, 1964, Vol. 12, pp. 568-581.
Dueck, G. and T. Scheuer, “Threshold Accepting Purpose Optimization Algorithm Appearing Superior to Simulated Annealing”, Joural of Computational Physics, 1990, Vol 90, pp. 161-175
Duhamel, C., J. Potvin and J. Rousseau, “A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows”, Institute for Operations Research and the Management Sciences, 1997, Vol. 31, pp.49-59
Fisher, M. and R. Jaikumar, “A Generalised Assignment Heuristic for Vehicle Routing”, Networks, 1981, Vol. 11, pp. 109-124.
Fisher, M., K. Jornsten and O. Madsen, “Vehicle Routing with Time Windows: Two Optimization Algorithms” Operations Research, 1997, Vol. 45, pp. 488-492.
Garcia, B., J. Potvin and J. Rousseau, “A Parallel Implementation of The Tabu Search Heuristic for Vehicle Routing Problems with Time Window Constraints”, Computers & Operations Research, 1994, Vol 21, pp.1025-1033.
Gillett, B. and L. Miller, “A Heuristic Algorithm for the Vehicle Dispath Problem”, Operations Research, 1974, Vol. 22, pp. 340-349.
Glover, F. “Tabu Search-Part I”, ORSA Journal on Computing, 1989, Vol. 1, No. 3, pp. 190-206.
Golden, B., L. Bodin, T. Doyle and W. Stewart, “Approximate Traveling Salesman Algorithms”, Operation Research, 1980, Vol. 28, pp549-711.
Haimovich, M. and A. Kan, “Bounds and Heuristics for Capacitated Routing Problems”, Mathematic Operation Research, 1985, Vol. 10, pp. 527-542.
Kirkpatrick, S., C. Gelatt Jr. and M. Vecchi, “Optimization Simulated Annealing”, Science, 1983, Vol. 220, No. 4598, pp. 671-680.
Kohl, N. and O. Madsen, “An Optimization Algorithm for The Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation,” Operations Research, 1997, Vol. 45, No 3, May-June, pp.395-406.
Kolen, A., J. Rinnooy and H. Trienekens, “Vehicle Routing with Time Windows”, Operation Research, 1987, Vol. 35, No. 2, pp. 266-273.
Koskosidis, Y., W. Powell and M. Solomon, “An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints”, Transportation Science, 1992, Vol. 26, pp.69-85.
Kulkavni, R. and P. Bhave, “Integer Programming Formulations of Vehicle Routing Problem”, Eurpean Journal of Operational Research, 1985, Vol. 20, pp. 56-87.
Lenstra, J. and A. Kan, “Complexity of Vehicle Routing and Scheduling Problems,” Networks, 1981, Vol. 11, pp. 221-228.
Lin, S. and B. Kernighan, “An Effective Heuristic Algorithm for The Traveling Salesmen Problem”, Operations Research, 1973, Vol. 21, pp. 498-516.
Mole, R. and S. Jameson, “A Sequeutial Route-Building Algorithm Employing A Generalized Savings Criterion”, Operation Research Quarterly, 1976, Vol. 27, pp. 503-511.
OR, I., “Traveling Salesman-Type Combinatorial problem and Their Relation to the Logistics of Blood Banking”, Ph.D. dissertation, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL, 1976.
Osman, I., “Metastrategy Simulated annealing and Tabu Search Algorithms for The Vehicle Routing Problem”, Annals of Operations Research, 1993, Vol. 41, pp. 421-451.
Potvin, J. and J. Rousseau, “An Exchange Heuristic for Routing Problems with Time Windows”, Journal of the Operational Research Society, 1995, Vol. 66, 331-340.
Potvin, J., T. Kervahut, B. Garcla and J. Rousseau, “The Vehicle Routing Problem with Time Windows Part I：Tabu Search,” INFORMS Journal on Computing, 1996, Vol. 8, No. 2, Spring, pp. 158-164.
Renaud, J., G. Laporte and F. Boctor, “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem,” Computers Operations Research, 1996, Vol. 23, No 3, pp. 229-235.
Taillard, E., P. Badeau, M. Gendreau, F. Guertin and J. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Science, 1997, Vol. 31, No. 2, May, pp.170-186.