智慧型運輸系統（Intelligent Transportation Systems, ITS）係透過通訊系統即時的溝通與連結，改善或強化人、車、路之間的互動關係，提升用路人的交通服務品質與績效。本論文以基因演算法為主要演算法，並輔以雲端運算架構(MapReduce)加速地圖資訊的運算，再配合圖層的切割與雲端計算結果再利用概念，實現”部分路徑可再利用性”，以達到節省時間並增進導航效能目的，並有助於提升整體導航之效率與準確度。從實驗結果中，我們觀察到在地圖上節點數目愈多的情況下，基因演算法所需要的執行時間也相對的愈多，而求得的近似最佳解的誤差也愈大。且根據不同染色體初始化的方式，以及使用不同雲端運算架構之回饋運算機制，在節點數目龐大的地圖上可以避免初始化失敗或陷入演算法容易過早收斂而導致無法找到近似最佳解的情形。隨著節點數劇烈增加，基因演算法配合雲端技術(MapReduce)可以在不需耗用太多資源就可以解決這類問題。實驗結果也顯示我們獲得較快及較佳的近似最佳解。 Intelligent Transportation System (ITS) provides real-time communications and connections; it increases and enhances interactions among people, and vehicles and improves traffic service quality. In this thesis, we propose to use a genetic algorithm, which is boosted by cloud computing infrastructure (MapReduce) to accelerate computation of map information. In addition, we use the concept of map layers to realize the ideas of “partial paths reusability” and “cloud computing results reusability” to enhance the navigation performance and improve the efficiency and accuracy of the overall navigation system. From the experiments, we observed that when the number of nodes of the map increases, the required execution time of the genetic algorithm increases, and the difference between the approximately optimal solution and the optimal solution increases as well. Also, for maps with a large number of nodes, one can use different chromosome initialization settings and different feedback mechanisms in cloud computing, to avoid problems such as chromosome initialization failure or premature convergence of the genetic algorithm that makes it very hard or impossible to find the approximately optimal solution in time. For applications with dramatic number of nodes, the proposed approach using the genetic algorithm and cloud technologies (MapReduce) is a suitable solution since it can offer approximate solutions without consuming lots of resources. The experimental results also showed that the proposed approach can obtain approximately optimal solutions faster and better.
