臺灣博碩士論文加值系統

宅配物流中心在商品流通的服務過程中，為滿足消費者的配送需求與追求運輸成本最小化的期望下，希望能迅速地做出最佳的配送路徑決策。此決策不但能增進獲利來達到企業營運所追求的目標，也能提升其本身的服務品質，藉此滿足消費者多變需求下的滿意度。因此，本研究將針對消費者對於產品種類的多樣化需求下，採用先以節省法為基礎，求得一組優良的初始解，再輔以禁忌搜法 (STS) 進行宅配物流中心移步交換與路徑規劃中的車輛途程間之改善，來滿足總配送成本最小化的目標。而在本研究之隨機模擬的測試例題中，所提出之 STS 演算法與最佳化軟體 (LINGO) 的相互比較下，可以發現到本研究所提之STS法可以有效率地求出一組優良的解。然而當問題規模較大時，STS 與 LINGO 的運算時間之差異程度更為顯著，而在求解的效果上，不會有太大的差異。

For the home delivery service industry, the company has to find the shortest delivery path in order to satisfy the consumer’s needs with the minimum of transportation cost. Besides, it increases not only the profits of company but also raises the service qualities of this company to fit the customers’ various demands. In this research, we propose a heuristic method which was based on savings algorithm and tabu search (STS) with move methods and vehicle routing decisions to satisfy the objective of minimum transportation cost. In comparison with the solutions by STS and optimum solutions by LINGO with the simulation test problems, we found that STS had better performance in these test problems. When the problem size becomes larger, the between STS and LINGO solution time becomes significantly different. However, the solutions of the STS approach have no significant difference with that of the LINGO in all test problems.

目 錄
頁次
中文摘要 i
ABSTRACT ii
誌謝 i
目 錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍與假設 3
1.4 研究流程 4
第二章 文獻回顧 7
2.1 車輛途程類型 (VRP) 之分類 7
2.2 車輛途程問題 (VRP) 之目標分類 8
2.3 車輛途程問題 (VRP) 之求解方法分類 9
2.4 啟發式方法運用在車輛途程問題之文獻回顧 10
2.4.1 傳統啟發式方法 (Classical-heuristic) 10
2.4.2 萬用啟發式方法 (Meta-heuristic) 16
第三章 模式建立與求解流程 20
3.1 研究假設與限制 20
3.2 模式建立 21
3.3節省法與禁忌搜尋演算法之建構 24
3.3.1 建構起始解 25
3.3.2 後續改善演算法 29
3.3.2.1 宅配物流中心之位置規劃改善（移步） 30
3.3.2.2 宅配物流中心內途程規劃改善（插入法） 34
第四章 例題測試與績效衡量 36
4.1 配送系統路徑規劃之例題測試 36
4.2 驗證績效準則 42
4.2.1 求解效果之績效驗證 42
4.2.2 運算時間之績效驗證 48
第五章 結論與建議 57
5.1結論 57
5.2建議與未來研究方向 57
參考文獻 59
附錄一 宅配物流中心資訊表 64
附錄二 第一組模擬試題消費者資訊表 67
附錄三 第二組模擬試題消費者資訊表 69
附錄四 第三組模擬試題消費者資訊表 73
附錄五 第四組模擬試題消費者資訊表 78
附錄六 第五組模擬試題消費者資訊表 83
附錄七 演算法模擬試題車輛途程資訊表 93


