以和諧演算法為基礎之混合全域搜尋法求解最小凹型成本轉運問題

HYBRID GLOBAL SEARCH ALGORITHM BASED ON HAMONY SEARCH OPTIMIZATION FOR MINIMUM CONCAVE COST TRANSSHIPMENT PROBLEMS

顏上堯(ShangyaoYan)；林至康(Chih-Kang Lin)；劉向邦(Xiang-Bang Liu)

和諧搜尋演算法 ； 凹形節線成本 ； 最小成本網路流動問題 ； 全域搜尋 ； Harmony search ； Concave arc cost ； Minimum cost network flow problem ； Global search

運輸計劃季刊

45卷3期（2016 / 09 / 30）

189 - 215

繁體中文

在實務上，貨物運送的單位成本常隨數量的增加而遞減，其成本函數曲線為凹形，而此類問題可定式為含凹形節線成本之最小成本網路流動問題，但此問題屬於NP-hard問題，故難在有限時間內求得大型問題的最佳解。新近的和諧搜尋演算法目前在各領域的問題求解上效果頗佳，但尚未發現有應用於含凹形節線成本最小成本網路流動問題，緣此，本研究以和諧搜尋演算法為基礎，並結合粒子群演算法、螞蟻族群演算法、門檻值接受法與凹形成本網路啟發解法之特點，以節線及路徑為基礎發展一混合式全域搜尋法，以有效求解含凹形節線成本之最小成本網路流動問題。為測試本研究演算法在不同規模及參數的網路問題之求解績效，本研究設計一隨機網路產生器產生大量隨機網路，並測試遺傳演算法、門檻值接受法、大洪水法、類螞蟻族群演算法及粒子群演算法，以評估本研究演算法之求解績效。測試結果顯示本研究演算法求解品質良好，可提供實務界求解此類網路運送問題之參考。

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, causing the transshipment problem an NP-hard problem. The harmony search (HS), a global search algorithm, has led to good results in many applications. 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 a global search algorithms for efficiently solving minimum concave cost network flow problems. Finally, to evaluate our algorithms we designed a network generator to create a sufficient number of problem instances. 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.

1. 顏上堯、李旺蒼、施佑林(2007)。路徑基礎類粒子群最佳化演算法於求解含凹形節線成本最小成本轉運問題之研究。運輸計劃季刊，36(3)，393-423。
   連結：
