應用基因演算法於智慧型行車資訊系統尋找最短時間路徑

Tunghai University Institutional Repository > 工學院 > 資訊工程學系所 > 碩士論文 > Item 310901/2659

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://140.128.103.80:8080/handle/310901/2659

题名:	應用基因演算法於智慧型行車資訊系統尋找最短時間路徑
其它题名:	A Genetic Algorithm for Finding Routes with Shortest Driving Time in Intelligent Transportation Systems
作者:	李嘉仁 Li, Chia-Ren
贡献者:	林祝興 Lin, Chu-Hsing 東海大學資訊工程學系
关键词:	基因演算法;智慧型行車資訊系統;最佳路徑;嵌入式系統;最短時間路徑 Genetic Algorithm;Intelligent Transportation System;Optimal Route;Embedded System;Shortest Time Path
日期:	2008
上传时间:	2011-03-23T05:56:29Z (UTC)
摘要:	行車導航是一項很熱門的需求應用，靠著手持裝置與GPS的普及性，人人都可以進行導航操作。而導航的準確性與快速性一直是大家要求的，在地圖資料改良與實際經驗下，這二項要求也漸漸達到完善的目標。為了提供更多的資訊，行車導航也開始需要考慮即時車流量與車子的行駛速率等，因系統的變因增加，計算所需的資源也就需要越多，而基因演算法可以在不需要耗用太多資源下解決這類的問題。基因演算法由演化法則的概念而來，藉由可以表現系統狀態的染色體(chromosome)對問題進行編碼，再透過交配(crossover)、突變(mutation)這些基因演算法內的操作方法，使最佳解逐漸逼進出來。基因演算法解決最短路徑問題的效率不錯，且節點數很多的情況下仍然收斂很快。一般針對行車導航的問題只是尋找出最短的行駛路徑而已，沒有考量到在不同路況車子也是會有不同的行駛速率，本文在此對這類的問題加以敘述，並說明使用基因演算法的解決辦法，而這類型的問題變化種類還有很多，多半只需要重新調整基因演算法的一些參數，就可以一樣簡便的尋求其解。 The route guidance system, which provides driving advice based on traffic information about an origin and a destination, has become very popular along with the advancement of handheld devices and the global position system. Since the accuracy and efficiency of route guidance depend on the accuracy of the traffic conditions, the route guidance system needs to include more variables in calculation, such as real time traffic flows and allowable vehicle speeds. As variables considered by the route guidance system increase, the cost to compute multiplies. As handheld devices have limited resources, it is not feasible to use them to compute the exact optimal solutions by some well-known algorithm, such as the Dijkstra’s algorithm, which is usually used to find the shortest path with a map of reasonable numbers of vertices. To solve this problem, we propose to use the genetic algorithm to alleviate the rising computational cost. We use the genetic algorithm to find the shortest time in driving with diverse scenarios of real traffic conditions and varying vehicle speeds. The effectiveness of the genetic algorithm is clearly demonstrated when applied on a real map of modern city with very large vertex numbers
显示于类别:	[資訊工程學系所] 碩士論文

文件中的档案:

档案	大小	格式	浏览次数
096THU00394004-001.pdf	1793Kb	Adobe PDF	860	检视/开启

在THUIR中所有的数据项都受到原著作权保护.

数据加载中.....