類螞蟻族群演算法於求解含凹形節線成本最小成本轉運問題之研究; Analogous Ant Colony System Algorithms for Solving Minimum Cost Transshipment Problems with Concave Arc Costs

NCUIR > Engineering College > Department of Civil Engineering > Research Project > Item 987654321/42675

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

Title:	類螞蟻族群演算法於求解含凹形節線成本最小成本轉運問題之研究;Analogous Ant Colony System Algorithms for Solving Minimum Cost Transshipment Problems with Concave Arc Costs
Authors:	顏上堯
Contributors:	土木工程學系
Keywords:	凹形節線成本;最小成本轉運問題;類螞蟻族群演算法;全域搜尋;鄰近搜尋;交通運輸
Date:	2006-07-01
Issue Date:	2010-12-06 15:02:24 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	傳統上，最小成本轉運問題的運送成本常以線性方式來定義，藉以簡化問題的複雜度。然而，在實務上，貨物運送的單位成本常隨數量的增加而遞減，其成本函數曲線呈現凹形。因此，近期有學者以新近鄰近搜尋法，如門檻值接受法與大洪水法，求解含凹形節線成本之特殊最小成本網路流動問題，以達到擴大搜尋範圍之效，期能找到較優於傳統啟發解法的解。然而，此等鄰近搜尋法，容易面臨退化的問題，且是否可快速探循全域，則不得而知。加上，有鑑於以往研究凹形成本運送問題的文獻，大都侷限於特殊的網路型態，因此近來有學者利用遺傳演算法發展全域搜尋法，以求解含凹形節線成本一般性最小成本轉運問題。螞蟻族群演算法為一新近風行之巨集啟發解法，其利用分散式搜尋之觀念進行求解，並在許多問題上求得頗佳的結果，在部分的應用例中甚至發現其求解效率較GA為佳。由於以往未發現有文獻利用螞蟻族群演算法求解凹形成本網路流動問題，因此本研究擬針對含凹形節線成本之最小成本轉運問題特性，以螞蟻族群演算法之搜尋觀念為基礎，並結合文獻上求解含凹形節線成本之最小成本網路流動問題之遺傳演算法、門檻值接受法及凹形成本網路啟發解法之特點，發展一類螞蟻族群演算法，期能有效得求解含凹形節線成本之最小成本轉運問題。為評估此演算法的求解績效，本研究亦將參考門檻值接受法、大洪水法與遺傳演算法，進行測試比較分析，提供實務界參考以求解此類實際的網路運送問題。在求解的初擬方法上，本研究將設計數個初始解法，並在可行解產生的過程中，發展數種狀態轉移法則產生多條路徑，並透過流量推擠法產生可行伸展樹。在費洛蒙的更新法則上，本研究擬結合區域與全域費洛蒙更新方式，並引進門檻值接受法部分之求解機制，發展數種與以往不同的費洛蒙更新方式。此外，本研究亦擬引進遺傳演算法之菁英策略，以提升演算績效。為測試本研究演算法在不同規模及參數的網路問題之求解績效，本研究擬設計一隨機網路產生器，產生大量的隨機網路，並以C++語言撰寫所有相關的電腦程式，在個人電腦上測試分析。研究期間：9408 ~ 9507
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Civil Engineering] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	386	View/Open

社群 sharing

Loading...