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

A Path-Based Analogous Particle Swarm Optimization Algorithm for Minimum Cost Network Flow Problems with Concave Arc Costs

10.6402/TPJ.200709.0393

顏上堯(Shang-Yao Yan)；李旺蒼(Wang-Tsang Lee)；施佑林(Yu-Lin Shih)

凹形節線成本 ； 網路流動問題 ； 粒子群最佳化演算法 ； 遺傳演算法 ； 門檻值接受法 ； Concave arc cost ； Network flow problem ； Particle swarm optimization ； Genetic algorithm ； Threshold accepting

運輸計劃季刊

36卷3期（2007 / 09 / 30）

393 - 423

繁體中文

本研究針對含平方根凹形節線成本之最小成本網路流動問題，以粒子群最佳化演算法之搜尋概念為基礎，並結合遺傳演算法、門檻值接受法與凹形成本網路啟發解法之技術，發展一以路徑為基礎之混合式全域搜尋法，以有效的求解問題。為評估本演算法之求解績效，本研究隨機產生多個網路問題，並以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.

1. 顏上堯、陳建榮、湯慶輝(2004)。含凹形節線成本最小成本轉運問題鄰近搜尋法之研究。運輸計劃季刊，33(2)，277-306。
   連結：
2. Ahuja, R. K.,Magnanti, T. L.,Orlin, J. B.(1993).Network Flows, Theory, Algorithms, and Applications.Englewood Cliffs:Prentice Hall.
3. Amiri, A.,Pirkul, H.(1997).New Formulation and Relaxation to Solve a Concave Cost Network Flow Problem.Journal of the Operational Research Society,48,278-287.
4. Balakrishnan, A.,Graves S. C.(1989).A Composite Algorithm for a Concave-Cost Network Flow Problem.Networks,19,175-202.
5. Blumenfeld, D. E.,Burns, L. D.,Diltz, J. D.,Daganzo, C. F.(1985).Analyzing Trade-offs Between Transportation, Inventory, and Production Costs on Freight Network.Transportation Research,19,361-380.
6. Boyd, R.,Richerson, P. J.(1985).Culture and the Evolutionary Process.Chicago:the University of Chicago Press.
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. Dukwon, K.,Panos, M.(2000).Dynamic Slope Scaling and Trust Interval Techniques for Solving Concave Piecewise Linear Network Flow Problems.Networks,35,216-222.
9. Eberhart, R. C.,Kennedy, J.(1995).Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Piscataway, NJ, Nagoya, Japan:IEEE Service Center.
10. Eberhart, R. C.,Kennedy, J.(1995).Particle Swarm Optimization.Proceedings of IEEE International Conference on Neural Networks
11. Gallo, G.,Sandi C.,Sodini, C.(1980).An Algorithm for the Min Concave Cost Flow Problem.European Journal of Operation Research,4,248-255.
12. Gallo, G.,Sandi, C.(1979).Adjacent Extreme Flows and Application to Min Concave Cost Flow Problems.Networks,9,95-121.
13. Garey, M. R.,Johnson, D. S.(1979).Computers and Intractability: A Guide to the Theory of NP-Completeness.San Francisco:WH Freeman and Co..
14. Glover, F.(1989).Tabu Search, Part I.ORSA Journal on Computing,1(3),190-206.
15. Glover, F.,Laguna, M.(1997).Tabu Search.Massachusetts:Kluwer Academic.
16. Goldberg, D. E.(1989).Genetic Algorithms in Search, Optimization, and Machine Learning.Reading MA:Addison-Wesley.
17. Guisewite, G. M.,Pardalos, P. M.(1993).A Polynomial Time Solvable Concave Network Flow Problems.Networks,23,143-147.
18. Jordan, W. C.(1986).Scale Economies on Multi-Commodity Networks.Operating Systems Research Dept., GM Research Laboratories.
19. Kennedy, J.,Eberhart, R. C.(1997).A Discrete Binary Version of the Particle Swarm Optimization.Proceedings of IEEE International Conference on Neural Networks
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,74-77.
21. Kirkpatrick, S.,Gelatt, C. D.,Vecchi, M. P.(1983).Optimization by Simulated Annealing.Science,220,671-680.
22. Kuhn, H. W.,Baumol, W. J.(1962).An Approximate Algorithm for the Fixed-Charge Transportation Problem.Naval Res. Logistics Quarterly,9,1-16.
23. Larsson, T.,Migdalas, A.,Ronnqvist, M.(1994).A Lagrangian Heuristic for the Capacitated Concave Minimum Cost Network Flow Problem.European Journal of Operational Research,78,116-129.
24. Nourie, F. J.,Guder, F.(1994).A Restricted-Entry Method for a Transportation Problem with Piecewise-Linear Concave Cost.Computer & Operations Research,21,723-733.
25. Rech, P.,Barton, L. G.,E. M. Beale, (ed.)(1970).A Non-Convex Transportation Algorithm.Applications of Mathematical Programming Techniques.
26. Reynolds, C.(1987).Flocks, Herds and Schools: A Distributed Behavioral Model.Computer Graphics,21,25-34.
27. Salerno, J.(1997).Using the Particle Swarm Optimization Technique to Train a Recurrent Neural Model.Proceedings of the Ninth IEEE International Conference on Tools with Artificial Intelligence
28. Shi, Y.(2004).Particle Swarm Optimization.IEEE Connections,2,8-13.
29. Shi, Y.,Eberhart, R. C.(1998).A Modified Particle Swarm Optimizer.Proceedings of the IEEE International Conference on Evolutionary Computation,Piscataway, NJ:
30. Shi, Y.,Eberhart, R. C.(2001).Proc. Congress on Evolutionary Computation 2001.Piscataway, NJ, Seoul, Korea:IEEE Service Center.
31. Shi, Y.,Eberhart, R. C.(1998).Evolutionary Programming VII: Proc. EP 98.New York:Springer-Verlag.
32. Suwan, R.,Sawased, T.(1999).Link Capacity Assignment in Packet-Switched Networks: The Case of Piecewise Linear Concave Cost Function.IEICE Trans. Commun.,82(10)
33. Thach, P. T.(1992).A Decomposition Method Using a Pricing Mechanism for Min Concave Cost Flow Problems with a Hierarchical Structure.Mathematical Programming,53,339-359.
34. Yaged, B.(1973).Minimum Cost Routing for Static Network Models.Networks,1,139-172.
35. Yan, S.,Juang, D. H.,Chen, C. R.,Lai, W. S.(2005).Global and Local Search Algorithms for Concave Cost Transshipment Problems.Journal of Global Optimization,33(1),123-156.
36. 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.
37. Yan, S.,Luo, S. C.(1999).Probabilistic Local Search Algorithms for Concave Cost Transportation Network Problems.European Journal of Operational Research,117,511-521.
38. Yan, S.,Young, H. F.(1996).A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling.Transportation Research,30,379-398.
39. Zangwill, W. I.(1968).Minimum Concave Cost Flows in Certain Networks.Management Science,14,429-450.
40. 徐育良(2002)。碩士論文(碩士論文)。東海大學資訊工程與科學研究所。
41. 張榮芳(2001)。博士論文(博士論文)。國立中山大學電機工程研究所。
42. 曾俊傑(2000)。碩士論文(碩士論文)。義守大學電機工程研究所。
43. 葉思緯(2003)。碩士論文(碩士論文)。元智大學工業工程與管理研究所。
44. 葉麗雯(2002)。碩士論文(碩士論文)。元智大學工業工程與管理研究所。

1. 顏上堯、劉向邦、林至康(2016)。以和諧演算法為基礎之混合全域搜尋法求解最小凹型成本轉運問題。運輸計劃季刊，45(3)，189-216。
2. 楊大輝、黃詩佳、陳珍珍(2014)。隨機實體配送網路設計模型及求解演算法。運輸學刊，26(2)，231-256。