圖目錄
頁次
圖1-1 B2B 通路配銷方式 2
圖1-2 B2C 通路配銷方式 2
圖1-3 C2C 通路配銷方式 2
圖1-4 研究流程架構圖 6
圖2-1 連結 (Join) 11
圖2-2 併入 (Attach) 11
圖2-3 合併 (Merge) 11
圖2-4 掃描法圖例 12
圖2-5 Swap 途程內交換 13
圖2-6 Swap 途程間交換 14
圖2-7 2-opt 途程內交換 14
圖2-8 2-opt 途程間交換 15
圖2-9 Or-opt 途程內交換 15
圖2-10 Or-opt 途程間交換 16
圖3-1 節省法起始解之流程圖 27
圖3-2 節省法節省量之計算 28
圖3-3 節省法之連結改善方式 29
圖3-4 宅配物流中心移步 31
圖3-5 門檻值接受法之意義 32
圖3-7 宅配物流中心內插入法之流程圖 35
圖4-1 第一組消費者為 5 之母體兩樣本 t 分析 43
圖4-2 第二組消費者為 8 之母體兩樣本 t 分析 43
圖 4-3 第三組消費者為 12 之母體兩樣本 t 分析 44
圖 4-4 第四組消費者為 15 之母體兩樣本 t 分析 44
圖4-5 第五組消費者為 18 之母體兩樣本 t 分析 45
圖4-6 第一組消費者為 5 之 F-方法 Levene’s 方法分析 46
圖4-7 第二組消費者為 8 之 F-方法 Levene’s 方法分析 46
圖4-8 第三組消費者為 12 之 F-方法 Levene’s 方法分析 47
圖4-9 第四組消費者為 15 之 F-方法 Levene’s 方法分析 47
圖4-10 第五組消費者為 18 之 F-方法 Levene’s 方法分析 48
圖4-11 第一組模擬測試例題時間 ANOVA 分析 49
圖4-12 第二組模擬測試例題時間 ANOVA 分析 50
圖4-13 第三組模擬測試例題時間 ANOVA 分析 51
圖4-14 第四組模擬測試例題時間 ANOVA 分析 52
圖4-15 第五組模擬測試例題時間 ANOVA 分析 53
圖4-16 第一組模擬測試例題時間盒型圖與散佈圖 54
圖4-17 第二組模擬測試例題時間盒型圖與散佈圖 54
圖4-18 第三組模擬測試例題時間盒型圖與散佈圖 55
圖4-19 第四組模擬測試例題時間盒型圖與散佈圖 55
圖4-20 第五組模擬測試例題時間盒型圖與散佈圖 56


表目錄
頁次
表 4-1 模擬測試例題宅配物流中心與消費者基本資料表 38
表 4-2 模擬測試例題相關數據表 38
表 4-3 STS 演算法與 LINGO 第一組模擬測試例題結果比較 39
表 4-4 STS 演算法與 LINGO 第二組模擬測試例題結果比較 39
表 4-5 STS 演算法與 LINGO 第三組模擬測試例題結果比較 40
表 4-6 STS 演算法與 LINGO 第四組模擬測試例題結果比較 40
表 4-7 STS 演算法與 LINGO 第五組模擬測試例題結果比較 41

杜世文，「多目標與模糊時窗貨物配送啟發式解法之研究」，國立交通大學交通運輸工程研究所，碩士論文，1992。
鄭啓忠，「配送中心場址規劃及選擇」，元智大學工業工程研究所，碩士論文， 1995。
徐明輝，「多部車一般性車輛途程解算法之研究」，元智大學工業工程研究所，碩士論文，1997。
白俊偉，「隨機型區位-途程問題解法之研究」，大葉大學工業工程研究所，碩士論文，1999。
許哲榮，「多產品配送中心場址規劃與選擇」，元智大學工業工程研究所，碩士論文，1998。
陳坤賓，「模擬退火演算法應用於車輛途程問題之研究」，元智大學工業工程研究所，碩士論文，1998。
敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，元智大學工業工程研究所，碩士論文，1999。
吳琴玲，「物流配送系統之區位-途程問題研究」，國立雲林科技大學工業工程與管理研究所，碩士論文，2000。
顏嘉宏，「區位-途程問題啟發式解法之研究」，大葉大學工業工程研究所，碩士論文，2000。
李順斌，「物流配銷系統下整合區位途程和存貨問題之研究」，國立屏東科技大學資訊管理研究所，碩士論文，2002。
羅敏華，「蟻群最佳化演算法於載重限制之車輛途程問題的研究」，元智大學工業工程研究所，碩士論文，2002。
夏承永，「以遺傳演算法求解多車種多倉庫之車輛途程問題」，國立清華大學工業工程與工程管理研究所，碩士論文，2003。
張振邦，「兼營宅配業務之快遞業車輛路線規劃問題」，南台科技大學行銷與流通管理研究所，碩士論文，2003。
陳怡芳，「單一宅配車輛路線規劃問題」，逢甲大學交通工程與管理研究所，碩士論文，2004。