2. Afkhami, S.,Ma'rouzi, O. R.,Soleimani, A.(2013).A Binary Harmony Search Algorithm for Solving the Maximum Clique Problem.International Journal of Computer Applications,69(12),38-43.
3. Ahuja, R. K.,Maganti, T. L.,Orlin, J. B.(1993).Network Flows, Theory, Algorithms, and Applications.Englewood Cliffs:Prentice Hall.
4. Charon, I.,Hurdy, O.(1993).The Noising Method: A New Method for Combinatorial Optimization.Operations Research Letters,14,133-137.
5. Dorigo, M.,Gambardella, L. M.(1996).A Study of Some Properties of Ant-Q.Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving from Nature,Berlin:
6. Dueck, G.(1993).New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel.Journal of Computational Physics,104,86-92.
7. Dueck, G.,Scheuer, T.(1990).Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing.Journal of Computational Physics,90,161-175.
8. Gallo, G.,Sandi C.,Sodini, C.(1980).An Algorithm for the Min Concave Cost Flow Problem.European Journal of Operation Research,4,248-255.
9. Gallo, G.,Sandi, C.(1979).Adjacent Extreme Flows and Application to Min Concave Cost Flow Problems.Networks,9,95-121.
10. Garey, M. R.,Johnson, D. S.(1979).Computers and Intractability: A Guide to the Theory of NP-Completeness.San Francisco:WH Freeman and Co..
11. Geem, Z. W.,Kim, J. H.,Loganathan, G. V.(2001).A New Heuristic Optimization Algorithm: Harmony Search.Simulation,76(2),60-68.
12. Geem, Z. W.,Lee, K. S.,Lee, S. H.,Bae, K. W.(2005).The Harmony Search Heuristic Algorithm for Discrete Structural Optimization.Engineering Optimization,37(7),663-684.
13. Geem, Z. W.,Tseng, C. L.,Park, Y.(2005).Harmony Search for Generalized Orienteering Problem: Best Touring in China.Advances in Natural Computation,3612,741-750.
14. Glover, F.(1990).Tabu Search- Part II.ORSA Journal on Computing,2(1),4-32.
15. Glover, F.(1989).Tabu Search, Part I.ORSA Journal on Computing,1(3),190-206.
16. Goldberg, D. E.(1989).Genetic Algorithms in Search, Optimization, and Machine Learning.Reading, MA:Addison-Wesley.
17. Gu, J.,Huang, X.(1994).Efficient Local Search with Search Space Smoothing: A Case Study of the Traveling Salesman Problem (TSP).IEEE Transaction on Systems, Man and Cybernetics,24,728-739.
18. Hansen, P.,Mladenovic, N.(2007).Variable Neighborhood Search.Computers and Operations Research,24,1097-1100.
19. Hosseini, S. D.,Shirazi, M. A.,Taghi Fatemi Ghomi, S. M.(2014).Harmony Search Optimization Algorithm for a Novel Transportation Problem in a Consolidation Network.Engineering Optimization,46,1538-1552.
20. Kennedy, J.,Spears, W.(1998).Matching Algorithms to Problems: An Experimental Test of the Particle Swarm and Some Genetic Algorithms on the Multimodal Problem Generator.IEEE World Congress on Computational Intelligence
21. Kirkpatrick, S.,Gelatt, C. D.,Vecchi, M. P.(1983).Optimization by Simulated Annealing.Science,220,671-680.
22. Nourie, F. J.,Guder, F.(1994).A Restricted-Entry Method for a Transportation Problem with Piecewise-Linear Concave Cost.Computer and Operations Research,21,423-733.
23. Osman, I. H.,Kelly, J. P.(1996).Meta-Heuristics: An Overview.Meta-Heuristics: Theory and Applications,Boston:
24. Rech, P.,Barton, L. G.(1970).A Non-Convex Transportation Algorithm.Applications of Mathematical Programming Techniques,New York:
25. Reeves, C. R.(1994).Improving the Efficiency of Tabu Search for Machine Sequencing Problems.Journal of the Operation Research Society,44(4),375-382.
26. Wang, L.,Pan, Q. K.,Tasgetiren, M. F.(2010).Minimizing the Total Flow Time in a Flow Shop with Blocking by Using Hybrid Harmony Search Algorithms.Expert Systems with Applications,37(12),7929-7936.
27. Yan, S.,Juang, D. H.,Chen, C. R.,Lai, W. S.(2004).Global and Local Search Algorithms for Concave Cost Transshipment Problems.Journal of Global Optimization,33(1),123-156.
28. Yan, S.,Luo, S. C.(1999).Probabilistic Local Search Algorithms for Concave Cost Transportation Network Problems.European Journal of Operational Research,117,511-521.
29. Yan, S.,Luo, S. C.(1998).A Tabu Search-based Algorithm for Concave Cost Transportation Network Problems.Journal of the Chinese Institute of Engineers,21,327-335.
30. Yan, S.,Shih, Y. L.,Lee, W. T.(2011).A Particle Swam Optimization-Based Hybrid Algorithm for Minimum Concave Cost Network Flow Problems.Journal of Global Optimization,49(4),539-559.
31. Yan, S.,Shih, Y. L.,Wang, C. L.(2010).An Ant Colony System-Based Hybrid Algorithm for Square Root Concave Cost Transshipment Problems.Engineering Optimization,42(11),983-1001.
32. Yan, S.,Young, H. F.(1996).A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling.Transportation Research,30A,379-398.
33. Zangwill, W. I.(1968).Minimum Concave Cost Flows in Certain Networks.Management Science,14,429-450.
34. 李亮、遲世春、褚雪松(2006)。基於修復策略的改進和聲搜索演算法求解土坡非圓臨界滑動面。中國岩土力學，27(10)，1714-1718。
35. 李亮、遲世春、鄭榕明、林皋(2007)。一種新型遺傳演算法及其在土坡任意滑動面確定中的應用。水利學報，38(2)，157-162。
36. 韓復華、卓裕仁(1996)。門檻接受法、成本擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析。運輸學刊，9(3)，103-129。
37. 韓復華、陳國清、卓裕仁(1997)。成本擾動法在TSP 問題之應用。中華民國第2 屆運輸網路研討會論文集