本文關鍵詞： 移動對象軌跡 推薦地點 多種群遺傳算法 路徑規(guī)劃　出處：《湖南科技大學》2014年碩士論文　論文類型：學位論文

【摘要】：隨著GPS設備、無線通信技術以及具有GPS功能的移動終端的迅猛發(fā)展與普及應用，我們能夠更加有效便利的追蹤移動對象各種行為運動模式并收集其軌跡數(shù)據。作為最熟悉城市交通網絡特性的出租車司機，他們很了解城市道路各時段各區(qū)域交通道路長度狀況及交通路網規(guī)律，因而其能選擇更為合理有效的行車路徑使自己能夠較好較快地抵達目的地。此外，出租車軌跡數(shù)據包含有經緯度、時間、速度等信息，具有易收集、分布廣、數(shù)據大的特點，這些數(shù)據蘊含了大量出租車司機的駕駛經驗。本文對這些軌跡記錄數(shù)據開展有效的分析研究，挖掘有經驗出租車司機在路線規(guī)劃中的智能經驗，能夠指導駕駛新手與外來司乘人員輔助實現(xiàn)智能導航，也為城市規(guī)劃和智能交通等輔助決策提供有力支撐。因此，本文主要開展了以下工作： （1）首先，本文以微軟亞洲研究院公開的移動對象軌跡數(shù)據集為基礎，對出租車移動行為模式進行分析并得到了人們在不同時段不同屬性的地點行為規(guī)律。同時，本文還簡單介紹了得到這些規(guī)律性知識的基于軌跡數(shù)據研究的時空數(shù)據挖掘技術，這也為后面的軌跡分析研究提供一定的知識儲備。 （2）我們通過分析研究移動對象的軌跡數(shù)據，得到了各時段停留點的數(shù)量，然后我們將數(shù)量與實際地理區(qū)域的進行比對，再通過與微軟亞洲研究院的結果比較驗證得到可行性。另外，我們采用基于時空聚類的方式獲取不同時段的乘客集中地點，考慮到這些乘客集中地呈現(xiàn)出區(qū)域集中出現(xiàn)的現(xiàn)象，本文在設計算法時采用K-Means算法聚類出租車周圍的推薦載客地點。 （3）我們首先通過借鑒TSP問題經典核心思想，對路線中載客點進行最短路徑研究，提煉出載客推薦點間最短路徑問題的網絡模型。其次，我們采用可變長度染色體的編碼機制，經優(yōu)化交叉，變異等操作，設計了用于解決城市道路網絡的SP問題的遺傳算法組件以及基于多種群遺傳算法規(guī)劃路徑規(guī)劃推薦，我們采用概率化尋優(yōu)方法計算出最短路徑精確解。然后，我們充分利用百度地圖API的進行路線搜索服務。最后，我們對出租車行駛于城市交通網絡的路徑進行大量的仿真實驗，并比較了多種群遺傳算法、隨機遺傳算法、標準遺傳算法等算法在城市道路實時交通網絡中的性能。我們的實驗結果表明，，多種群遺傳算法相比其他算法，能更有效地解決優(yōu)化出租車司機智能載客路徑。
[Abstract]:With the rapid development and popularization of GPS devices, wireless communication technologies and mobile terminals with GPS functions, We can more effectively track the movement patterns of moving objects and collect track data. As taxi drivers who are most familiar with the characteristics of urban transportation network, They have a good understanding of the length of each region of the city road and the regularity of the traffic network, so they can choose more reasonable and effective traffic paths so that they can reach their destination better and faster. Taxi track data packet contains longitude, latitude, time, speed and other information. It is easy to collect, widely distributed, and has large data. These data contain a large number of taxi drivers' driving experience. This paper carries out an effective analysis and research on the track record data, mining the intelligent experience of experienced taxi drivers in route planning. It can guide the novice driver and the foreign rider to help realize the intelligent navigation, and it also provides the powerful support for the city planning and the intelligent transportation and so on. Therefore, this paper mainly carries out the following work:. First of all, based on the track data set of mobile objects published by Microsoft Asia Research Institute, this paper analyzes the mobile behavior patterns of taxis and obtains the locational behavior patterns of people at different time and different attributes. At the same time, This paper also briefly introduces the spatio-temporal data mining technology based on trajectory data research to obtain these regular knowledge, which also provides a certain knowledge reserve for the future trajectory analysis research. By analyzing and studying the trajectory data of moving objects, we get the number of stopping points in each time period, and then we compare the number with the actual geographical area. In addition, we use spatio-temporal clustering method to get passenger concentration locations at different periods of time, considering the phenomenon that these passengers are concentrated in different regions. In this paper, K-Means algorithm is used to cluster the recommended passenger locations around taxis. Firstly, we use the classical core idea of TSP problem for reference to study the shortest path of passenger points in the route, and extract the network model of the shortest path problem between passenger recommendation points. Secondly, we adopt the coding mechanism of variable length chromosomes. After optimizing the operation of crossover and mutation, the genetic algorithm component for solving the SP problem of urban road network and the path planning recommendation based on multi-population genetic algorithm are designed. We use probabilistic optimization method to calculate the exact solution of the shortest path. Then, we make full use of Baidu map API for route search service. Finally, we do a lot of simulation experiments on the path of taxi running in urban traffic network. The performance of multi-population genetic algorithm, stochastic genetic algorithm and standard genetic algorithm in urban road real-time traffic network is compared. Our experimental results show that the multi-population genetic algorithm is better than other algorithms. Can more effectively solve the optimization of taxi drivers intelligent passenger path.
【學位授予單位】：湖南科技大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：U495;TP311.13

【參考文獻】

相關期刊論文 前1條

1 劉大有;陳慧靈;齊紅;楊博;;時空數(shù)據挖掘研究進展[J];計算機研究與發(fā)展;2013年02期

相關博士學位論文 前1條

1 張治華;基于GPS軌跡的出行信息提取研究[D];華東師范大學;2010年

本文編號：1544892