許晉嘉，「宅配業貨物配送路線規劃問題之研究」，國立成功大學交通管理科學研究所，碩士論文，2004。
曹餘偉，「應用禁忌搜尋法求解多車種多物流中心之區位途程問題」，元智大學工業工程研究所，碩士論文，2006。
Antunes, A. and Petters, D., “A Dynamic Optimization Model for School Network Planning,” Socio-Economic Planning Sciences, Vol. 34, pp. 101-120, 2000.
Bodin, L. D., B. L. Golden, A. A. Assad and M. O. Ball, “Routing and Scheduling of Vehicles and Crews. The State of the Art,” Computers and Operations Research, Vol. 10, No. 2, pp. 63-211, 1983.
Bowerman, R. L., P. H. Calamai and G. B. Hall, “The Spacefilling Curve with Optimal Partitioning Heuristic for the Vehicle Routing Problem,” European Journal of Operational Research, Vol. 76, pp. 128-142, 1994.
Clarke, G. and W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operation Research, Vol. 12, pp. 568-581, 1964.
Cornorjols, G., Nemhauster, G. L, and Wolsry L. A., “The Uncapacitated Facility Location Theory,” John Wiley and Sons, pp. 119-171, 1990.
Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors, Combinatorial Optimization, pp. 325-338, Wiley, Chichester, 1979.
Dondo, R. and J. Cerda, “A Cluster-Based Optimization Approach for the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Window,” European Journal of Operational Research, In Press, Corrected Proof, Available online 23 January 2006.
Dorigo M., Optimization, Learning and Natural Algorithms, Ph.D.Thesis, Politecnicodi Milano, Italy,1992
Galvao, R. D. and Santibanez-Gonzalez, E. R., “A Lagrangean Heuristic for The -Median Dynamic Location Problem,” European Journal of Operational Research, Vol. 58, pp. 250-262, 1992.

Gendreau, M., G. Laporte, C. Musaraganyi and E. D. Taillard, “A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem,” Computers and Operations Research, Vol. 26, pp. 1153-1173, 1999.
Gillett, B. E. and L. R. Miller, “A Heuristic Algorithm for the Vehicle-Dispatch Problem,” Operations Research, Vol. 22, pp. 340-349, 1974.
Glover, F. “Tabu Search-Part I,” ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206, 1989.
Golden, B., A. Assad, L. Levy and F. Gheyaens, ”The fleet size and mix vehicle routing problem,” Computers & Operations Research, Vol. 11, No. 1, pp. 49-66, 1984.
Hansen, P. H., B. Hegegahl, S. Hjortkjar and B. Obel, “A Heuristic Solution to the Warehouse Location-Routing Problem,” European Journal of Operational Research, Vol. 78, pp. 111-127, 1994.
Hollland, J. H., Adaptation in Natural and Artificial System,The University of Michigan Press,1975.
Kirkpartrick, S.,C. D. Gelatt, Jr., and M. P. Vevvhi, “ Optimization Simulated Annealing,” Science, Vol. 220, pp. 671-680, 1983.
Kohl, N. and O. Madsen, “An Optimization Algorithm for The Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation,” Operations Research, Vol. 45, No. 3, pp. 395-406, 1997.
Kuehn, A. and Hamburger, M. J., “A Heuristic Program for Locating Warehouse,” Management Science, Vol. 19, pp. 643-666, 1963.
Lima, C. M. R. R., M. C. Goldbarg, E. F. G. Goldbarg, “A Memetic Algorithm for the Hetergeneous Fleet Vehicle Routing Problem,” Electronic Notes in Discrete Mathematics, Vol. 18, pp. 171-179, 2004.


