用于车辆共享的移动线路推荐算法的研究与实现

摘要

随着城市现代化进程的不断加速，城市人口不断增加，人们在生活中经常会遇到早晚高峰时期堵车、打车难等问题。随着GPS、Wi-Fi、RFID以及Bluetooth等无线智能设备的普及，移动轨迹数据被各行业的信息系统不断的收集，因此利用这些数据通过城市的大数据分析与挖掘解决城市中所面临的一些困难与挑战。如今，城市交通管理方面的一些决策对市民的出行起着非常重要的作用，本文着重研究车辆共享移动线路推荐问题。该问题的目的就是对于在不同位置发出乘车请求的用户，将满足一些限制条件的多个乘客作为一个请求组合分配给行驶的车辆，使得车辆的收益最大化。求解该问题对于解决城市打车难、车辆座位利用率低、减小环境污染以及缓解交通都有非常广泛的实践意义。
　　本文设计了两个算法解决问题，分别为精确算法以及基于模拟退火的近似算法。在精确算法中，通过三个阶段解决该问题，分别为组合与剪枝、相容性剪枝，计算与推荐。第一阶段主要计算出所有的请求组合情况并通过车辆的容量的限制对请求的组合进行剪枝，车辆的容量限制就是在同一个请求组合的乘客总数不能超过车辆的当前的座位数量。第二阶段通过判断每个请求组合中用户的路径序列是否满足相容性条件，所谓的相容性条件就是在同一个组合中的用户的请求路径序列可以连接为同一条路径序列，为此本文设计了Match算法和Compatibility算法。第三阶段我们通过定义的评价函数计算每个请求组合的利润，并将利润最大的组合推荐给司机，为此我们设计了Scanning算法。另外，通过对模拟退火算法步骤的分析，本文提出了一种近似的解法SA Group Search算法。该方法中最为关键的是在迭代的过程中产生新的可行解，为此设计Produce算法通过增加请求以及对限制条件的判断等方法为每一次迭代产生新的可行解。
　　通过对比在两个真实道路网络数据以及一个人工道路网络数据集上的实验表明，本文提出的两个方法都能很好的解决车辆共享移动线路推荐问题，并且对提高座位利用率，增加司机的收入有的明显的效果，同时通过对共享车辆前后车辆的行驶距离的比较表明该问题对环境保护起着间接的作用。对于在大量的用户请求的情况下，本文提出的近似算法能够起到很好的效果。

目录

第一个书签之前