淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2007200912235200
中文論文名稱 粒子群演算法應用於多目標車輛途程問題之研究
英文論文名稱 A Study on the Application of Particle Swarm Algorithm on Multi-objective Vehicle Routing Problem.
校院名稱 淡江大學
系所名稱(中) 運輸管理學系碩士班
系所名稱(英) Department of Transportation Management
學年度 97
學期 2
出版年 98
研究生中文姓名 楊昆展
研究生英文姓名 Kun-Chan Yang
學號 696660249
學位類別 碩士
語文別 中文
口試日期 2009-06-15
論文頁數 101頁
口試委員 指導教授-邱顯明
委員-顏上堯
委員-石豐宇
中文關鍵字 多目標規劃  粒子群演算法  車輛途程問題 
英文關鍵字 Multi-objective Programming  Particle Swarm Algorithm  Vehicle Routing Problem 
學科別分類 學科別社會科學管理學
中文摘要 物流業之型態也不斷地修正,期望能達到有效率的物流配送方式,同時也針對顧客的需求改變而進行配送型態改變。物流供應鏈逐漸整合,逆物流對於物流業者的重要性逐漸提升,因此正向物流加上逆向物流才能兼顧物流循環的完整性,因此同時考量收貨與送貨的車輛途程規劃就顯得相當重要。正逆向物流同時進行能有效減少車輛固定成本的花費及有效率的執行收貨與送貨需求,因此為了能有效將物流配送的過程也能達到節能減碳的目的,必須有效減少車輛的使用與行駛的里程,並且使車輛空間有效利用。
目前國際間重要的兩個議題為全球暖化與能源短缺,造成全球暖化的最主要原因是二氧化碳的大量排放,根據國際能源總署指出運輸部門為各國二氧化碳主要來源之一,經濟部能源局也指出運輸部門能源損耗為各部門第二。因此在國內各產業繁榮發展的同時,公司與公司間貨物流動更加頻繁,也對於節能減碳也逐漸開始重視,更因應未來碳權交易的實施,因此希望物流業者藉由採用多車種配送下達到此目的。
本研究在模式構建上主要是以物流業者為出發點,考量運輸總成本最小化、二氧化碳排放量最少及運送車輛貨物平均承載率最高等目標,來構建多目標多車種車輛途程規劃。問題的求解則是以C語言自行撰寫粒子群演算法進行求解。
以車輛途程問題的小型範例,來驗證模式與演算法的正確性;並以黃信穎(2005)所設計之模擬退火法進行求解品質與精度測試,由測試結果發現本研究演算法求解品質較佳;演算法參數的選擇上,則是利用了ANOVA檢定及LSD檢定找出較佳的參數。最後進行大型問題求解,經多次測試,提高運送車輛貨物平均承載率有效減少運輸成本與能源損耗;有規劃將需求點分群再進行運送,有效增加多車種運送時的整體效益。若採用低污染運送車輛對於運輸成本無明顯提升,卻能大大減少二氧化碳排放與增加運送車輛貨物承載率。由結果可之合乎一般邏輯性,證明本模式之正確性,具有應用價值,可以作為實務決策之參考。
英文摘要 The pattern of logistics is continuous updated to achieve the effective delivery operations and to provide an efficient response to changes in customer demand. With the focus on the integration of the logistics Supply Chain, the importance of the reverse logistics is increasing to the logistics firms. Therefore, the integration of the forward and reverse logistics is critical to the logistics efficiency. The vehicle routing problem with simultaneous delivery and pick-up service is major task in this integration. This task not only reduces the fixed vehicle cost, but also increases the delivery operation. This task not only reduces the fixed vehicle cost, but also increases the delivery operation. With the global warming, the energy saving and carbon reduction is hottest topic in the society. Therefore, the reduction of the vehicle usage should be major concern in logistics will be major contribution for the logistics in this aspect.
The purpose of this study is to develop a Multi-objective Heterogeneous Fleet Vehicle Routing Problem to reflect the versatile concerns with the energy conservation and carbon reduction. A delivery operation plan with the multiple objectives such as minimum total transportation cost, minimum carbon consumption amount and maximum average loading ratio is derived from the proposed model. A solution procedure based on the Particle Swarm Algorithm (PSA) is developed for this model. All the coding of the proposed procedure is based on C-language to be executed in a PC.
To test the validation of the proposed solution procedure, we first apply it on a small size problem with an optimal solution form enumeration. The result indicate the proposed procedure capable of provide the same optimal solution. The case study of the Huang (2005) used to camper the result from his simultaneous annealing algorithm with our from the particle swarm algorithm, which demonstrates that superiority of our procedure. The parameters in the PSA are selected by the ANOVA and LSD tests to identify the best parameter value. A large scale of case study is then constructed to test the capability of the proposed procedure in dealing large delivery network. Based on the results of case study and sensitivity analysis, several findings can be identified as follows: 1.The increase of the loading factor results in reduction in transportation cost and energy consumption. 2.The cluster first and routing second approach can enhances the heterogeneous fleet impact on the improvement of objective function value. 3.The introduction low pollution vehicle can reduce tremendous carbon production and increase the vehicle load factor without significant increase in transportation cost. The results of above tests indicate that the proposed solution procedure can provide the valid and solid solution for the simultaneous consideration of the pickup and delivery operations with forward and reverse logistics.
論文目次 目錄
中文摘要
英文摘要
誌謝
目錄 i
表目錄 v
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍 2
1.4 研究方法與流程 3
第二章 文獻回顧 5
2.1 物流論述與節能減碳 5
2.1.1 逆物流概論 5
2.1.2 節能減碳 9
2.1.3 能源損耗與二氧化碳排放之相關文獻 10
2.1.4 小結 14
2.2 車輛途程問題 14
2.2.1 一般車輛途程問題 15
2.2.2 多車種車輛途程問題 18
2.2.3 同時收貨與送貨車輛途程問題 19
2.2.4 小結 22
2.3 模糊與多目標規劃 22
2.3.1 多目標規劃 22
2.3.2 模糊多目標規劃問題 24
2.3.3 小結 29
2.4 粒子群演算法(Particle Swarm Optimization, PSO) 29
2.4.1 PSO之發展背景 29
2.4.2 PSO最佳化演算法介紹 29
2.4.3 PSO演算法步驟 32
2.4.4 小結 34
第三章 問題定義與模式架構 35
3.1 問題定義 35
3.2 前提假設 36
3.3 問題架構 37
3.4 模式建構 37
3.5 模式修正與求解 40
3.6 小結 41
第四章 演算法應用求解與程式設計 42
4.1 問題輸入與限制 42
4.2 車隊組合策略 42
4.3 粒子群演算法編碼及初始群體之產生 45
4.3.1 粒子群演算法編碼 45
4.3.2 粒子群演算法初始群體的產生 46
4.3.3 粒子群演算法初始群體之運用 49
4.4 模式求解架構及流程 49
4.4.1 粒子群演算法應用步驟及流程 49
4.4.2 路線改善應用步驟及流程 52
4.4.3 粒子群演算法之車輛途程規劃模式求解 54
4.5 粒子群演算設計 57
4.5.1 粒子群演算法更新 57
4.5.2 路線改善 59
4.6 粒子群演算法適應值計算、懲罰值及停止條件 59
4.6.1 適應函數(Fitness Function)與懲罰值計算 59
4.6.2 停止條件 60
第五章 範例測試與應用 61
5.1 車輛途程問題範例 61
5.1.1 範例一內容 61
5.1.2 本研究應用與求解 63
5.2 多目標車輛途程問題範例 63
5.2.1 範例二內容 63
5.2.2 演算法求解與品質比較 66
5.2.3 演算法績效分析 67
5.2.4 參數設計比較 68
5.2.5 範例二求解過程 70
5.2.6 範例二結果 72
5.2.7 範例二結果分析 73
5.2.8 範例二路網分析 74
5.2.9 範例二不同策略下之結果分析 78
5.2.10 情境假設分析 83
5.3 敏感度分析 85
第六章 結論與建議 88
6.1 結論 88
6.2 建議 90
參考文獻 91
附錄一 50點需求點例題 96
附錄二 分群方法之結果 98
附錄三 固定成本敏感度分析結果 100

