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

詳目顯示:::

: 
twitterline
研究生:趙立愔
研究生(外文):ZHAO,LI-YIN
論文名稱:以無人飛行器進行物流配送路徑規劃之研究
論文名稱(外文):A Research on Logistics Distribution Path Planning for Using Unmanned Aerial Vehicle(UAV)
指導教授:方孝華方孝華引用關係
指導教授(外文):Fang,XIA-HUA
口試委員:劉育津游聖瑾鄒慶士
口試委員(外文):LIU,YU-CHINYU,SHENG-CHINTSOU,CHING-SHIH
口試日期:2017-05-26
學位類別:碩士
校院名稱:世新大學
系所名稱:資訊管理學研究所(含碩專班)
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:中文
論文頁數:44
中文關鍵詞:無人飛行器物流配送K-means路徑規劃基因演算法
外文關鍵詞:UAVLogistics distributionK-meansPath planningGenetic Algorithm
相關次數:
  • 被引用被引用:2
  • 點閱點閱:1014
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:132
  • 收藏至我的研究室書目清單書目收藏:1
2013年Amazon提出運用UAV進行宅配貨品到家的服務,陸續開始有國家之物流業者投入UAV物流服務。然而,目前美國聯邦總署的法規對於商用無人飛行器有嚴格的規範與限制;並且UAV屬於3D的飛行環境,其路徑規劃與一般傳統用於2D平面環境的路徑規劃不同。因此本研究期許國際間相關飛航法規解禁以及UAV載運能力提昇之後,當UAV應用於宅配物流時,讓決策者在安排UAV運輸排程的路徑規劃有更好的選擇。
實務上,物流中心通常是由多台運輸工具進行配送服務,而且每次的訂單群組與配送位置都不一樣,因此本研究首先會透過K-means進行訂單群組分群的處理,並將問題視為多旅行推銷員問題求解。由於多旅行推銷員問題屬於複雜的最佳化組合問題,不易在多項式時間內找到最佳解,其所需計算次數將隨著問題複雜度成指數成長,因此,本研究將採用基因演算法進行UAV的路徑規劃,藉由GA多點平行搜尋的特性,提升演算效率。
本研究系統設計分為四大部分,訂單分群、分群TSP、基因演算法設計與顧客服務水準分析。首先,訂單分群會以K-means進行訂單群組的分群,並將分群結果執行TSP的計算,作為初始群體第一個解,透過此解以亂數的方式調整作為後續產生的初始群組,接著進行GA演算法設計,其中染色體編碼方式以two-part chromosome方式呈現,並以顧客的服務水準作為適應值函數,選擇與複製的方式採二元競爭法選擇,交配與突變方式則分別採用two-part chromosome crossover與交換突變法的方式,並設定迭代的次數作為終止條件,最後則是進行顧客服務水準分析,若UAV路徑規劃的結果在顧客服務水準內,則結束運算;否則將增加一架UAV進行配送服務,即多增一群,並重新進行訂單群組的分群。
利用無人飛行器作為物流的運送服務將是未來趨勢,本研究經過證實可得到相對有效的結果,未來相關決策者根據本模型可得到較佳的決策。

In 2013, Amazon announced that it would use UAV to do home delivery services in the future. From that time many countries of logistics industry in the world began to research the area of UAV on logistics service. However, the Federal Aviation Administration's newly-proposed drone guidelines have strict restrictions of using UAV for delivery services in the United States. The UAV flight environment belongs to 3D environment which is different from the traditional path planning for 2D environment. Therefore, in this research explores the UAV using in delivery logistics, hoping this study would provide decision makers a better choice about the arrangement of the UAV’s path planning after the relevant rules of International Air Traffic Regulation are allowed and the UAV capability has progressed.
Practically, the logistics center usually has more than one conveyance to do delivery services in real life. With the change of order groups and the individual destination in this research uses K-means for clustering order groups at first, and Multiple Traveling Salesman Problem (MTSP) is regarded as solution of this study. As MTSP is a complex combination optimization problem, it is very difficult to find out optimal solution in polynomial time, and its calculation times will be with problem complex degrees into index growth. Therefore, in this study will use Genetic Algorithm (GA) to find out the path planning of UAV. GA’s characteristics of parallel multiple-point search can upgrade execution efficiency.
The system is designed into four parts, order clustering, clustering TSP, genetic algorithm, and customer service level analysis. First, order clustering would use K-means for clustering order groups. And then the clustering result would execute TSP calculation for obtaining the first result of initial population. And other results of initial population are based on the first result randomly generated. Second, genetic algorithm design would start chromosome encoding used two-part chromosome technique, and customer service level is used define fitness function. The method of selection and reproduction adopts binary tournament selection method. Two-part chromosome crossover is used in Crossover and swap mutation is adopted in Mutation. The termination condition is set by the number of iterations. Finally, we would carry out customer service level analysis, if the result of path planning for UAV is within the customer service level, operation is ended. Otherwise, we will increase a UAV for delivery services, and one group will be added and clustering order groups again.
This study has been proved to obtain an effective result. The decision maker could make decision easily by this model in the future.

