原文传递
基于交通大数据的动态拼车调度算法研究
| 论文题名： | 基于交通大数据的动态拼车调度算法研究 |
| 关键词： | 拼车调度算法;搜索策略;交通大数据;数据挖掘 |
| 摘要： | 随着城市汽车数量呈现出爆炸性增长趋势，引发了严重的交通堵塞和环境污染问题。一个高效的拼车系统是一种有效的解决方案，它可以在满足乘客需求的同时，提高出租车司机的收入，同时可以减少环境污染和能源消耗。随着智能手机 GPS技术的不断成熟，基于智能手机 GPS数据实现一个高效的拼车调度系统现已成为建设现代化城市的迫切需求。然而，设计一个高效的拼车算法是非常具有挑战性的工作。与非拼车调度相比，拼车调度需要更加复杂的调度策略。在实际的应用系统中，拼车是一个动态变化的过程，在做调度优化的同时，也需要保证实时性。拼车另一个具有挑战性的原因是乘客的查询和出租车的位置信息都是高度动态变化的，而且很难预测。 为了解决上述问题，在本文中我们通过对交通大数据进行数据挖掘及分析构建了一种基于打车热点的出租车拼车调度系统，它可以有效的对乘客打车请求提供实时拼车服务，并生成相应的调度方案来满足乘客需求。与此同时，该系统可以显著减少出租车总的行驶距离。在我们的方法中，主要分为两个阶段，搜索阶段和调度阶段。在搜索阶段，提出了一个基于时间二分法的搜索策略来快速高效检索可能满足乘客打车需求的出租车候选集。在调度阶段，根据打车请求中的限制，检查搜索阶段得到的出租车候选集中的每一辆出租车，并从中选出插入打车请求后平均满意度最大的出租车来为乘客提供服务。为了减少空载率，针对空车我们提出了一种基于打车热点的调度策略，并对地图数据的存取进行了优化设置，其中热点的选取、打车需求量预测、空车调度范围等参数都通过对真实打车数据分析进行了合理的设置。之后，我们考虑到大数据的应用场景，给出了拼车调度系统的Spark平台实现，考虑到实时性我们采用Spark Streaming和Kafka消息队列等技术对平台的数据接收、数据处理、数据反馈各个模块进行了合理设计。 最后，我们采用一个打车请求生成器生成的在北京朝阳区一天包含101952次打车请求的大规模的数据集来检验我们的系统。结果表明，我们提供的拼车调度方法和不拼车相比可以在节省30%行驶距离的同时得到40%的服务率提升，并且与已有的方法相比服务率提升了15%、行驶距离减少了17%以上。 |
| 作者： | 高健人 |
| 专业： | 计算机应用技术 |
| 导师： | 申彦明 |
| 授予学位： | 硕士 |
| 授予学位单位： | 大连理工大学 |
| 学位年度： | 2017 |
| 正文语种： | 中文 |
检索历史
应用推荐
