以和諧搜尋演算法為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究; Hybrid Global Search Algorithm Based on Harmony Search for Concave Cost Minimum Cost Network Flow Problems

NCUIR > Engineering College > Graduate Institute of Civil Engineering > Electronic Thesis & Dissertation > Item 987654321/1279

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/1279

Title:	以和諧搜尋演算法為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究;Hybrid Global Search Algorithm Based on Harmony Search for Concave Cost Minimum Cost Network Flow Problems
Authors:	劉向邦;Xiang-Bang Liu
Contributors:	土木工程研究所
Keywords:	和諧搜尋演算法;凹形節線成本;區域搜尋;全域搜尋;最小成本網路流動問題;concave arc cost;global search;local search;minimum cost network flow problem;hamony search
Date:	2008-06-23
Issue Date:	2009-09-18 17:25:40 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	傳統在最小成本轉運問題定式下，常以線性方式來定義運送成本，藉以簡化問題的複雜度。在實務上，貨物運送的單位成本常隨數量的增加而遞減，其成本函數曲線為凹形。以往有不少含凹形成本節線之研究，但侷限於不同之特殊網路且方法屬傳統區域搜尋法或傳統啟發解法，近期雖有學者開始以新近鄰近搜尋法求解簡化的運輸問題，以達到較大範圍的搜尋方式，期能找到較優於傳統啟發解法之解，卻忽略運輸網路常見的轉運問題。因此近期有學者發展類遺傳演算法、類螞蟻族群演算法及粒子群演算法以求解含凹形節線成本最小成本網路流動問題。另外，新近的和諧搜尋演算法目前在各領域的問題求解上效果頗佳，甚至有發現較遺傳演算法為佳，但尚未發現有應用於含凹形節線成本最小成本網路流動問題，緣此，本研究針對含凹形節線成本之最小成本網路流動問題，以和諧搜尋演算法之搜尋概念為基礎，並結合粒子群演算法、螞蟻族群演算法、門檻值接受法與凹形成本網路啟發解法之特點，以節線及路徑為基礎發展一混合式全域搜尋法，期能有效的求解含凹形節線成本之最小成本網路流動問題。在求解方法上，本研究以和諧搜尋演算法為基礎，利用和諧搜尋演算法中以和弦記憶空間為母體之選擇機制之全域搜尋法與調音機制之區域搜尋法重新組成新可行解，並加入PSO速度更新策略、ACS費洛蒙更新策略、TA與凹形成本網路啟發解法之演算特色，針對凹形成本網路流動問題之特性，發展一套適合凹形節線成本轉運問題之類和諧搜尋演算法。最後，為測試本研究演算法在不同規模及參數的網路問題之求解績效，本研究設計一隨機網路產生器，產生大量隨機網路，在個人電腦上以C++語言撰寫所有相關的電腦程式，並測試新近發展之遺傳演算法、門檻值接受法、大洪水法、類螞蟻族群演算法及粒子群演算法，以評估本研究演算法之求解績效，進而提供實務界求解此類實際的網路運送問題之參考。測試結果顯示，本研究演算法求解品質良好。 Traditionally, the minimum cost transshipment problems were simplified as linear cost problems in order to reduce problem complexity. In practice, the unit cost for transporting freight usually decreases as the amount of freight increases. Hence, in actual operations the transportation cost function can usually be formulated as a concave cost function. Great efforts have been devoted to the development of solution algorithms. However, they were confined to specical transportation networks. Besides, their methods were focused on local search algorithms or traditional heuristics. Recently, researchers began to use advanced neighborhood search algorithms to solve concave cost bi-partite transportation network problems to enlarge search area and find near-optimal solutions. This type of research, however, neglected flow transfers in transportation networks. Recently, there has been research adopting the genetic algorithm (GA), the ant colony system algorithm (ACS) and the particle swarm optimization algorithm (PSO) for solving concave cost network problems, and obtaining better solutions than some neighborhood search algorithms do. The harmony search (HS), a global search algorithm, has led to good results in many applications. In some applications, HS was even more effective than GA. Since there has not yet been any research applying HS to minimum concave cost network flow problems, we employ HS, coupled with the techniques of PSO, ACS and TA, to develop one global search algorithms for efficiently solving minimum concave cost network flow problems. In the solution method, we take the harmony search as the foundation, use a global search which is harmony memory consideration and a local search which is Pitch Adjusting to compose the new feasible solution, we also join the velocity update rules in PSO, the pheromone update rules in ACS, TA and the concave cost initial solution algorithm, we develop a analogous harmony search which is fitting the minimum cost transshipment problems with concave costs. Finally, to evaluate our algorithms we designed a network generator to create a sufficient number of problem instances. The C++ computer language was used to code all the necessary programs and the test was performed on personal computers. To evaluate our algorithm, we also tested the recently designed TA, GDA, GA, ACS and PSO that solve minimum concave cost network flow problems. The results show that the developed algorithms performed well in the tests.
Appears in Collections:	[Graduate Institute of Civil Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...