车辆合乘问题的分布式复合变邻域搜索算法

来源：计算机科学与探索杂志2019年第2期北京时间：

作者：郭羽含，伊鹏

单位：辽宁工程技术大学 软件学院，辽宁 葫芦岛 125100

摘要：针对长期车辆合乘问题（long-term carpooling problem，LTCPP），提出一种基于分布式的复合变邻域搜索算法，利用分布式计算的优势可快速求解出大规模用户的合乘匹配方案。首先构建带有时间窗约束和车容量约束的数学模型，建立成本计算的目标函数；然后按复合距离优先算法将所有用户分配到各合乘小组中，最终得到满足约束条件的初始合乘方案。通过对变邻域搜索算法进行分布式处理，使算法可以对初始合乘方案进行并行迭代优化计算，得到最终的合乘方案。实验结果表明，该算法在速度和大规模问题求解质量上具有明显的优势。

关键词：变邻域搜索,车辆合乘问题,智能交通,启发式算法,优化匹配,车辆调度问题