(3.238.174.50) 您好!臺灣時間:2021/04/18 17:52
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李國村
研究生(外文):Kuo-Tsun Li
論文名稱:以群蟻演算法求解動態車輛途程規劃
論文名稱(外文):Applying Ant Colony Algorithm in Solving the Dynamic Vehicle Routing Problem
指導教授:王順生王順生引用關係
指導教授(外文):Shun-Sheng Wang
學位類別:碩士
校院名稱:朝陽科技大學
系所名稱:工業工程與管理系碩士班
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:67
中文關鍵詞:群蟻最佳化演算法替代性道路即時資訊車輛途程規劃
外文關鍵詞:vehicle routing problemreal-time informationant colony algorithm
相關次數:
  • 被引用被引用:12
  • 點閱點閱:503
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:128
  • 收藏至我的研究室書目清單書目收藏:0
近年來由於世界經濟的全球化、貿易的自由化、產品生命週期的縮短、客戶要求服務水準的提升等因素,物流(或稱運籌Logistics)成為全球企業關注的焦點,善用物流以提高顧客服務的水準,並滿足顧客的需求已成為企業強化競爭優勢的重要策略。物流的範圍非常廣,本研究主要針對動態車輛途程規劃問題進行探討。
國內外一直有許多的文獻探討車輛途程規劃的問題,前提假設大多以靜態來計算現有的路線規劃的最佳路線,這些演算法也只能被應用在顧客需求量、時間變數(車輛運送時間、時間窗)為明確數值時,對於現實生活中的時間變數不確定的情形下較不能適用,故本研究將以群蟻最佳化演算法解決途程路線的問題。
本研究將針對顧客需求所在的位置來進行車輛途程路線,並藉由改善進而獲得車輛途程路線的最佳解。另外,藉由定位系統收到的途程路段交通擁塞或意外事故發生的即時資訊,並且應用K條最短路徑演算法(KSP)來選擇替代性道路,因此能因應即時資訊下的途程路線,以反應真實的交通狀況。
Since the competition in transportation industry, logistics has become an important issue. Related companies need to put much effort to cut-down the running cost as well as derive new policy to survive. Wise vehicle routing path proved to be an efficient act.

Many researches studied the vehicle routing problem with different considerations, such as customer''s demand, and time variable (transport time, time window). However, most of the solutions seemed time-consuming, especially, when the parameters at hand became large. And, most of the time, the solutions are not accurate enough. On the other hand, when real traffic conditions such as traffic jams and bad weather take into account, those methods are unable to settle the problem.

This research applies ant colony algorithm and K shortest path algorithm in solving the dynamic vehicle routing problem. A model was built to test the algorithm with different parameters. The results prove that the efficiency under real-time information was improved. Same approach should be able to apply on other case, such as the relocation of goods in a storage or warehouse.
中文摘要 ……………………………………………………………………i
目錄…………………………………………………………………………ii
圖目錄………………………………………………………………………vi
表目錄 ……………………………………………………………………vii
第一章 緒論…………………………………………………………………1
1.1研究動機……………………………………………………………1
1.2研究目的……………………………………………………………2
1.3研究方法與流程……………………………………………………3
1.4研究範圍……………………………………………………………4
第二章 文獻探討
2.1 傳統車輛途程規劃理論介紹………………………………………7
2.1.1車輛途程規劃問題 …………………………………………7
2.1.2車輛途程規劃模式的基本假設……………………………10
2.2 求解車輛途程規劃的方法 ………………………………………11
2.2.1車輛途程規劃求解方法……………………………………11
2.2.2精確法………………………………………………………14
2.2.3啟發法………………………………………………………15
2.2.4兩階段法……………………………………………………17
2.2.5最佳化啟發法………………………………………………17
2.2.6通用啟發法…………………………………………………18
2.3 動態車輛途程路線 ………………………………………………21
2.3.1隨機旅行時間的車輛途程規劃問題………………………21
2.4 群蟻最佳化演算法 ………………………………………………24
2.4.1真實螞蟻行為………………………………………………24
2.4.2人造螞蟻……………………………………………………25
2.4.3群蟻演算法的應用範圍……………………………………25
2.4.4群蟻最佳化演算流程………………………………………26
2.4.5群蟻演算法公式……………………………………………28
第三章 研究方法
3.1 建立即時資訊下動態車輛途程規劃評估架構 …………………31
3.1.1動態指派架構………………………………………………31
3.1.2即時資訊下動態車輛途程規劃架構………………………33
3.2 群蟻演算法於靜態VRP之測試 …………………………………36
3.2.1實驗設計……………………………………………………36
3.2.2結果分析……………………………………………………38
3.2.3 費洛蒙揮發係數 ………………………………………39
3.2.4螞蟻數量參數設定實驗 …………………………………40
3.2.5 費洛蒙痕跡參數與 啟發式函數參數之實驗 …………41
3.2.6迭代圈數參數………………………………………………43
3.3 群蟻演算法求解動態車輛途程路徑問題 ………………………43
第四章 提供即時資訊下之動態VRP之實驗與分析
4.1 即時資訊途程路線求解演算法設計 ……………………………46
4.1.1即時資訊說明………………………………………………46
4.1.2擁擠路段之預測……………………………………………46
4.1.3提供即時資訊與歷史資料下途程路線演算流程…………48
4.2 實驗設計 …………………………………………………………50
4.2.1路網資料……………………………………………………50
4.2.2實驗參數設定………………………………………………50
4.2.3在車容量限制下,車輛途程路徑結果……………………52
4.3 提供即時資訊下動態VRPS之結果分析 ………………………54
4.3.1型態1車流分布穩定下……………………………………54
4.3.2型態2車流分布擁擠狀態下………………………………57
第五章 結論與建議
5.1 結論 ………………………………………………………………61
5.2 建議 ………………………………………………………………63

