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

NCUIR > Engineering College > Graduate Institute of Civil Engineering > Electronic Thesis & Dissertation > Item 987654321/706

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/706

Title:	含凹形節線成本最小成本網路流動問題之全域搜尋演算法研究;The global search algorithms in minimum cost flow problem with concave costs
Authors:	陳建榮;Jung-Chien Chen
Contributors:	土木工程研究所
Keywords:	最小成本網路流動問題;全域搜尋;區域搜尋;凹形節線成本;遺傳演算法;genetic algorithm;concave arc cost;neighborhood search;global search;minimum cost network flow problem
Date:	2002-06-01
Issue Date:	2009-09-18 17:10:43 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	傳統在最小成本轉運問題的定式上，常以線性方式來定義運送成本，藉以簡化問題的複雜度。在實務上，貨物運送的單位成本常隨數量的增加而遞減，成本函數曲線為凹形。近期在求解含凹形節線成本的特殊最小成本網路流動問題上，有學者以新近鄰近搜尋法求解問題，達到較大範圍的搜尋方式，期能找到較優於傳統啟發解法的解。然而，此等鄰近搜尋法，容易面臨退化的問題，且是否可快速探循全域，則不得而知。另外，以往許多研究凹形成本運送問題的文獻，侷限於不同之特殊網路，在求解上雖較一般性最小成本網路流動問題為簡單。緣此，本研究將針對含凹形節線成本一般性最小成本網路流動問題，發展有效率的全域搜尋法，以求解問題。為評估此全域搜尋法的求解績效，本研究亦參考新近鄰近搜尋法，如門檻值接受法與大洪水法，針對此問題，發展有效的區域搜尋法，測試並比較二者的求解績效，以提供實務界求解此類實際的網路運送問題之參考。在求解的方法上，本研究引用遺傳演算法之全域式搜尋觀念，並配合本研究問題之理論特性，延伸修正遺傳演算法，以發展適合本研究問題之全域式搜尋演算法。本研究首先設計有效率的編碼方法，以提升網路的運算效率。在遺傳演算法中的群體產生、複製、篩選、交配和突變的各階段做法上，本研究設計適合凹形成本網路流動特性之演算法則。為測試本研究演算法在不同規模及參數的網路問題的求解績效，本研究設計一隨機網路產生器，產生大量的隨機網路，並以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.
Appears in Collections:	[Graduate Institute of Civil Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...