基于GPS轨迹的出租车载客路径智能推荐

发布时间：2018-02-28 00:02

本文关键词： 移动对象轨迹推荐地点多种群遗传算法路径规划　出处：《湖南科技大学》2014年硕士论文　论文类型：学位论文

【摘要】：随着GPS设备、无线通信技术以及具有GPS功能的移动终端的迅猛发展与普及应用，我们能够更加有效便利的追踪移动对象各种行为运动模式并收集其轨迹数据。作为最熟悉城市交通网络特性的出租车司机，他们很了解城市道路各时段各区域交通道路长度状况及交通路网规律，因而其能选择更为合理有效的行车路径使自己能够较好较快地抵达目的地。此外，出租车轨迹数据包含有经纬度、时间、速度等信息，具有易收集、分布广、数据大的特点，这些数据蕴含了大量出租车司机的驾驶经验。本文对这些轨迹记录数据开展有效的分析研究，挖掘有经验出租车司机在路线规划中的智能经验，能够指导驾驶新手与外来司乘人员辅助实现智能导航，也为城市规划和智能交通等辅助决策提供有力支撑。因此，本文主要开展了以下工作：（1）首先，本文以微软亚洲研究院公开的移动对象轨迹数据集为基础，对出租车移动行为模式进行分析并得到了人们在不同时段不同属性的地点行为规律。同时，本文还简单介绍了得到这些规律性知识的基于轨迹数据研究的时空数据挖掘技术，这也为后面的轨迹分析研究提供一定的知识储备。（2）我们通过分析研究移动对象的轨迹数据，得到了各时段停留点的数量，然后我们将数量与实际地理区域的进行比对，再通过与微软亚洲研究院的结果比较验证得到可行性。另外，我们采用基于时空聚类的方式获取不同时段的乘客集中地点，考虑到这些乘客集中地呈现出区域集中出现的现象，本文在设计算法时采用K-Means算法聚类出租车周围的推荐载客地点。（3）我们首先通过借鉴TSP问题经典核心思想，对路线中载客点进行最短路径研究，提炼出载客推荐点间最短路径问题的网络模型。其次，我们采用可变长度染色体的编码机制，经优化交叉，变异等操作，设计了用于解决城市道路网络的SP问题的遗传算法组件以及基于多种群遗传算法规划路径规划推荐，我们采用概率化寻优方法计算出最短路径精确解。然后，我们充分利用百度地图API的进行路线搜索服务。最后，我们对出租车行驶于城市交通网络的路径进行大量的仿真实验，并比较了多种群遗传算法、随机遗传算法、标准遗传算法等算法在城市道路实时交通网络中的性能。我们的实验结果表明，，多种群遗传算法相比其他算法，能更有效地解决优化出租车司机智能载客路径。
[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

【参考文献】