Abstract: A Hybrid Variable Neighborhood Search Algorithm (HVNSA) was proposed for solving Long-Term CarPooling Problem (LTCPP), which reduced the number of vehicle trips by matching the users with the same destination. Firstly, a comprehensive and accurate mathematical model of LTCPP was built. Then all users were assigned to the car pools by the composite distance preference algorithm, the time window and vehicle capacity constraint were verified to obtain the initial carpooling scheme. Secondly, the initial carpooling scheme was optimized by using variable neighborhood search algorithm to obtain the optimal long-term carpooling scheme. The experimental results show that HVNSA can obtain high quality of optimal carpooling scheme within 1 second for 100 people and 200 people instances; at the same time, the algorithm can obtain higher quality of optimal carpooling scheme within 2-4 seconds for the larger-scale instances such as 400 people and 1000 people.

Key words: Long-Term CarPooling Problem (LTCPP), neighborhood structure, variable neighborhood search, carpool matching, vehicle scheduling problem

摘要： 针对于长期车辆合乘问题（LTCPP），提出一种复合变邻域搜索算法（HVNSA），将具有相同目的地的用户进行合乘匹配从而减少车辆出行数量。首先，构建一个全面准确的长期车辆合乘问题的数学模型，将所有用户按复合距离优先算法分配到合乘小组中，对时间窗口和车容量约束验证，得到初始合乘方案；然后利用变邻域搜索算法对初始合乘方案进行优化迭代，得到最终的优化合乘方案。实验结果表明，该算法在处理100人和200人的规模问题上可以在1 s内得到高质量的优化合乘方案，对于400人和1000人的较大规模问题，该算法仍然可以在2~4 s内得到较高质量的优化合乘方案。

关键词: 长期车辆合乘问题, 邻域结构, 变邻域搜索, 合乘匹配, 车辆调度问题