以和諧搜尋演算法為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究

Hybrid Global Search Algorithm Based on Harmony Search for Concave Cost Minimum Cost Network Flow Problems

劉向邦(Xiang-Bang Liu)

指導教授 ： 顏上堯

國立中央大學/工學院/土木工程學系/碩士(2008年)

摘要

傳統在最小成本轉運問題定式下，常以線性方式來定義運送成本，藉以簡化問題的複雜度。在實務上，貨物運送的單位成本常隨數量的增加而遞減，其成本函數曲線為凹形。以往有不少含凹形成本節線之研究，但侷限於不同之特殊網路且方法屬傳統區域搜尋法或傳統啟發解法，近期雖有學者開始以新近鄰近搜尋法求解簡化的運輸問題，以達到較大範圍的搜尋方式，期能找到較優於傳統啟發解法之解，卻忽略運輸網路常見的轉運問題。因此近期有學者發展類遺傳演算法、類螞蟻族群演算法及粒子群演算法以求解含凹形節線成本最小成本網路流動問題。另外，新近的和諧搜尋演算法目前在各領域的問題求解上效果頗佳，甚至有發現較遺傳演算法為佳，但尚未發現有應用於含凹形節線成本最小成本網路流動問題，緣此，本研究針對含凹形節線成本之最小成本網路流動問題，以和諧搜尋演算法之搜尋概念為基礎，並結合粒子群演算法、螞蟻族群演算法、門檻值接受法與凹形成本網路啟發解法之特點，以節線及路徑為基礎發展一混合式全域搜尋法，期能有效的求解含凹形節線成本之最小成本網路流動問題。
在求解方法上，本研究以和諧搜尋演算法為基礎，利用和諧搜尋演算法中以和弦記憶空間為母體之選擇機制之全域搜尋法與調音機制之區域搜尋法重新組成新可行解，並加入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.

並列關鍵字

concave arc cost ； global search ； local search ； minimum cost network flow problem ； hamony search

參考文獻

3. 田佳芸，「變動鄰域搜尋法於雙目標平行機台排程問題之研究」，元智大學工業工程與管理學系碩士論文(2006)。

25. 韓復華、楊智凱、卓裕仁，「應用門檻接受法求解車輛路線問題之研究」，運輸計畫季刊，第二十六卷，第二期，第253-280頁(1997)。

26. 顏上堯、周容昌、李其灃，「交通建設計畫評選模式及其解法之研究─以中小型交通建設計畫的評選為例」，運輸計畫季刊，第三十一卷，第一期(2002)。

8. 李岳倫，「以螞蟻識別系統進行零件分群」，大同大學資訊經營所碩士論文(2004)。

5. 李旺蒼，「以粒子群最佳化為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究」，中央大學土木工程研究所碩士論文(2006)。