大规模拼车算法研究进展

随着共享经济的发展,拼车这一由多位乘客协商共同乘坐同一辆车并分担费用的共享出行模式正得到广泛应用.在移动互联网与普适计算的推动下,拼车体现出数据量大、动态性强、目标多样、应用范围广等新特点.这些新特点使得求解大规模拼车问题的难度大大增加,并催生了众多大规模拼车算法的学术研究.拼车中各类关于社会影响因素的实际问题也成为新型研究热点.为了面向大规模拼车算法进行系统性介绍,首先介绍了拼车问题的概念定义与工作流程.随后,对大规模拼车系统的核心算法问题,即路线规划问题进行了系统地分类、介绍与分析,并进一步详细讨论了大规模拼车涉及的激励机制、隐私保护、安全保障等社会影响因素.最后,分析展望了该领域未来的潜在研究方向,为从事拼车算法的相关研究人员和从业者提供参考和帮助.

分车收发车辆路径问题的三个启发式算法之比较

车辆路径问题已经出现了很多的变种.在这些扩展的VRP问题当中,分车收发车辆路径问题就是其中之一.本文针对这一问题在已有的模型上加以改进,并且提出了摆脱车辆数限制的最远点拼车算法和竞争决策算法。最后结合最远点完全拼车算法通过数值实验对三者进行了比较.结果显示竞争决策算法得到的结果好于其他两者,其次是最远点拼车算法。