臺灣博碩士論文加值系統

資訊科技日新月異，不斷改變商品的交易模式，從實體商店消費模式進而轉至利用網路線上購物，讓物流業者去配送實體商品交給顧客，而配送之過程往往是物流業者備受重視的問題。近年來許多學者致力於車輛途程問題(Vehicle Routing Problem,VRP)演算法的發展，以求改善物流配送的距離與成本。由於VRP問題是屬於非完全多項式(NP-Complete)問題，本論文提出一個新的以群聚概念為基礎的蟻群最佳化技術(Ant Colony Optimization, ACO)，稱為群聚概念螞蟻群最佳化技術( Clustering-based Ant Colony Optimization, CACO)主要是以自然界模擬螞蟻尋食之方式來建構路線模式，求解具車輛容量限制之車輛途程問題(The Vehicle Routing Problem under Capacity, CVRP)。先以三角形最小面積合併節點建構初始路線，再以蟻群最佳化演算法(Ant Colony Optimization, ACO)做為研究的核心主軸，並且以2-opt交換法做鄰近解搜尋，直至無法改善為止。

With the progress of information technology, business models change rapidly. The models shift from shopping in physical stores to shopping on the Internet and products are delivered to customers by logistic agencies. Logistic agencies put much emphasis on delivery cost because it relates significantly to their competitive advantage. Vehicle routing problem (VRP) focuses on distribution problems about designing vehicle routes to serve those customers, and it aims to reduce the delivery cost and deliver products to customers correctly and quickly. VRP is also a NP-Complete problem. In this thesis, we propose a new clustering concept for solving VRP and the algorithm is called Clustering-based Ant Colony Optimization (CACO). We construct preference paths by simulating ant’s ways of seeking for food to solve Vehicle Routing Problem under Capacity (CVRP). First, nodes which form smallest triangle will be combined as initial paths. Second, we implement ACO as a core approach for determine optimal routes and 2-opt exchange is used to search optimal route.

摘要 I
Abstract III
誌謝 V
目錄 VI
圖表索引 IX
第1章 緒論 1
1.1 研究動機與背景 1
1.2 研究目的 2
1.3 研究限制 2
1.4 研究流程與架構 3
1.5 研究步驟 4
1.6 論文架構 5
第2章 文獻探討 6
2.1螞蟻群聚最佳化演算法(The Ant Colony Optimization) 6
2.1.1 螞蟻群聚(Ant Colonies) 6
2.1.2 螞蟻系統(The Ant System) 8
2.1.3 螞蟻群聚系統(The Ant Colony System) 10
2.1.4 螞蟻群聚最佳化演算法(The Ant Colony Optimization) 11
2.2途程問題之分類 13
2.2.1 車輛途程問題 13
2.2.2 車輛途程(VRP)問題之目標分類 14
2.2.3 車輛途程(VRP)問題之求解方法分類 14
第3章 研究方法 20
3.1問題定義 20
3.1.1 CACO演算法執行步驟 22
3.1.2 三角形面積建構路線規則 24
3.1.3 候選名單 28
3.1.4 費洛蒙表(Pheromone Table) 29
3.1.5 螞蟻選擇路徑策略 29
3.1.6 區域更新(Local Updating) 31
3.1.7 鄰近解搜尋(Local Search) 31
3.1.8 全域更新(Global Updating) 31
3.1.9 CACO步驟與演算法 32
第4章 實驗設計與結果 35
4.1參數設計 35
4.2 實驗數據 35
4.2.1 資料集Case 1 36
4.2.2 資料集Case 2 37
4.2.3 資料集Case 3 39
4.2.4 資料集Case 4 40
4.2.5 資料集Case 5 41
4.2.6 時間成本資料集Case 1 42
4.2.7 時間成本資料集Case 2 43
4.2.8 時間成本資料集Case 3 43
4.2.9 時間成本資料集Case 4 43
4.2.10 時間成本資料集Case 5 44
4.3 各演算法總距離成本 44
4.4 各演算法時間成本 47
第5章 車輛途程應用 50
5.1 系統架構 51
5.1.1 Server端 51
5.1.2 Client端 53
5.1.3 地圖製作 54
5.1.4 系統功能展示 55
第6章 結論 64
6.1 結論與討論 64
6.2 未來研究方向 66
參考文獻 67
作者簡介 70

