原文传递
基于k-Regret查询的动态共乘问题研究
| 论文题名： | 基于k-Regret查询的动态共乘问题研究 |
| 关键词： | 动态共乘;后悔查询;车辆过滤;方向约束;动态匹配;顺风车服务 |
| 摘要： | 随着经济的发展和城市化进程的推进，城市交通越来越拥堵，出行问题受到民众和相关管理部门的广泛关注。目前城市交通中，存在车辆空载率高的问题，共乘是一种降低空载率、缓解交通拥堵的有效解决方案。目前，滴滴、Uber等出行软件提供了网约车及顺风车等服务，方便民众出行的同时在一定程度上缓解了交通拥堵。但是当前的顺风车服务需要提前预定以及人为规划路线，未能处理实时提交的拼车出行请求，完成动态共乘服务。 本论文研究内容是将实时提交的出行请求与路网上行驶的车辆进行动态匹配的动态共乘出行问题。动态共乘问题的研究框架主要由车辆索引构建、路径规划、车辆过滤、车辆-请求匹配四部分组成，本文的研究工作集中在车辆过滤和车辆-请求匹配模块。在车辆索引方面，本文采用已有的网格索引，该索引结构简单高效，能满足车辆位置快速动态更新的索引要求。在路径规划方面，由于多乘客的路径规划是旅行商问题，本文采用简洁有效的插入策略下的路径规划方式。 在车辆过滤阶段，发现车辆原路径可视为插入路径规划后新路径的简化轨迹，结合方向保证的轨迹简化思想，本文提出了满足方向约束的车辆过滤算法。该算法借助满足方向约束的可探索范围，对不满足约束条件的车辆进行过滤从而得到候选集，并从理论上证明探索范围的合理性。 在车辆-请求匹配阶段，为弥补已有算法无法满足乘客个性化出行需求的不足，可使用Skyline查询选择匹配车辆，但Skyline查询结果集的体积不受约束，可依据乘客选择的偏好或以往出行习惯确定的偏好函数，选择此时得分最高的车辆进行车辆-请求匹配。本文提出了基于k-Regret查询的匹配算法，该算法对已完成路径规划的候选车辆从共乘车费和到达延时两个维度进行共乘损失评估，选择损失最大的乘客作为代表表示整个车辆并进行k-Regret查询得到最大损失最小化的结果集，乘客根据自身偏好选择匹配度更高的车辆完成出行请求从而提升出行质量;进一步地，本文考虑已有乘客的车辆所包含的偏好信息，形成具有强约束的后悔查询，通过消除部分非最优解，提升查询效率。 实验部分设计并实现原型系统，采用真实路网数据和请求数据集验证本文提出算法的有效性和高效性。 |
| 作者： | 裴新宇 |
| 专业： | 计算机科学与技术 |
| 导师： | 宁博 |
| 授予学位： | 硕士 |
| 授予学位单位： | 大连海事大学 |
| 学位年度： | 2017 |
| 正文语种： | 中文 |
检索历史
应用推荐