參考文獻……………………………………………………………………64
附錄…………………………………………………………………………67
附錄A…………………………………………………………………67
圖目錄
圖1 研究流程圖……………………………………………………………4
圖2 物流配送系統示意圖…………………………………………………5
圖3 車輛途程規劃求解方法枝狀圖 ……………………………………13
圖4 螞蟻覓食行為 ………………………………………………………25
圖5 群蟻演算法流程圖 …………………………………………………27
圖6 車輛指派與途程路線研擬 …………………………………………32
圖7 即時資訊下動態指派架構演算流程圖 ……………………………34
圖8 動態車輛途程規劃演算流程圖 ……………………………………45
圖9 考慮即時資訊與歷史資料下途程路線演算流程 …………………49
圖10 台中市西屯區街道圖………………………………………………50
圖11 各個需求點的位置圖………………………………………………52
圖12 型態1-在離峰情況下5個需求點途程路線比較圖………………55
圖13 型態1-在尖峰情況下5個需求點途程路線比較圖………………56
圖14 交通路網中車流量擁擠路段示意圖………………………………57
圖15 型態2-在離峰情況下5個需求點途程路線比較圖………………58
圖16 型態2-在尖峰情況下5個需求點途程路線比較圖………………60
圖17 在離峰情況下與尖峰情況下的途程路線比較圖…………………62


表目錄
表1 研究範圍及假設………………………………………………………6
表2 車輛途程規劃模式的基本假設 ……………………………………10
表3 TSP 測試例題表 ……………………………………………………37
表4 測試項目表 …………………………………………………………38
表5 起始解對求解品質影響 ……………………………………………39
表6 參數 對求解品質影響 ……………………………………………40
表7 參數ant m對求解品質影響 ………………………………………41
表8 參數 對求解品質影響 …………………………………………42
表9 各個需求點編號及其需求量 ………………………………………52
表10 在離峰情況下5個需求點路線數目、旅行時間、改善百分比…55
表11 在尖峰情況下5個需求點路線數目、旅行時間、改善百分比…57
表12 在離峰情況下5個需求點路線數目、旅行時間、改善百分比…59
表13 在尖峰情況下5個需求點路線數目、旅行時間、改善百分比…60
[1] Laporte, G. and Osman, I. H., “Routing Problem : A Bibliography,”
Annals of Operations Research, Vol.6, pp.227-263, 1995.

[2] Fisher, M.L., and Jaikumar, R., “A Generalize Assignment Heuristic for Vehicle Routing,” Networks, Vol. 11, pp.109-124, 1981.

[3] Bodin, L. D., Golden, B. L., Assad, A. A., and Ball, M. , “Routing
and scheduling of vehicles and crews, the state of the art,” Computers and OperationsResearch, 10(2), pp.63-212, 1983.

[4] 林依潔,「整合模糊理論與螞蟻演算法於含時間窗限制之車輛途程問題」,台北科技大學生產系統工程與管理研究所碩士學位論文,2003。