目錄
摘要 I
Abstract II
目錄 IV
表目錄 VI
圖目錄 VII
第壹章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍 3
1.4 研究限制 3
1.5 研究流程 4
第貳章 文獻探討 5
2.1 無人飛行器的發展演進 5
2.1.1 軍用無人飛行器 5
2.1.2 民用無人飛行器 5
2.2 3D模擬地形 7
2.3 分群方法 8
2.3.1 階層式分群法 8
2.3.2 分割式分群法 8
2.4 路徑規劃的方法 9
2.4.1 旅行推銷員問題(TSP) 9
2.4.2 多旅行推銷員問題(MTSP) 10
2.5 基因演算法 11
第參章 研究設計 18
3.1 系統流程架構介紹 18
3.2 訂單分群 18
3.3 分群TSP路徑規劃 19
3.4 基因演算法設計 19
3.5 顧客服務水準分析 22
第肆章 實證分析 24
4.1 系統簡介 24
4.1.1 系統功能介紹 24
4.1.2 系統開發環境介紹 26
4.2 實證分析 26
4.2.1 系統參數設定 29
4.2.2 實證結果 29
第伍章 結論與建議 33
5.1 結論 33
5.2 未來研究建議 33
參考文獻 34
一、 中文文獻 34
二、 英文文獻 35
表目錄
表2-1 Amazon Prime Air規格 6
表2-2 FAA法規 7
表2-3各國UAV物流狀況 7
表2-4多旅行推銷員問題求法 11
表4-1地圖參數設計 25
表4-2電腦環境 26
表4-3系統程式環境 26
表4-4地圖參數設定 26
表4-5 MTSP參數設定 26
表4-6訂單位置與UAV中心位置座標 27
表4-7 K-means分群結果 28
表4-8 K-means分群組內變異 28
表4-9 K-means分群組間變異 29
表4-10 K-means分群變異數分析表 29
表4-11 GA參數設定 29
表4-12 10次演算結果統計資料 32
表4-13 10次演算結果與前20次平均結果之一致性檢定 32
圖目錄
圖1-1研究架構圖 4
圖2-1 TSP完整路徑圖 9
圖2-2 MTSP完整路徑圖 10
圖2-3基因演算法運作架構圖 11
圖2-4二元編碼示例 12
圖2-5實數編碼示例 12
圖2-6符號編碼示例 12
圖2-7 one chromosome technique示例 12
圖2-8 two chromosome technique示例 13
圖2-9 two-part chromosome technique示例 13
圖2-10單點交配法示例 15
圖2-11雙點交配法示例 15
圖2-12部分對應交配示例 16
圖2-13單點無性交配示例 16
圖2-14 two-part chromosome crossover示例 17
圖2-15單點突變法示例 17
圖2-16交換突變法示例 17
圖3-1系統流程架構圖 19
圖3-2本研究染色體設計示例圖 20
圖3-3本研究two-part chromosome crossover示例圖 21
圖3-4本研究交換突變法示例圖 22
圖4-1系統介面 25
圖4-2模擬地形圖 25
圖4-3城市大複雜度高模擬地形圖 27
圖4-4初始參數設定之結果 30
圖4-5一千代迭代次數之結果 30
圖4-6一千代迭代最佳解分群圖 31
圖4-7 UAV路徑規劃 31
參考文獻
一、中文文獻
1.尤濬哲,2015,應用地域多螞蟻演算法建構物流派遣支援系統之研究,國立中山大學資訊管理學系研究所博士論文。
2.王曉娟(2015年7月15日)。凱度最新發布「加速電子商務在民生消費品市場的成長–2015年版」報告。(2016年11月17日),取自:http: //www. kantar worldpanel.com/tw/news/Accelerating-the-growth-of-e-commerce-2015-Edition
3.李卓軒,2013,基於多目標最佳化基因演算法之民用UAV路徑規劃,國立宜蘭大學資訊工程研究所碩士論文。
4.無人機快遞大盤點:只知道這幾家無人機快遞你就out啦(2016年07月27日)。每日頭條。(2016年11月27日),取自:https://kknews.cc /tech/yn9ejn.html
5.施雅月、賴錦慧(譯)(2008)。資料探勘Introduction to Data Mining(原作者:P. N. Tan, and M. Steinbach, and V. Kumar)。台北市:培生教育出版股份有限公司。(原著出版年:2005)
6.范雯婷,2008,以基因演算法探討多旅行銷售員問題,元智大學資訊管理學系碩士論文。
7.徐百輝(2013年6月)。無人飛行載具簡介及其於測繪領域之應用。杜風。(2016年11月17日),取自:http://www.ntucenewsletter.tw/vol.67/T4_1n.html
8.張超翔(2008年12月15日)。台灣宅配系統之業務發展分析研究,網路社會學通訊期刊,75。(2016年10月26日),取自:http://www.nhu.edu.tw/ ~society/e-j/75/75-02.htm
9.許晉嘉,2003,宅配業貨物配送路線規劃問題之研究,國立成功大學交通管理學系碩士論文。
10.連忠銓,2010,動態即時路徑規劃應用物流管理之研究,醒吾技術學院資訊科技應用研究所碩士論文。
11.陳逸榮,2012,進化式演算法求解大規模旅行銷售員問題之探討,世新大學資訊管理學系碩士論文。
12.陳曉莉(2015年3月26日)。Amazon:機種都已被淘汰不飛了FAA才給無人機測試許可。iThome。(2016年10月26日),取自:http://www.ithome. com.tw/news/94818
13.無人機之家(2016年6月7日)。無人機知識系統盤點看完後了解無人機(2016年11月27日),取自:http://www.wrjzj.com/wrjjs/kpmc/2558. html
14.黃逸平、賴子韶(2015)。無人機旋風席捲全球-帶你認識火紅無人機,思考台灣高飛契機。DIGITIMES。(2016年10月26日),取自:http://mms.digi times.com/tw /indepth/2015_drone/index.html
15.楊安琪(2016年6月24日)。FAA 商用無人機法規出爐,放寬操作者資格及部分規範。TechNews。(2016年10月26日),取自:http://technews. tw/2016/06/24/faa-finalize-rules-for-small-unmanned-aircraft-systems/
16.蔡志強,2003,以蟻群系統建立物流宅配最佳化配送路徑規劃。國立屏東科技大學工業管理學系碩士論文。
17.蘇育德、蔡曜陽(2013年5月29日)。無人飛行載具運用研析。(2016年10月26日),取自:http://defence.hgsh.hc.edu.tw/announce.php?Submenu=3&ai d=1104
二、英文文獻
1.Amazon Prime Air. (n. d.). Retrieved November 05, 2016, from https://www. Am azon.com/b?ref=tsm_1_tw_s_amzn_mx3eqp&node=8037720011
2.Bektas, T. “The Multiple Traveling Salesman Problem:An Overview of Formulations and Solution Procedures,” Omega, Vol. 34, 2006, pp. 209-219
3.Carter, E., and Ragsdale, C. “A New Approach to Solving the Multiple Traveling Salesperson Problem Using Genetic Algorithms,” European Journal of Operational Research, Vol. 175, 2006, pp. 246-257
4.Holland, J. (1975). “Adaptation in Natural and Artificial System,” University of Michigan Press, Ann Arbor, Michigan.
5.Kim, J. (2014, October 16). How the World Orders and Delivers in 10 Charts. QUARTZ. Retrieved November 17, 2016, from http://qz.com/281051/how-the -world-orders-and-delivers-in-10-charts/
6.Mittal, S., and Deb, K. “Three-Dimensional Offline Path Planning for UAVs Using Multiobjective Evolutionary Algorithms,” Proceeding of IEEE Congress on Evolutionary Computation (CEC2007), Singapore September. 25-28, pp. 3195-3202
7.Yuan, S., and Skinner, B., and Huang, S., and Liu, D. “A New Crossover Approach for Solving the Multiple Travelling Salesmen Problem Using Genetic Algorithms,” European Journal of Operational Research, Vol. 228, 2013, pp. 72-82

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