含凹形節線成本最小成本網路流動問題之全域搜尋演算法研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：219

、訪客IP：3.147.55.155

姓名

陳建榮(Jung-Chien Chen) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

含凹形節線成本最小成本網路流動問題之全域搜尋演算法研究
(The global search algorithms in minimum cost flow problem with concave costs)

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

傳統在最小成本轉運問題的定式上，常以線性方式來定義運送成本，藉以簡化問題的複雜度。在實務上，貨物運送的單位成本常隨數量的增加而遞減，成本函數曲線為凹形。近期在求解含凹形節線成本的特殊最小成本網路流動問題上，有學者以新近鄰近搜尋法求解問題，達到較大範圍的搜尋方式，期能找到較優於傳統啟發解法的解。然而，此等鄰近搜尋法，容易面臨退化的問題，且是否可快速探循全域，則不得而知。另外，以往許多研究凹形成本運送問題的文獻，侷限於不同之特殊網路，在求解上雖較一般性最小成本網路流動問題為簡單。緣此，本研究將針對含凹形節線成本一般性最小成本網路流動問題，發展有效率的全域搜尋法，以求解問題。為評估此全域搜尋法的求解績效，本研究亦參考新近鄰近搜尋法，如門檻值接受法與大洪水法，針對此問題，發展有效的區域搜尋法，測試並比較二者的求解績效，以提供實務界求解此類實際的網路運送問題之參考。
在求解的方法上，本研究引用遺傳演算法之全域式搜尋觀念，並配合本研究問題之理論特性，延伸修正遺傳演算法，以發展適合本研究問題之全域式搜尋演算法。本研究首先設計有效率的編碼方法，以提升網路的運算效率。在遺傳演算法中的群體產生、複製、篩選、交配和突變的各階段做法上，本研究設計適合凹形成本網路流動特性之演算法則。為測試本研究演算法在不同規模及參數的網路問題的求解績效，本研究設計一隨機網路產生器，產生大量的隨機網路，並以C++語言撰寫所有相關的電腦程式，在個人電腦上測試分析，以比較全域搜尋法與鄰近搜尋法之績效。實證結果顯示，本研究採行的編碼方式在具方向性網路上求解品質良好，遺傳演算法整體求解時間雖較長，但求解結果區域搜尋法為佳。

摘要(英)

The minimum cost transshipment problems are traditionally formulated as a linear cost problem, in order to reduce problem complexity. In reality, the unit cost decreases as the amount transported increases, resulting in a concave cost function. Recently, a research started to use advanced neighborhood search algorithms to solve concave cost network problems in order to find better solutions than traditional heuristics. However, such neighborhood search algorithms easily encounter degeneracy problems, resulting in decreased solution efficiency. It is wonder if such algorithms can explore the whole domain area to find good solutions. This research attempts to develop global search algorithms to solve normal minimum cost network flow problems with concave arc costs. To evaluate global search algorithms and neighborhood search algorithms, we developed two neighborhood search algorithms referring to the threshold accepting algorithm and the great deluge algorithm. The results will hopefully be useful reference for practitioners to solve their real transshipment problems.
We first explored the problem characteristics then modified the genetic algorithm (GA) to develop suitable global search algorithms. In details, we designed an efficient coding method to represent network solutions. During various stages of GA, including production, reproduction, selection, crossover, and mutation, we designed methods that are suitable for the characteristics of minimum cost network flow problems with concave arc costs. To evaluate global and neighborhood search algorithms, we designed a randomized network generator to produce many test problems. We employed C++ computer language to code all necessary programs and perform tests on personal computers. The results show that the coding method and other stages in GA performed relatively well in the tests.

關鍵字(中)

★ 最小成本網路流動問題
★ 全域搜尋
★ 區域搜尋
★ 凹形節線成本
★ 遺傳演算法

關鍵字(英)

★ genetic algorithm
★ concave arc cost
★ neighborhood search
★ global search
★ minimum cost network flow problem

論文目次

