跳到主要內容

臺灣博碩士論文加值系統

(3.236.84.188) 您好!臺灣時間:2021/08/05 01:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:徐瑋朗
研究生(外文):Wei-Lang Shiu
論文名稱:蟻群演算法應用於宅配業送路徑規劃
論文名稱(外文):The Application of Ant Colony Optimization on Routing Planning for Home-Delivery Distribution
指導教授:虞台文
指導教授(外文):Tai-Wen Yue
口試委員:虞台文
口試委員(外文):Tai-Wen Yue
口試日期:2014-07-22
學位類別:碩士
校院名稱:大同大學
系所名稱:資訊工程學系(所)
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:中文
論文頁數:63
中文關鍵詞:宅配業蟻群演算法車輛問題
外文關鍵詞:Home-DeliveryACOVRP
相關次數:
  • 被引用被引用:2
  • 點閱點閱:96
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
宅配業配送路線規劃之目的在於規劃合適的運送路線,滿足顧客的需求,使運送員以最小運送成本和最短運送距離,將貨物送達目的地為目標。多銷售員問題(multiple traveling salesman problem, MTSP)有許多種類型,其中車輛路徑問題(Vehicle Routing Problem,VRP)廣為人探討。大多數VRP是屬於NP-hard的問題,若要求取最佳解,則其計算時間將會隨著點數的增加呈現指數的成長,因此問題規模大時求取最佳解往往相當費時。近年來國內外學者提出了大量啟發式演算法,並取得了一些成果。本文針對單車場多銷售員問題(single depot Vehicle Routing Problem)和多車場多銷售員問題(Multi-depots Vehicle Routing Problem)進行討論。

本研究利用蟻群演算法結合最小-最大距離化,以車輛數作為分群的依據,設定每隻螞蟻走第一步後會進行距離比較,只選出走最短距離的螞蟻,且其餘的將都退回出發點,依此方式尋找較短的路徑,進行路徑建構。因此,可達到將每個派送員所走的距離接近,且總距離較短。另一方面,透過求解標竿測試例題之案例和Hongqiang Zheng論文之例題來驗證本研究所建構之模式與方法,經由個別測試後,發現本研究所提出之方法,有不錯求解績效。
The purpose of the Home-delivery is to planning a suitable transport routes to Satisfy demands of customers, make the delivery staff can deliver goods as the target in minimize transport costs and the shortest distance transport. Multiple traveling salesman problem, (MTSP) has lots of types, widely-discussed in Vehicle Routing Problem,(VRP).Most of VRP is the question belong NP-hard, if request to take the best solution, then the number of points will be presenting growth index as the calculation time increases. So obtaining the best solution when problems in large scale always quite time-consuming. In recent years, scholars made a number of heuristic algorithms and obtained some results. In this paper, single depot Vehicle Routing Problem and Multi-depots Vehicle Routing Problem will be discussed.