[5]Laporte, G. and Nobert, Y. , “Exact Algorithms for the Vehicle Routing Problem,” Surveys in Combinatorial Optimization, pp. 147-184, 1987.

[6]Kolen, A., Kan, W. and Trienekens, H., “Vehicle Routing with Time Windows,” Operations Research, Vol. 35, pp. 266-273, 1987.

[7] Clarke, G. and Wright, J. W., “Scheduling of Vehicles from a Central Depot to a Number of Deliver Points,” Operations Research, Vol. 12, pp. 568-581, 1964.

[8]李洪鑫,「含時窗車輛途程問題各演算法適用範圍之探討」,東海大學工業工程研究所碩士論文,2002。

[9] Lin, S. and Kernighan, B. W., “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498-516, 1973.

[10] Gillett, B. and Miller, L., “A Heuristic for the Vehicle Dispatching Problem,” Operations Research, Vol. 22, pp. 340-349, 1974.



[11] Golden, B. L. and Bodin, L., “Microcomputer-Based Vehicle Routing and Scheduling Software,” Computers & Operations Research, Vol. 13, pp. 277-285, 1986.

[12] Tangiguchi, E., Yamada, T. and Tamagawa, D., “Modeling Advanced Routing and Scheduling of Urban Pickup/Delivery Trucks,” Proc., 6th World Congress on Intelligent Transportation System, 1999.

[13] Glover, F., “Heuristic for Integer Programming Using Surrogate Constraints,” Decision Science, Vol. 8, pp.156-166, 1977.

[14] Carlton, W. B. and Barners, J. W., “Solving the Traveling Salesman Problem with Time Windows Using Tabu Search,” IIE Transaction, pp. 617-629, 1996.

[15] Gendreau, M., Hertz, A., and Laporte, G., “A Tabu Search Heuristic for the Vehicle Routing Problem,” Management Science, 40(10),
pp.1276-1290,1994.

[16] Toth, P. and Vigo, D., “The Granular Tabu Search (and Its Application to the Vehicle Routing Problem),” Working Paper, DEIS, University of Bologna, 1998.

[17]羅敏華,「蟻群最佳化演算法於載重限制之車輛途程問題的研究」,元
智大學工業工程與管理研究所碩士論文,2003。

[18]吳亮瑩,「單一物流中心配送車輛途程問題之研究–以遺傳演算法求解」,成功大學工業管理研究所碩士論文,1999。

[19] Kirkpatrick, S., Gelatt, C. D., Jr. and Vecchi, M. P., “Optimization Simulated Annealing,” Science, Vol. 220, pp. 671-680, 1983.

[20] Psaraftis, H.N. , “Dynamic vehicle routing: Status and prospect,” Annals of Operations Research, Vol. 61, pp.143-164, 1995.



[21]許晉嘉,「宅配業貨物配送路線規劃問題之研究」,成功大學交通管理科學研究所碩士論文,2003。

[22]呂英志,「即時資訊下車輛路線問題之研究」,逢甲大學交通工程與管理研究所碩士論文,2002。

[23]曾鈺惠,「即時行車資訊下物流配送作業規劃之研究」,淡江大學運輸管理學系運輸科學碩士班碩士論文,2003。

[24] Dorigo, M. and Gambardella, L.M., “Ant Colonies for the Traveling Salesman Problem,” BioSystems, Vol. 43, pp. 73-81, 1997.

[25] Dorigo, M. and Gambardella, L.M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on evolutionary Computation, pp.53-66, 1997.

[26] Dorigo, M., Maniezzo, V. and Colorni, A., “The Ant System:Optimization by a Colony of Cooperating Agents, ” IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 1, pp.1-13,1996.

[27]陳志明,「應用群蟻演算法於動態車輛途程規劃研究」,朝陽科技大學工業工程與管理研究所碩士論文,2004。

[28] Hadjiconstantinou, E. and Christofides, N., “An Efficient Implementation
of an Algorithm for Finding K Shortest Simple Paths”, Networks, Vol.34(2), pp.88-101, 1999

[29] Doerner, K., Gronalt, M., Hartl, R. F., Reimann, M., Strauss, C. and Stummer, M., “SavingsAnts for the Vehicle Routing Problem,” POM Working Paper 02/2002,Department of Production and Operations Management, University of Vienna,2002.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