表目錄
表1-1 研究範圍 2
表2-1 逆物流分類表 8
表2-2 CO2排放量推估方法之比較 11
表2-3 不同型態的移動源與活動數據的內設燃料效率因子參考值 13
表2-4 Bodin和Golden求解VRP策略 17
表2-5 Fisher 求解VRP方法發展階段表 18
表2-6 多車種車輛路線啟發式解法一欄表 19
表2-7 同時收貨與送貨車輛路線問題相關文獻 21
表2-8 模糊多目標規劃模型之比較 25
表2-9 報酬表計算內容 26
表2-10 模糊多目標規劃應用文獻一覽 28
表3-1 研究問題定義 36
表3-2 耗能參數及CO2排放係數 38
表3-3 報酬表計算內容 40
表4-1  基因演算法應用於本研究之專有名詞對照表 45
表4-2 粒子群編碼與解碼表 46
表5-1 各需求點座標與需求 61
表5-2 範例結果 62
表5-3 本研究測試結果 63
表5-4 範例二參數設定 64
表5-5 初步車隊組合策略 65
表5-6 求解品質測試結果 66
表5-7 粒子群演算法績效分析 67
表5-8 粒子群演算法參數設計相關內容 68
表5-9 實驗設計ANOVA結果 69
表5-10 LSD檢定結果 70
表5-11 本研究演算法參數設定 70
表5-12 車隊策略修正策略 71
表5-13 車隊組合與隸屬函數表 71
表5-14 範例二測試結果 72
表5-15 策略之隸屬函數 73
表5-16 最終滿意度結果 73
表5-17 策略十三路線分析表 75
表5-18 策略二路線分析表 76
表5-19 策略一路線分析表 77
表5-20 分群測試之結果 79
表5-21 分群策略結果 80
表5-22 低污染大貨車比較表 83
表5-23 情境假設測試結果 83
表5-24 情境假設結果 84
表5-25 結果比較分析表 84
表5-26 車容量參數敏感度分析 85
表5-27 固定成本參數敏感度分析 86
表5-28 學習因子參數敏感度分析 87


