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