Lin, C. K. Y. and R. C. W. Kwok, “Multi-Objective Metahuristics for a Location-Routing Problem with Multiple Use of Vehicles on Real Data and Simulated Data,” European Journal of Operational Research, In Press, Corrected Proof, Available online 10 August 2005.
Mole, R. and S. Jameson, “A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion,” Operation Research Quarterly, Vol. 27, pp. 503-511, 1976.
Osman, I. H., “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 41, pp. 421-451, 1993.
Osman, I. H. and N. Christofides, “Capacitated Clustering Problems by Hybrid Simulated Annealing and Tabu Search,” International Transactions in Operational Research, Vol. 1, No. 3, pp. 317-336, 1994.
Osman, I. H.and J. P. Kelly, “Meta-Heuristics：An Overview,” Meta-Heuristics,: Theory and applications, pp. 1-21, 1996.
Perl, J. and M. S. Daskin, “A warehouse location-routing problem,” Transportation Research B, Vol. 19, pp. 381-396, 1985.
Pirkul, H. and V. Jayaraman, “A Multi-Commodity, Multi-Plant, Capacitated Facility Location Problem: Formulation and Efficient Heuristic Solution,” Computers & Operations Research, Vol. 25, No. 10, pp. 869-878, 1998.
Raft, O. M., “A Modular Algorithm for an Extended Vehicle Scheduling Problem,” European Journal of Operational Research, Vol. 11, pp. 67-76, 1982.
Renaud, J., G.. Laporte and F. F. Boctor, “A Tabu Search Heuristics for the Multi-Depot Vehicle Routing Problem,” Computers & Operations Research, Vol. 23 , pp. 229-235, 1996.
Rolland, E., D. A. Schilling and J. R. Current, “An Efficient Tabu Search Procedure for the P-Median Problem,” European Journal of Operational Research, Vol. 127, pp. 329-342, 1996.

Salhi, S. and M. Sari, “A Multi-Level Composite Heuristic for the Multi-Depot Vehicle Fleet Mix Problem,” European Journal of Operational Research, Vol. 103, pp. 95-112, 1997.
Schmitt, L. J., An Empirical Computational Study of Genetic Algorithms to Solve Order Based Problems：An Emphasis on TSP and VRPTC, Ph.D. Dissertation, Fogelman College of Business and Economics, University of Memphis,1994.
Schmitt, L. J., “An Evaluation of a Genetic Algorithmic Approach to the Vehicle Routing Problem,” Working Paper, Department of Information Technology Management, Christian Brothers University, Memphis, 1995.
Tillman, F. A., “The Multiple Terminal Delivery Problem with Probabilistic Demands,” Transportation Science, Vol. 3, pp. 192-204, 1969.
Tragantalerngask, S., J. Holt and M. Ronnqvist, “Lagrangian Heuristics for the Two-Echelon, Single-Source, Capacitated Facility Location Problem,” European Journal of Operational Research, Vol. 102, pp. 611-625, 1997.
Tuzun, D. and L. I. Burke, “A Two-Phase Tabu Search Approach to the Location Routing Problem,” European Journal of Operational Research, Vol. 116, pp. 87-99, 1999.
Van Roy, T. J. and Erlenkotter, D., “A Dual-Based Procedure for Dynamic Facility Location,” Management Science, Vol. 28, No.10, pp. 1091-1105, 1982.
Wren A. and A. Holiday, “Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Point,” Operational Research Quarterly, Vol. 23, pp. 333-344, 1972.