圖目錄
圖1-1 研究流程圖 4
圖2-1 產品逆物流 6
圖2-2 逆物流機制(Fleischmann, 2000) 7
圖2-3 二氧化碳排放量結構分佈 10
圖2-4 車輛耗能與二氧化碳推估計算流程 12
圖2-5 一般車輛途程問題 15
圖2-6 目標式隸屬函數圖 27
圖2-7 粒子群最佳化示意圖 30
圖2-8 粒子群演算法流程圖 33
圖4-1 車隊組成策略示意圖 43
圖4-2 本研究車隊組合策略流程圖 44
圖4-3 解碼轉換示意圖 46
圖4-4 本研究初始群體解產生流程圖 48
圖4-5 初代群體示意圖 49
圖4-6 本研究運用粒子群演算法流程圖 51
圖4-7 改善路線之流程圖 53
圖4-8 本研究求解問題流程圖 56
圖4-9 慣性權重變化示意圖 58
圖4-10 2-Swap Exchange示意圖 59
圖5-1 小路網車輛路線圖 62
圖5-2 50點需求點之車輛路線圖 66
圖5-3 測試路網需求點分佈圖 74
圖5-4 策略十三之車輛路線圖 75
圖5-5 策略二之車輛路線圖 76
圖5-6 策略一之車輛路線圖 77
圖5-7 原始策略下之運送車輛行駛路線圖 81
圖5-8 分群方法一之運送車輛行駛路線圖 81
圖5-9 分群方法二之運送車輛行駛路線圖 82
圖5-10 分群方法三之運送車輛行駛路線圖 82

