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

Hybrid Global Search Algorithm Based on Particle Swarm Optimization for Concave Cost Minimum Cost Network Flow Problems

李旺蒼(Wang-Tsang Lee)

指導教授 ： 顏上堯

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

摘要

傳統上，最小成本網路流動問題的運送成本常以線性方式來定義，藉以簡化問題的複雜度。在實務上，貨物運送的單位成本常隨數量的增加而遞減，其成本函數曲線為凹形。近期在求解含凹形節線成本之特殊最小成本網路流動問題上，有學者以新近鄰近搜尋法求解問題，達到較大範圍的搜尋方式，期能找到較優於傳統啟發解法的解。然而，此等鄰近搜尋法，容易面臨退化的問題，且是否可快速探尋全域，則不得而知。因此近期有學者發展類遺傳演算法與類螞蟻族群演算法以求解含凹形節線成本最小成本網路流動問題。另外，新近的粒子群最佳化演算法目前在各領域的問題求解上效果頗佳，甚至有發現較遺傳演算法為佳，但尚未發現有應用於含凹形節線成本最小成本網路流動問題。緣此，本研究針對含凹形節線成本之最小成本網路流動問題，以粒子群最佳化演算法之搜尋概念為基礎，並結合遺傳演算法、門檻值接受法與凹形成本網路啟發解法之特點，以節線及路徑為基礎發展兩種不同之混合式全域搜尋法，以有效的求解含凹形節線成本之最小成本網路流動問題。
本研究演算法的設計如下：在初始解的產生上，以隨機方式及配合凹形成本網路特性發展二初始解法，產生初始的粒子群。在可行解的產生上：以節線為基礎之演算法，以前ㄧ回合伸展樹為基礎，引進遺傳演算法之輪盤法選擇策略，發展數種方式以挑選節線加入伸展樹，並透過流量推擠法產生可行伸展樹；至於以路徑為基礎之演算法，則發展數種供給點指派之順序選擇策略及供需節點對之路徑選取方式，以重新指派供需節點間的運送量，並藉由流量推擠法以形成可行伸展樹。另外再發展路徑集合更新策略，以加入較佳伸展樹中新的供需節點路徑。另外，在粒子的速度更新法則上，參考引入連續型粒子群最佳化之慣性權重值（w）與可行伸展樹之特性，發展與以往不同的速度演算法則。在全體與個體最佳解的更新方式上，則引入門檻值接受法之求解機制。最後在搜尋的深度上，結合區域搜尋能力較強的鄰近搜尋法，以提升演算績效。最後，為測試本研究演算法在不同規模及參數的網路問題之求解績效，本研究設計一隨機網路產生器，產生大量的隨機網路，在個人電腦上以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. Recently, some advanced neighborhood search algorithms have been used to solve concave cost network problems. However, they were easily encountered degeneracy problems or confined to local regions, resulting in decreased solution efficiency. Recently, there has been research adopting the genetic algorithm (GA) and the ant colony system algorithm (ACS) for solving concave cost network problems, and obtaining better solutions than some neighborhood search algorithms. The particle swarm optimization algorithm (PSO), a global search algorithm, has led to good results in many applications. In some applications, PSO was even more effective than GA. Since there has not yet been any research applying PSO to minimum concave cost network flow problems, we employ PSO, coupled with the techniques of GA　and TA, to develop two global search algorithms for efficiently solving minimum concave cost network flow problems.
The algorithms are designed as follows: First, two heuristics for generating the initial solutions are proposed: one is the random initial solution algorithm and the other is the concave cost initial solution algorithm. Then, two methods for generating feasible solutions are proposed: In the arc-based method, we employed the roulette wheel method in GA to design several ways for selecting and adding arcs into the spanning tree obtained from the previous iteration. In the path-based method, we developed several methods to select supply/demand node pair paths to form a new feasible solution. The flow augmentation algorithm is then used to adjust the non-spanning trees to become feasible spanning trees for both methods. In addition, for the path-based method we developed a strategy for updating the path set by incorporating the new paths from better feasible spanning trees. Followed by the two steps, we developed a new rule for updating the particle velocities, incorporating the inertia weight method and the spanning tree’s characteristics. We also employed the TA technique for updating the feasible solutions. To enhance the depth search we employed a neighborhood search technique. Finally, to evaluate our algorithms we designed a network generator to generate a sufficient number of problem instances. The C++ computer language was used to code all the necessary programs and the tests was performed on personal computers. To evaluate our algorithms, we also tested the recently designed TA, GDA, GA and ACS that solve minimum concave cost network flow problems.

並列關鍵字

global search ； concave arc cost ； particle swarm optimization ； genetic algorithm ； minimum cost network flow problem

參考文獻

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

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

16. 顏上堯、陳建榮、湯慶輝，「含凹形節線成本最小成本轉運問題鄰近搜尋法之研究」，運輸計劃季刊，第三十三卷，第二期，第277-306頁（2004）。

7. 張榮芳，「電力用戶負載歸類及整合」，國立中山大學電機工程研究所博士論文（2001）。

9. 葉麗雯，「供應商產能有限及價格折扣下多產品多供應商最佳化採購決策」，元智大學工業工程與管理研究所碩士論文（2002）。