使用基因演算法求解旅行銷售員問題於自走車路徑規劃之應用實現; Solving traveling salesman problem for route planning realization of an autonomous line-tracking car by means of genetic algorithm

NCU Institutional Repository > 資訊電機學院 > 電機工程學系碩士在職專班 > 博碩士論文 > Item 987654321/61125

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

題名:	使用基因演算法求解旅行銷售員問題於自走車路徑規劃之應用實現;Solving traveling salesman problem for route planning realization of an autonomous line-tracking car by means of genetic algorithm
作者:	林勇;Lin,Yung
貢獻者:	電機工程學系在職專班
關鍵詞:	基因演算法;旅行銷售員問題旅行銷售員問題;循線自走車;Genetic Algorithm (GA);Traveling salesman Problem (TSP);autonomous line-tracking car
日期:	2013-07-30
上傳時間:	2013-08-22 12:12:38 (UTC+8)
出版者:	國立中央大學
摘要:	本論文研究如何透過基因演算法來有效率的搜尋循線自走車的路徑規劃。藉由將循線自走車的路徑規劃組成旅行銷售員的求解問題，並以基因演算法取得旅行銷售員的最佳解(Optimal solution)。本方法用於多目標點的旅行家問題求解，所完成的路徑，要求每一目標點只能通過一次，且必須回到原點。目前研究成果已經可以準確的完成目標點為10以上的路徑規劃問題。本系統使用個人電腦求解循線自走車的路徑最佳解，而計算結果則經由無線模組傳輸到循線自走車。本論文所提基因演算法包含隨機初始化、交配、突變、菁英政策、基因毀滅等主要程序，當完成最佳路徑規劃，由電腦端的無線模組傳送引導循線自走車行進。每行經一個目標點時，即由車體端無線射頻辨識(RFID)模組讀取目標點的射頻辨識標籤，判斷目標點資料後，車體進行轉向，續朝下一目標點循線前進。當目標數為10時，設定染色體數為200，最大演化代數為5000，突變率及交配率分別為0.3及0.85，求得全域最佳解機率為100%。本論文成功以基因演算法求解旅行銷售員問題之最短路徑，並以循線自走車驗證路徑規劃結果，本結果未來可應用於無人搬運車進行生產自動化配送作業。 This thesis aims to search the optimized route planning for an autonomous line-tracking car using Genetic Algorithm (GA). By formulating the route planning question as a Travelling Salesman Problem (TSP), the GA has proved its effectiveness with high accuracy in achieving the multi-target route planning of the autonomous line-tracking car, in which the route planning requested each target should be passed through only one time and the line-tracking car should return to the initial target. Our study results have successfully implemented the route planning of the line-tracking car for 10 or more targets. The optimized route planning of the autonomous line-tracking car was computed on a PC platform. The optimized solutions obtained from GA were transmitted through a wireless transmission module to the autonomous line-tracking car. The utilized GA algorithm was designed to contain several steps, including the random initialization, crossover, mutation, elite policy, gene destruction, etc. Once the optimized route has been obtained, the optimized TSP solution is transferred to guide the autonomous line-tracking car. When the autonomous link-tracking car reached each designated target, the ID tag attached on the target was sensed by a RFID module, equipped on the autonomous line-tracking car and direct the line-tracking car toward next target. It has been shown that the present system can achieve 100% accuracy for 10 targets, with chromosome number of 200, maximum evolution of 5000, mutation and the crossover rates of 0.3 and 0.85, respectively. In this thesis, the genetic algorithm successfully solved the traveling salesman problem and used it for planning the shortest path length of an autonomous line-tracking car. The study results may be helpful to the logistic transportation of automated guided vehicle in future applications.
顯示於類別:	[電機工程學系碩士在職專班] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	2408	檢視/開啟

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

社群 sharing

資料載入中.....