參考文獻 中文部份
1. 申永順(2008),「國際間溫室氣體盤查管理及碳揭露活動之發展趨勢與因應」,財團法人中技社春季環境與能源研討會,民國97年。
2. 吳泰熙,徐俊誠(2000),「車輛途程含取貨問題解法之研究」,大葉大學工業工程研究所碩士論文,民國89年。
3. 李軍、郭耀煌(2001),「物流配送車輛優化調度理論與方法」,中國地質出版社。
4. 李旺蒼(2006),「以粒子群最佳化為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究」,國立中央大學土木工程研究所碩士論文,民國95年。
5. 卓裕仁(1990),「以巨集啟發式方法求解多車種與週期性車輛路線問題之研究」,國立交通大學運輸工程與管理系博士論文,民國89年。
6. 胡曉暉(2002),「粒子群優化算法介紹」,http://www.swarmintelligence.org/papers/cPSOTutorial.pdf,民國91年。
7. 柯政良(2006),「逆物流策略之探索性研究-以供應商觀點」,國立台灣海洋大學航運管理學系研究所碩士論文,民國95年。
8. 敖君瑋(1999),「禁制搜尋法於軟性時窗限制之車輛途程問題研究」,元智大學工業工程研究所碩士論文,民國88年。
9. 張立偉(2001),「災後工程緊急搶修作業排程之研究」,淡江大學運輸管理學系運輸科學碩士班碩士論文,民國90年。
10. 許志義(2003),「多目標決策」,增訂版,五南圖書出版公司。
11. 許哲斌(2008),「在需求變動下具有軟時窗限制之同時收、送貨車輛途程問題」,國立雲林科技大學工業工程與管理研究所碩士論文,民國97年。
12. 黃木才(1996),「貨櫃運輸公司車輛排程問題之研究-模糊多目標遺傳演算法之應用」,國立交通大學交通運輸研究所碩士論文,民國85年。
13. 黃信穎(2005),「同時處理收貨與送貨業務之配送路線規劃」,立德管理學院應用資訊研究所碩士論文,民國94年。
14. 黃小芬(2005),「考慮有限巡行距離下之混合收、送貨車輛途程問題」,國立雲林科技大學工業與管理研究所碩士論文,民國94年。
15. 邱仕銘(2006),「同時收送貨車輛配送問題之研究」,長榮大學經營管理研究所碩士論文,民國95年。
16. 經濟部工業局,移動源CO2排放量的計算工具,民國91年。
17. 經濟部能源局,使用中車輛能源效率評估與提升研究計畫,民國93年。
18. 葉仁吉(2006),「以類免疫演算法應用於船席指派問題之研究」,淡江大學運輸管理學系運輸科學碩士班碩士論文,民國95年。
19. 陳一昌等人(2001),「運輸部門節約能源及減少溫室氣體排放之規劃研究」,交通部運輸研究所,民國90年。
20. 陳正芳,莊英群(2003),「應用禁忌搜尋法混合送收貨之車輛途程問題」,逢甲大學工業工程研究所碩士論文,民國92年。
21. 陳一昌等人(2008),「能源損耗、污染排放與車輛使用之整合關聯模式研究」,交通部運輸研究所,民國97年。
22. 環保署/國科會,台灣地區移動污染源CO2排放量清查暨減量策略評析,民國96年。
23. 蘇雄義(2002),「企業物流導論:新競爭力泉源」,第二版,華泰文化事業。
24. 蘇文清(2005),「軟時窗限制下探討同時正逆向物流之車輛途程問題」,國立中央大學土木工程學系研究所碩士論文,民國94年。
25. 車輛研究耗能網站,http://auto.itri.org.tw/。
26. 節約能源區網站,http://www.energypark.org.tw/index.asp。
27. 行政院環保署,http://www.epa.gov.tw/。

