跳到主要內容

臺灣博碩士論文加值系統

(23.20.20.52) 您好!臺灣時間:2022/01/24 18:57
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳建榮
研究生(外文):Jung-Chien Chen
論文名稱:含凹形節線成本最小成本網路流動問題之全域搜尋演算法研究
論文名稱(外文):The global search algorithms in minimum cost flow problem with concave costs
指導教授:顏上堯顏上堯引用關係
指導教授(外文):Shangyao Yan
學位類別:碩士
校院名稱:國立中央大學
系所名稱:土木工程研究所
學門:工程學門
學類:土木工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:108
中文關鍵詞:最小成本網路流動問題全域搜尋區域搜尋凹形節線成本遺傳演算法
外文關鍵詞:genetic algorithmconcave arc costneighborhood searchglobal searchminimum cost network flow problem
相關次數:
  • 被引用被引用:7
  • 點閱點閱:135
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
傳統在最小成本轉運問題的定式上,常以線性方式來定義運送成本,藉以簡化問題的複雜度。在實務上,貨物運送的單位成本常隨數量的增加而遞減,成本函數曲線為凹形。近期在求解含凹形節線成本的特殊最小成本網路流動問題上,有學者以新近鄰近搜尋法求解問題,達到較大範圍的搜尋方式,期能找到較優於傳統啟發解法的解。然而,此等鄰近搜尋法,容易面臨退化的問題,且是否可快速探循全域,則不得而知。另外,以往許多研究凹形成本運送問題的文獻,侷限於不同之特殊網路,在求解上雖較一般性最小成本網路流動問題為簡單。緣此,本研究將針對含凹形節線成本一般性最小成本網路流動問題,發展有效率的全域搜尋法,以求解問題。為評估此全域搜尋法的求解績效,本研究亦參考新近鄰近搜尋法,如門檻值接受法與大洪水法,針對此問題,發展有效的區域搜尋法,測試並比較二者的求解績效,以提供實務界求解此類實際的網路運送問題之參考。
在求解的方法上,本研究引用遺傳演算法之全域式搜尋觀念,並配合本研究問題之理論特性,延伸修正遺傳演算法,以發展適合本研究問題之全域式搜尋演算法。本研究首先設計有效率的編碼方法,以提升網路的運算效率。在遺傳演算法中的群體產生、複製、篩選、交配和突變的各階段做法上,本研究設計適合凹形成本網路流動特性之演算法則。為測試本研究演算法在不同規模及參數的網路問題的求解績效,本研究設計一隨機網路產生器,產生大量的隨機網路,並以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.
中文摘要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 優良解複製率Pe61
4.2.2.3 加入群體率Pp62
4.2.2.4 直接搜尋率Pl63
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).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top