基于k-Regret查询的动态共乘问题研究

发布时间：2019-04-09 13:17

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

【相似文献】

相关期刊论文 前6条

1 肖习雨;张昌凡;龙永红;;基于视频的车辆违章监测方法[J];湖南工业大学学报;2009年06期

2 陈方泽，肖承德;车辆位置实时监测网的研制[J];小型微型计算机系统;1994年05期

3 ;网络话题:信息化与人性化[J];运输经理世界;2012年11期

4 雷明宇;;车载信号车辆位置信息传输技术在地铁中的应用[J];科技视界;2012年20期

5 何菲;;易到:无须拥有的专车[J];IT经理世界;2011年24期

6 ;[J];;年期

相关重要报纸文章 前2条

1 刘俊京;探索企业信息化之路[N];中国冶金报;2003年

2 记者 边金波 韩数鹏;河南联通“定位之星”服务企业用户[N];人民邮电;2004年

相关硕士学位论文 前4条

1 裴新宇;基于k-Regret查询的动态共乘问题研究[D];大连海事大学;2017年

2 王文萃;65044部队车辆位置监控系统设计与实现[D];大连理工大学;2014年

3 陈首名;基于视频的城市交通路口车辆位置信息提取方法研究[D];哈尔滨工业大学;2010年

4 范恩博;基于移动平台的公交信息化技术的设计与实现[D];天津大学;2014年

，

本文编号：2455216