英文部分
1. Ayed Salmen, Imtiaz Ahmad, Sabah Al-Madani, “Particle swarm optimization for task assignment problem,”Microprocessors and Microsystems, pp.363-371, 2002.
2. Bianchessi N, and Righini G, “Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery,”Computers and Operations Research, 2007.
3. Cohon, J.L, “Multiobjective Programming and Planning,”Academic Press, New York, 1978.
4. Dell'Amico M, Righini G, and Salani M, “A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection,” Transportation Science, 2006.
5. Emmanouil E. Zachariadis, Christos D. Tarantilis, Chris T. Kiranoudis, “A hybrid metaheuristic algorithm for the vehicle routing problemwith simultaneous delivery and pick-up service,” Expert Systems with Applications, 2007.
6. Fleischmann, M., Jacqueline, Bloemhof-Ruwaard, M., Dekker, R., Vander Laan, E., Nunen, J. V., Wassenhove, L. V., “Quantitative Models for Reverse Logistics: A Review,” European Journal of Operation Research, Vol. 103, No. 1, pp.1-17, 1997.
7. Fleischmann Mortiz, Krikke Hans Ronald, Dekker Rommert, and Flapper Simme Douwe P,“A characterisation of logistics networks for product recovery, ”The International Journal of Management Science, Omega, Vol. 28, December, pp.653-666, 2000.
8. Golden, B., A. Assad, L. Levy, and E. Gheysens, “The fleet size and mix vehicle routing problem,”Comps. & Opns. Res., pp.49-66, 1984.
9. Guide Jr., Daniel, Wassenhove, and Luk, “The Reverse Supply Chain,”Harvard Business Review, 2002.
10. Jin Ai, and Voratas K., “A particle swarm optimization for the vehicle routing problem with simultaneouspickup and delivery,” Computers & Operations Research, 2008.
11. Jin Ai, and Voratas K., “Particle swarm optimization and two solution representations for solvingthe capacitated vehicle routing problem,” Computers & Industrial Engineering, 2008.
12. Jan Dethloff, “Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up,” OR Spektrum, pp.79-96, 2001.
13. Kennedy, J., and Eberhart, R. C, “Particle swarm optimization,”Proceedings of the 1995 IEEE International Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, pp.1942-1948, 1995.
14. Lenstra, J. K. and Rinnooy Kan, “Complexity of vehicle and scheduling problems,” Networks, pp.221-227,1981.
15. Marius M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, Vol. 35, No. 2, 1987.
16. Chen P., Huang H., and Dong X., “An Ant Colony System Based Heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pickup,” Industrial Electronics and Applications, 2007.
17. Zhu Q., Qian L., Li Y., and Zhu S., “An Improved Particle Swarm Optimization Algorithm for Vehicle Routing Problem with Time Windows,” Congress on Evolutionary Computation, 2006.
18. Rogers, D. S. and Tibben-Lembke, R., “An examination of reverse logistics practices,” Journal of Business Logistics, Vol. 22, No. 2, pp. 129-148.
19. Shi Y., and R. Eberhart, “Parameter Selection in Particle Swarm Optimization,”The Seventh Annual Conf. on Evolutionary Programming, 1998.
20. Theresa J., “Strategic Supply Chain Alignment —Best practice in supply chain management,” Reverse logistics bringing the product back: taking it into the future, 1998.
21. Tang FA, Galvao RD., “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service,”Computers and Operations Research, Vol. 33, NO. 3, pp. 595—619, 2006.
22. Liu Y., Qin Z., Shi Z., and Lu J., “Center particle swarm optimization,” Neurocomputing, pp.672-679, 2007.
23. Zhang Zhixia, and Lu Caiwu, “Application of the Improved Particle Swarm Optimizer to Vehicle Routing and Scheduling Problems,” Proceedings of 2007 IEEE International Conference, 2007.
24. Wang Z., Sun X., and Zhang D., “A PSO-Based Multicast Routing Algorithm,” Third International Conference on Natural Computation, 2007.
25. Tao Z., Chunmei Z., Yuejie Z., and Chuoya Y., “A Mixed PSO Algorithm for the VRPSPD,” Chinese Control and Decision Conference, 2008.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-07-24公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-07-24起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信