路徑基礎類粒子群最佳化演算法於求解含凹形節線成本最小成本轉運問題之研究

A PATH-BASED ANALOGOUS PARTICLE SWARMOPTIMIZATION ALGORITHM FOR MINIMUM COST NETWORK FLOW PROBLEMS WITH CONCAVE ARC COSTS

本研究針對含平方根凹形節線成本之最小成本網路流動問題，以粒子群最佳化演算法之搜尋概念為基礎，並結合遺傳演算法、門檻值接受法與凹形成本網路啟發解法之技術，發展一以路徑為基礎之混合式全域搜尋法，以有效的求解問題。為評估本演算法之求解績效，本研究隨機產生多個網路問題，並以C++ 語言撰寫所有相關的電腦程式，進行測試分析。測試結果顯示本演算法比新近發展之鄰近搜尋演算法及遺傳演算法更能有效地求解含平方根凹形節線成本之最小成本網路流動問題。

In this research, a particle swarm optimization algorithm was employed, coupled with the techniques of a genetic algorithm, and threshold acceptance method and concave cost network heuristics, to develop a path-based global search algorithm for efficiently solving minimum cost network flow problems with square root concave arc costs. To evaluate the proposed algorithm, several network flow problems are randomly generated. C++ is used to code all the necessary programs for the tests. The results indicate that the proposed algorithm is more effective than recently designed local search algorithms and genetic algorithms for solving minimum cost network flow problems with square root concave arc costs.