以粒子群優化演算法結合動態慣性權重求解車輛途程問題

Meiho University Institutional Repository > 研討會 > 2015南台灣健康照護產業暨健康產業國際學術研討會 > Item 987654321/2957

請使用永久網址來引用或連結此文件: http://ir.meiho.edu.tw/ir/handle/987654321/2957

題名:	以粒子群優化演算法結合動態慣性權重求解車輛途程問題
作者:	游義地;陳信穎;蕭華家
關鍵詞:	車輛途程問題;粒子群優化演算法;動態慣性權重
日期:	2015
上傳時間:	2015-11-23T07:24:22Z (UTC)
摘要:	車輛途程問題（vehicle routing problem, VRP）被廣泛應用於倉儲貨運、人員巡邏及宅配等運輸問題上。車輛途程問題的基本定義為運輸路徑中包含一個場站及數個城市，每部車輛從場站出發，限定拜訪每個城市一次，在車輛容量限制情況下至城市端收取貨物，適應函數為使用車輛最小化及車輛總行駛距離最短。車輛途程問題為旅行推銷員問題之延伸，屬於NP-Hard問題，其時間複雜度隨城市數量呈指數成長，近年來的研究大多著重於利用巨集啟發式演算法求解。粒子群優化演算法（particle swarm optimization, PSO）是由Eberhart 及Kennedy （1995）所提出的一種群體學習的智慧型搜尋法則，由於具有參數設定少、操作簡易及計算效果良好等優點，粒子群優化演算法已廣泛應用於各類優化問題。本文利用改良型粒子群演算法求解車輛途程問題之城市排序，再配合車輛容量限制分派車輛收取貨物。求解過程採用節省演算法（saving algorithm）及貪婪演算法（greedy algorithm）建立起始路徑，為了避免計算過程中落入區域最佳化而無法跳脫，本文採用動態慣性權重及k-opt 交換法，針對城市排序及不同車輛路徑進行路線改善。為了達視窗化功能，程式執行後可立即繪出車輛路徑圖，本文利用C#程式語言開發車輛途程應用程式。先以VRP web 實驗數據做為測試範例，利用輪盤方式設定車輛容量限制，允許每部車輛擁有不同的容量限制，經驗證結果，本文所提出的改良方法具有良好的準確性與執行效率。其次，本文發現將每部車輛所拜訪之城市利用節省演算法重新排列，可有效提高k-opt的改善效果。
顯示於類別:	[研討會] 2015南台灣健康照護產業暨健康產業國際學術研討會

文件中的檔案:

沒有與此文件相關的檔案.

檢視Licence

在MUIR中所有的資料項目都受到原著作權保護.

資料載入中.....