中文摘要 I
英文摘要 II
誌謝 III
目錄 IV
圖目錄 VII
表目錄 VIII
第一章緒論 1
1.1 研究緣起與動機 1
1.2 研究目的與範圍 3
1.3 研究方法與流程 4
第二章文獻回顧 5
2.1 凹形成本問題 5
2.2 新近組合最佳化啟發式解法 7
2.3 遺傳演算法 9
2.3.1 遺傳演算法簡介 9
2.3.1.1 編碼(Code)方式 11
2.3.1.2 初始群體 11
2.3.1.3 適應度、選擇與複製 11
2.3.1.4 交配 12
2.3.1.5 突變 13
2.3.1.6 遺傳演算法與傳統方法之比較 14
2.3.2 各種遺傳演算法應用 14
2.4 鄰近搜尋法 17
2.4.1 模擬退火法： 17
2.4.2 門檻值接受法： 18
2.4.3 大洪水法： 18
2.4.4 禁制搜尋法： 19
2.5 小結 20
第三章問題描述與求解演算法設計 21
3.1問題描述 21
3.1.1問題定式 21
3.1.2問題特性說明 22
3.2 求解演算法設計 25
3.2.1 全域改善策略 – 遺傳演算法(GA) 25
3.2.1.1 編碼方式(Coding) 25
3.2.1.2 流量推擠法 28
3.2.1.3 初始群體產生策略 29
3.2.1.3.1 隨機初始解產生法 30
3.2.1.3.2 依據凹形特性產生起始解 33
3.2.1.4 選擇(Selection) 36
3.2.1.5 複製(Reproduction) 37
3.2.1.6 交配(Crossover) 37
3.2.1.7 突變(Mutation) 39
3.2.1.8 群體組成 42
3.2.2 區域尋優啟發法之交換策略 42
3.2.2.1 起始解 42
3.2.2.2 門檻值接受法的交換策略(TA) 43
3.2.2.3 大洪水法的交換策略(GDA) 45
3.2.2.4 結合禁制策略的門檻值接受法(TTA)與大洪水法(TGDA) 46
3.3 小結 49
第四章實證分析 51
4.1 網路產生器設計 51
4.1.1 隨機網路產生法 51
4.1.2 供給(需求)節點與供給(需求)量的隨機產生法 53
4.2 全域搜尋法-遺傳演算法 54
4.2.1 群體大小與交換節線數 57
4.2.2 群體組成 59
4.2.2.1 突變率 59
4.2.2.2 優良解複製率Pe 61
4.2.2.3 加入群體率Pp 62
4.2.2.4 直接搜尋率Pl 63
4.2.3 結合鄰近搜尋法 – 突變 64
4.2.4 個體選擇方式 67
4.2.5 凹形初始解與隨機初始解之比較 68
4.2.6 初始群體 69
4.2.7 演化世代數與收斂情形 72
4.2.8 小結 74
4.3 區域搜尋法 75
4.3.1 起始解 75
4.3.2 TA與GDA之系統參數 76
4.3.3 加入禁制搜尋策略於TA與GDA的系統參數 77
4.3.4 小結 79
4.4 全域演算法和區域演算法之實證與績效比較 80
4.5 不具方向性網路 84
第五章結論與建議 87
5.1 結論 87
5.2 貢獻 88
5.3 建議 89
參考文獻 91
附錄一 Prüfer code編、解碼方式 96
附錄二中大型網路初始群體與最終解關係圖例 99
附錄三各型網路之目前最佳解 101
附錄四各演算法配合方案求解時間 104
附錄五各演算法配合方案網路規模與求解時間 106

參考文獻