[1]李文專，以一個改良式螞蟻演算法解決網路通訊中具有品質服務之群播路由與拓樸設計之問題，屏東科技大學，碩士論文，2005。
[2]敖君瑋，禁制搜尋法於軟性時窗限制之車輛問題研究，元智大學，碩士論文，1999。
[3]莊志諒，配送網路之設計研究，交通大學交通運輸研究所，碩士論文，1988。
[4]廖亮富，含時間窗限制多部車車輛途程問題解算之研究，元智大學，碩士論文，1998。
[5]羅敏華，以蟻群最佳化演算法於載重限制之車輛途程問題的研究，元智大學，碩士論文，2003。
[6]Bella, J.E., McMullen P.R., “Ant colony optimization techniques for the vehicle routing problem”, Advanced Engineering Informatics, 18:41-48, 2004.
[7]Bodin, L., Berman, L., “Routing and Scheduling of school buses by computer”, Transportation Science, 13(2):113-129, 1979.
[8]Bullnheimer, B., Hartl, R.F., Strauss, C., “Applying the Ant System to the Vehicle Routing Problem”, In I. Osman, S. Voss, S. Martello, and C. Roucairol, editors, Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization , pp. 109-120, 1998.
[9]Bullnheimer, B., Hartl, R.F., Strauss, C., “An Improved Ant System Algorithm for The Vehicle Routing Problem”, Technical Report POM-10/97, Institute of Management Science, University of Vienna, Austria, 1997.
[10]Christofides, N.A., Mingozzi, P.Toth, “The Vehicle Routing Problem”, Combinatorial Optimization, pp. 325-338, 1979.
[11]Clarke, G., Wright, J.W., “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, 12:568-581, 1974.
[12]Croes, G.A., “A Method for Solving Traveling-Salesman Problems”, Operations Research, 6:791-812, 1958.
[13]Dorigo, M., “Learning by probabilistic Boolean networks,” IEEE World Congress on Computational Intelligence, IEEE International Conference on Neural Networks, 2:887-891, 1994.
[14]Dorigo, M. , Bonabeau, E., Theraulaz, G., “Ant Alogrithms and Stigmergy”, Future Generation Computer Systems, 16(8):851-871, 2000.
[15]Dorigo, M., Caro, G.D., “The Ant Colony Optimization Meta-Heuristic”, New Ideas in Optimization, McGraw-Hill, pp. 11-32, 1999.
[16]Dorigo M., Gambardella, L.M., “Ant Colony System: A Cooperative Leargin Approach to The Traveling Salesman Problem”, IEEE Transactions on Evolutionary Computation, 1(1):53-66, 1997.
[17]Dorigo, M., Gambardella, L.M., “Ant Colonies for the Traveling Salesman Problem”, BioSystems, pp. 73-81, 1997.
[18]Dorigo, M., Maniezzo, V., and Colorni, A., “Ant System: Optimization by a Colony of Cooperating Agents”, IEEE Transactions on System, Man and Cybernetics-Part B, 26(1):29-42, 1996.
[19]Gambardella, L.M., Dorigo, M., “Solving Symmetric and Asymmetric TSPs by Ant Colonies”, IEEE International Conference on Evolutionary Computation, pp. 622-627, 1996.
[20]Gendreau, M., Hertz,A., Laporte, G., “A Tabu Search Heuristic for the Vehicle Routing Problem”, Management Science, 40:1276-1290, 1994.
[21]Gillett, B., Johnson, J., “Multi-Terminal Vehicle-Dispatch Algorithm”, Omega, 4:711-718, 1976.
[22]Gillett, B.E., Miller, L.R., “Aheuristic Algorithm for the Vehicle Dispatch Problem”, Operations Research, 22:340-349, 1974.
[23]Lin, S., Kernighan, B.W. “An effective heuristic algorithm for the TSP”, Operations Research, pp. 498-516, 1973.。
[24]Lu, G., Liu, Z., “Multicast Routing based on Ant-algorithm with Delay and Delay Variation Constraints”, The 2000 IEEE Asia-Pacific Conference on Circuits and Systems, pp. 243-246, 2000.
[25]Mole, R.H., Jameson, S.R., “A sequential route-building algorithmemploying a generalised savings criterion”, Operations Research, 27:503-511, 1976.
[26]Reimann, M., Stummer, M., Doerner, K., “A Savings Based Ant System for the Vehicle Routing Problem“, POM Working Paper 03/2002, Department of Production and Operations Management, University of Vienna, 2002.
[27]Robuste F., Daganzo C.F., Souleyrette R., “Implementing Vehicle Routing Models“, Transporation Research, 24:263-286, 1990.
[28]Toth P., Vigo D., “The Vehicl Routing Problem”, Siam, pp. 121-125, 2001.
[29]Wang, Y., Xie, J., “Ant Colony Optimization For Multicast Routing”, T　he 2000 IEEE Asia-Pacific Conference on Circuits and Systems, pp. 54-57, 2000.