Abstract: A distributed hybrid variable neighborhood search algorithm is proposed for a specific type of carpooling problem where users maintain a long-term carpooling relationship (LTCPP). Benefited from the distributed computing, the approach can solve large-scale instances rapidly. First of all, a mathematical model with time window and vehicle capacity constraints is constructed and a cost based objective function is built. Then, all users are assigned to carpools accordingly by a hybrid distance priority algorithm in order to get the initial carpooling scheme with satisfying all the constraints. Finally, a variable neighborhood search algorithm is designed with the aid of distributed computing architecture, so that the algorithm can iteratively optimize the initial carpooling scheme in parallel and obtain the final long-term carpooling scheme. Experimental results show that the proposed algorithm has significant advantages in calculating speed and solving large-scale instances.

Key words: variable neighborhood search, carpooling problem, intelligent transportation, heuristics algorithm, optimal matching, vehicle scheduling problem

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

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