行車導航是一項很熱門的需求應用，靠著手持裝置與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