In this study, use ant colony algorithm combined minimum - maximum distance, the number of vehicles as the basis for grouping, setting the distance comparison after each ant taken the first steps, only choose the ants walked shortest distance, and remainder will have to return to the starting point. According to this way to find a shorter path, conducted the path construct. So each delivery staff can be reached by walking distance proximity, and the total distance is shorter.in the other side, through solving the case of the benchmark test examples and examples in the paper of Hongqiang Zheng to verify the mode and method of construct in this study, after test respectively, the method proposed by this study found that there is a good achievement for solving.
謝誌i
摘要ii
ABSTRACTiii
目次iv
圖目錄vi
表目錄viii
第一章 緒論1
1.1研究背景與動機1
1.2研究目的1
1.3研究範圍與限制3
1.4研究流程3
1.5論文架構4
第二章 相關研究探討5
2.1前言5
2.2宅配業5
2.2.1宅配的定義5
2.2.2台灣宅配業現況6
2.2.3宅配業與傳統貨運之比較7
2.2.4宅配業運送流程8
2.3蟻群演算法9
2.3.1蟻群演算法之理論9
2.3.2蟻群演算法之演進11
2.3.2.1螞蟻系統(Ant System, AS)11
2.3.2.2蟻群系統(Ant Colony System, ACS)13
2.3.2.3蟻群優化法(Ant Colony Optimization, ACO)14
2.4車輛途程問題15
2.4.1車輛途程之種類15
2.4.2車輛途程之求解方法17
第三章 研究方法20
3.1研究模型20
3.2最小-最大總距離之數學模組21
3.3路徑規劃提出最佳化之演算法22
3.3.1基本假設與限制22
3.3.2符號定義23
3.3.3蟻群算法公式24
3.4演算法25
第四章 實驗分析與設計27
4.1問題描述27
4.2程式介面介紹27
4.3測試例題建立29
4.3.1 VRP例題測試30
4.3.2 多車場例題測試33
4.3.3 Hongqiang Zheng論文例題測試37
4.4討論40
第五章 結論50
5.1結論50
5.2未來研究方向50
參考文獻52
〔1〕周承德,「智慧型物流配送路線系統之研究」,知識社群與資訊安全學術
研討會,2007。
〔2〕黑貓宅急便網站http://www.t-cat.com.tw/company/about.aspx
〔3〕洪珈萱、羅冠傑、林冬香,「宅配服務品質提升之探討-以大學生為主要消費族群」,中華大學運輸科技與物流管理學系,民國103。
〔4〕林大傑,「宅配路線規劃應用禁制搜尋法之研究」,逢甲大學交通工程與管理學系碩士班,民國95年。
〔5〕許晉嘉,「宅配業貨物配送路線規畫問題之研究」,國立成功大學交通管理科學研究所,民國92年。
〔6〕蔡志強,「以蟻群系統建立物流宅配作家畫配送路徑規劃」,國立屏東科技大學工業管理所,民國93年。
〔7〕林志鴻、許晉嘉,「宅配業車輛路線問題之研究」,中華民國運輸計畫季刊運輸計劃季刊,第三十五卷第四期,頁443-474,民國95年。
〔8〕Dorigo, M., and L.M.Gambardella, “Ant colonies for the traveling salesman problem,”BioSystems, 43, pp.73-81,1997b.
〔9〕Dorigo, M., V. Maniezzo and A. Colorni, “Ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol.26, no. 1, pp.29-41, 1996.
〔10〕Dorigo, M., V. Maniezzo and A. Colorni, “The ant system: An
autocatalytic optimizing process,”Technical Report no. 91-016 Revised,
Politecnico di Milano, Italy,1991b.Dorigo, M., V. Maniezzo, and A.
Colorni, “The ant system: An autocatalytic optimizing process,”Technical
Report no. 91-016 Revised, Politecnico di Milano, Italy,1991b.
〔11〕Dorigo, M. and L.M. Gambardella, “Ant colony system:cooperative
learning approach to the traveling salesman problem,”IEEE Transitions
on Evolutionary Computation, vol.1, no.1, pp.53-66,1997a.
〔12〕李士勇,「蟻群算法及其應用」,哈爾濱工業大學出版社,哈爾濱,2004
〔13〕謝騰飛,「使用螞蟻演算法求解隨機需求車輛路徑問題---以販賣機補
貨車為例」,國立高雄第一科技大學運籌管理系碩士班,民國99年。
〔14〕Bodin人 Bodin, L., Golden, B., Assad, A., and Ball, M. (1983). “Routing and Scheduling of Vehicle and Crew: The State of Art. Special Issue of Computers and Operations Research,” 10(2), 63-211.
〔15〕NEO http://neo.lcc.uma.es/vrp/
〔16〕Hongqiang Zheng, Yongquan Zhou, Qifang Luo, “A hybrid Cuckoo
Search Algorithm-GRASP for Vehicle Routing Problem,”Journal of
Convergence Information Technology(JCIT), Volume8, Number3,Feb 2013.
〔17〕Lingxia Liu、Qiang Song,“Min-max Vehicle Routing Problem Based
on Ant Colony Algorithm,”International Journal of Hybird Information
Technology, Vol.6, No.4, July 2013, 105-116
〔18〕Tolga Bektas,“The multiple traveling salesman problem:an overview of
formulations and solution procedures,” 8 January 2005,209-219.
〔19〕Koushik Srinath Venkata Narasimha,“Ant Colony Optimization
Technique to Solve Min-Max MultiDepot Vehicle Routing
Problem,”University of Cincinnati,2011.
〔20〕許哲斌,「在需求變動下具有軟時窗限制之同時收、送貨車輛途程問
題」,國立雲林科技大學工業工程與管理研究所,民國97年。
〔21〕Transportion Network Laboratoryhttp://140.113.119.114/network
〔22〕鍾政偉、江昶翰、蔡鳳珊,「應用螞蟻演算法於求解考慮時間窗、多
車種與多場站貨、多車種與多場站貨運業的最適車輛指派與收、卸貨
路徑規畫問題之研究」,國科會計畫案,民國95年8月至96年7月。
〔23〕羅敏華,「蟻群最佳化演算法於載重限制之車輛途程問題的研究」,私
立員智大學工業工程與管理研究所,民國92年。
〔24〕Bharath Manicka Vasagam,“Ant Colony Algorithm and Genetic Algorithm for Multiple Travelling Salesmen Problem,”University of Salford Manchester,2012.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top