1. 林鄉鎮、魏健宏，「應用類神經網路與遺傳演算法構建小汽車跟車模式之研究」，運輸計畫季刊，第二十八卷，第三期，第353-378頁(1999)。
2. 吴志远、邵惠鹤、吴新余，「一种新的自适应遗传算法及其在多峰值函数优化中的应用」控制理论与应用，第十六卷，第一期(1999)。
3. 張維新，「用混合式基因演算法求解具容量限制之多點網路設計問題」，博士論文，交通大學資訊管理所(2000)。
4. 詹達穎，「模擬鍛鍊法求解車輛排程之探討」，中華民國運輸學會第九屆論文研討會論文集，第185-192頁(1994)。
5. 謝國倫，「基因演算法應用於捷運轉乘公車區位路徑問題之研究」，碩士論文，淡江大學運輸管理學系，台北(1998)。
6. 韓復華、卓裕仁，「門檻接受法、成本擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析」，運輸學刊，第九卷，第三期，第103-129頁(1996)。
7. 韓復華、林修竹，「TA與GDA巨集啟發式法在VRPTW問題上之應用」，中華民國第四屆運輸網路研討會，第83-92頁(1999)。
8. 韓復華、楊智凱，「門檻接受法在TSP問題上之應用」，運輸計劃季刊，第二十五卷，第二期，第163-188頁(1996)。
9. 韓復華、陳國清、卓裕仁，「成本擾動法在TSP問題之應用」，中華民國第二屆運輸網路研討會論文集，第283-292頁(1997)。
10. 韓復華、楊智凱、卓裕仁，「應用門檻接受法求解車輛路線問題之研究」，運輸計畫季刊，第二十六卷，第二期，第253-280頁(1997)。
11. 藍武王、邱裕鈞，「線性軸輻路網接駁卅轉運區位、路線與排班之規劃─遺傳演算法之應用」，第二十九卷，第三期，第465-493頁(2000)。
12. 顏上堯、周容昌、李其灃，「交通建設計畫評選模式及其解法之研究─以中小型交通建設計畫的評選為例」，運輸計畫季刊，第三十一卷，第一期(2002)。(已接受)
13. Abuali, F. N., Wainwright, R. L., and Schoenefeld D. A., “Determinant factorization: a new encoding scheme for spanning trees applied to the probabilistic minimum spanning tree problem,” Proceedings of The Sixth International Conference on Genetic Algorithms, pp. 470-477 (1995).
14. Ahuja, R. K., Maganti, T. L. and Orlin, J. B., Network Flows, Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs (1993).
15. Alfa, A. S., Heragu, S. S. and Chen, M. “A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problem,” Computers and Industrial Engineering, Vol. 21, pp. 635-639 (1991).
16. Amiri, A., and Pirkul, H., “New Formulation and Relaxation to Solve a Concave Cost Network Flow Problem,” Journal of the Operational Research Society, Vol. 48, pp. 278-287 (1997).
17. Balakrishnan, A., and Graves S. C., “A Composite Algorithm for a concave-cost network flow problem,“ Networks, Vol. 19, pp. 175-202 (1989).
18. Blumenfeld, D. E., Burns, L. D., Diltz, J. D., and Daganzo, C. F., “Analyzing Trade-offs Between Transportation, Inventory, and Production Costs on Freight Network,” Transportation Research, Vol. 19B, pp. 361-380 (1985).
19. Booker, L. B., “Improving Search in Genetic Algorithms,” Genetic Algorithms and Simulated Annealing (L. Davis, editor), Pitman, London, pp. 61-73 (1987).
20. Charon, I. and Hurdy, O., “The Noising Method: A New Method for Combinatorial Optimization,” Operations Research Letters, Vol. 14, pp. 133-137 (1993).
21. Cheng, C. P., Liu, C. W., and Liu, C. C., “Unit Commitment by Lagrange Relaxation and Genetic Algorithms,” IEEE Transactions on Power Systems, Vol. 15, No. 2 (2000).
22. Davis, L., “Genetic Algorithm and Simulated Annealing,” Morgan Kaufman Publishers, Los Altos, CA (1987).
23. Davis, L., “Adapting operator probabilities in genetic algorithms,” Proceedings of the Third International Conference on Genetic Algorithms, pp. 61-69 (1989).
24. DeJong, K. A., “Analysis of the Behavior of a Class of Genetic Adaptive Systems,” Ph.D. Dissertation, University of Michigan (1975).
25. Demeulemeester, E., Dodin, B. and Herroelen, W., “A Random Activity Network Generator,” Operations Research, Vol. 41, No. 5, pp. 972-980(1993).
26. Dueck, G., “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational Physics, Vol. 104, pp. 86-92 (1993).
27. Dueck, G., and Scheuer, T., ”Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp. 161-175 (1990).
28. Dukwon, K., and Panos, M., “Dynamic Slope Scaling and Trust Interval Techniques for Solving Concave Piecewise Linear Network Flow Problems,” Networks, Vol. 35, pp. 216-222 (2000).
29. Gallo, G., Sandi C., and Sodini, C., “An Algorithm for the Min Concave Cost Flow Problem,” European Journal of Operation Research, Vol. 4, pp. 248-255 (1980).
30. Gallo, G., and Sandi, C., ”Adjacent Extreme Flows and Application to Min Concave Cost Flow Problems,” Networks, Vol. 9, pp. 95-121 (1979).
31. Gen, M., and Cheng, R., “Genetic Algorithms and Engineering Design”, Wiley Interscience Publication, MA (1997).
32. Glover, F., and Laguna, M., “Tabu search, Kluwer Academic Publishers,” Massachusetts (1997).
33. Glover, F., “Tabu Search, PartⅠ,” ORSA Journal on Computing Vol. 1, No. 3, pp.190-206 (1989).
34. Glover, F., “Tabu Search- Part II,” ORSA Journal on Computing, Vol. 2, No. 1, pp. 4-32 (1990).
35. Goldberg, D. E., “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley, Reading MA (1989).
36. Golden, B. L., and Skiscim, C. C., “Using Stimulated Annealing to Solve Routing and Location Problems,” Naval Research Logistic Quarterly, Vol. 33, pp. 261-279 (1986).
37. Gu, J. and Huang, X., “Efficient Local Search with Search Space Smoothing: A Case Study of the Traveling Salesman Problem (TSP),” IEEE Transaction on Systems, Man and Cybernetics, Vol. 24, pp. 728-739 (1994).
38. Guisewite, G. M., and Pardalos, P. M., “A Polynomial Time Solvable Concave Network Flow Problems,” Networks, Vol. 23, pp. 143-147 (1993).
39. Hall, R. W., ”Direct Versus Terminal Freight Routing on Network with Concave Costs,” GMR-4517, Transportation Research Dept., GM Research Laboratories (1983).
40. Hillier, F. S., and Lieberman, G. J., “Introduction to Operation Research,” 7th ed., McGrow-Hill( 2000).
41. Jeffrey, A. J., and Christopher, R. H., “On the Use of Non-Stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems with GA’s,” Department of Industrial Engineering North Carolina State University, NC 27695-7906 (1994).
42. Jordan, W. C., “Scale Economies on Multi-Commodity Networks,” GMR-5579, Operating Systems Research Dept., GM Research Laboratories (1986).
43. Kershenbaum, A., “When Genetic Algorithms Work Best,” INFORMS Journal of Computing, Vol. 9, No. 3, pp.253-254 (1997).
44. Kirkpatrick, S., Gelatt , C. D., and Vecchi, M.P., “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680 (1983).
45. Klingman, D., Gelatt, C. D., and Stutze, J., “NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problem,” Management Science, Vol. 20, pp. 814-821(1974).
46. Kuhn, H. W., and Baumol, W. J., “An Approximate Algorithm for the Fixed-Charge Transportation Problem,” Naval Res. Logistics Quarterly, Vol. 9, pp. 1-16 (1962).
47. Larsson, T., Migdalas, A., and Ronnqvist, M., ”A Lagrange an Heuristic for the Capacitated Concave Minimum Cost Network Flow Problem,” European Journal of Operational Research, Vol. 78,pp. 116-129 (1994).
48. Mathias, K. E., and Whitley, L. D., “Initial performance comparisons for the delta coding algorithm,” The First IEEE Conference on Evolutionary Computation, Orlando, Florida (1994).
49. Nourie, F. J., and Guder, F., ”A Restricted-Entry Method for a Transportation Problem with Piecewise-Linear Concave Cost,” Computer & Operations Research, Vol. 21, pp. 723-733, (1994).
50. Osman, I. H., and Kelly, J. P., “Meta-Heuristics: An overview,” Meta-Heuristics: Theory & Applications, Kluwer Academic Publishers, Boston, London, Dordrecht, pp. 1-21 (1996).
51. Palmer, C. C. and Kershenbaum, A., “An Approach to a Problem in Network Design Using Genetic Algorithms”, Networks, vol. 26, pp151-163(1995).
52. Rech, P., and Barton, L. G., “A Non-Convex Transportation Algorithm,” Applications of Mathematical Programming Techniques, E. M. Beale, ed. (1970).
53. Reeves, C., “Genetic Algorithms for the Operations Researcher”, INFORMS Journal on Computing, Vol. 9, No. 3, pp. 231-250 (1997).
54. Reeves, C. R., “Improving the Efficiency of Tabu Search for Machine Sequencing Problems,” Journal of the Operation Research Society, Vol. 44, No. 4, pp. 375-382 (1993).
55. Robuste, F., Daganzo, C. F., and Souleyrette, R., “Implementing Vehicle Routing Models,” Transportation Research, Vol. 24B, No. 4, pp. 263-286 (1990).
56. Rudolph, G., “Convergence properties of canonical genetic algorithms,” IEEE Trans. Neural Networks, Vol. 5, pp. 96-101 (1994).
57. Seiichi, K., Maggie, K., and Wayne, W. D., “Genetic Simulated Annealing and Application to Non-slicing Floor plan Design,” Baskin Center for Computer Engineering & Information Sciences University of California, Santa Cruz, CA 95064 (1995).
58. Sheffi, M. J.,”Urban Transportation Networks：Equilibrium Analysis with Mathematical Programming Methods,” Prentical-Hall(1984).
59. Srinivas, M., and Patnaik, L. M., “Adaptive probabilities of crossover and mutation in genetic algorithms,” IEEE Trans Syst., Man, and Cybern, Vol. 24, pp. 656-667 (1994).
60. Suwan, R., and Sawased, T., “Link Capacity Assignment in Packet- Switched Networks: The Case of Piecewise Linear Concave Cost Function,” IEICE Trans. Commun., Vol. E82-B, No. 10 (1999).
61. Taguhi, T., Ida. K., Gen, M., “A Genetic Algorithm for Optimal Flow Assignment in Computer Network,” Computers ind. Engng, Vol. 35, No3-4, pp. 535-538(1998).
62. Thach, P. T., “A Decomposition Method Using A Pricing Mechanism for Min Concave Cost Flow Problems With a Hierarchical Structure,” Mathematical Programming, Vol. 53, pp. 339-359 (1992).
63. Thierens, D., and Goldberg D., “Elitist recombination: an integrated selection recombination GA,” The First IEEE Conference on Evolutionary Computation, Orlando, Florida (1994).
64. Yaged, B., “Minimum Cost Routing for Static Network Models,” Networks, Vol. 1, pp. 139-172 (1971).
65. Yan, S., and Luo, S. C., “A Tabu Search-based Algorithm for Concave Cost Transportation Network Problems,” Journal of the Chinese Institute of Engineers, Vol. 21, pp. 327-335 (1998).
66. Yan, S., and Luo, S. C., “Probabilistic Local Search Algorithms for Concave Cost Transportation Network Problems,” European Journal of Operational Research, Vol.117, pp. 511-521 (1999).
67. Zangwill, W. I., ”Minimum Concave Cost Flows in Certain Networks,” Management Science, Vol. 14, pp. 429-450 (1968).

指導教授

顏上堯(Shangyao Yan)

審核日期

2002-7-9

推文