动态共乘问题的算法研究

发布时间：2024-02-21 00:22

　　以共享交通工具为特点的车辆共乘,可以有效减少路上行驶车辆数量,对降低出行费用,缓解交通拥堵和减轻环境污染有着重要的意义。大数据背景下智能出行的发展趋势就是在车辆行驶中对乘客请求进行实时匹配的动态共乘。虽然动态共乘已经在学术界进行了多年的研究,但由于实际道路网络的复杂性,离线预约的不灵活性和资源有限等原因,对它的研究仍旧缺乏实践的普适性。特别是在现代大城市的交通网络中,道路网络通常更为复杂,有许多的单向路和高架桥路段。受此现状的启发,本文考虑了动态共乘匹配算法中尚未深入研究的真实道路信息。主要工作成果如下:(1)整理介绍了国内外车辆共乘的研究现状以及相关的理论。(2)研究了动态车辆共乘的模型与匹配算法,针对动态共乘SHAREK系统的匹配算法中的不足进行修改,并在匹配算法中加入了单向路中高架桥路段作为启发式信息进行预处理,通过两段算法来提前筛选一些不会成为Skyline结果的司机,减少了复杂的实际道路网络计算,提高匹配算法的效率。(3)使用MNTG网站生成的数据集进行实验,对本文的算法进行评估,与SHAREK进行比较,结果表现了更高的成功率;通过实验验证了考虑单行路因素能够有效的缩短系统的...

【文章页数】：75 页

【学位级别】：硕士

【部分图文】：

图２．?１?ＶＲＰ求解算法分类??Ｆｉｇ．２．１?Ｃｌａｓｓｆｉｃａｔｉｏｎ?ｏｆ?ｓｏｌｖｉｎｇ?ｍｅｔｈｏｄｓ??２．２车辆共乘及相关研究??

?大连海事大学硕士学位论文???机制和生成解的算法各不相同。其中最经典的智能启发式算法包括：禁忌搜索算法［３５］、??模拟退火算法［３６］、遗传算法［３７］、蚁群算法［３８］、粒子群优化算法［３９］和人工神经网络算法。??＾?精确算法??１／＾??Ｉ?＼?，?，?＾构造启发式算法....

图２．?５?ＭＮＴＧ的Ｗｅｂ界面??Ｆｉｇ．?２．５?Ｔｈｅ?Ｗｅｂ?ｉｎｔｅｒｆａｃｅ?ｏｆ?ＭＮＴＧ??ＭＮＴＧ在两个领域具有很好的可扩展性：??（１）可以轻松扩展以支持各种道路网络交通生成器

乘问题的算法研究???应的改善包装，使其易于使用、配置和可以获取到任意区域的道路网络交通数据集。要??通过ＭＮＴＧ生成道路网络交通数据，用户只需使用其用户友好的Ｗｅｂ界面在地图上指??定任意空间范围，选择对应的道路网络交通生成的方法，并将道路网络交通生成的请求??提交给服务器即可....

图３．?１价格模型??

?大连海事大学硕士学位论文???要搭载乘客ｒ跑完乘客的行程（仍办「７＞扣），直到乘客的终点最后，司机从乘客的??终点Ａ？返回到司机的终点）。??

图４．?１?ＳＨＡＲＥＫ数据集的路网图??Ｆｉｇ．?４．１?Ｒｏａｄ?ｎｅｔｗｏｒｋ?ｏｆ?ｔｈｅ?ＳＨＡＲＥＫ?ｄａｔａ?ｓｅｔ??

?动态共乘问题的算法研宄???４动态共乘匹配算法的性能分析??４．１实验数据??４．１．１数据集??本文的实验数据均通过Ｍｉｎｎｅｓｏｔａ?Ｔｒａｆｆｉｃ?Ｇｅｎｅｒａｔｏｒ（ＭＮＴＧ）生成。ＭＮＴＧ是一款道??路网络交通生成器，由明尼苏达州大学开发。ＭＮＴＧ生成器集成了?Ｏｐｅ....

本文编号：3904749