随着我国经济的高速增长,私家车已经成为人们普遍的出行工具,但由此带来的交通压力和环境污染也日趋明显。通过车辆合乘方式共享出行则可有效缓解以上问题,因此车辆合乘问题(Carpooling Problem,CPP)逐渐成为研究的热点领域。长期车辆合乘问题(Long-Term Carpooling Problem,LTCPP)属于车辆合乘问题的子问题,它是一种用户目的地相近且用户之间的合乘关系固定的特殊车辆合乘问题。本文应用启发式算法中的变邻域搜索算法(Variable Neighborhood Search Algorithm,VNSA)对长期车辆合乘问题进行研究,通过构造不同变邻域结构对长期车辆合乘问题的解域进行局部搜索,可在较短时间内求解长期车辆合乘问题。首先对长期车辆问题进行分析,构建以出行成本为目标函数并带有时间窗约束和车容量约束的数学模型;然后根据用户地理位置分布,应用复合距离优先算法将用户划分到各个合乘小组,对各个合乘小组进行约束验证得到质量较高的初始解。为了避免陷入局部最优,本文通过构造不同的邻域搜索结构分别对初始解进行局部优化,经过邻域搜索迭代优化后得到满足时间窗口约束和车容量约束的较优解。最后构建基于分布式计算的变邻域搜索机制,提高算法的可靠性和精度,达到节约出行成本的目的。实验结果表明,该算法对于大规模算例能够求解出高质量的较优解,同时该算法在收敛速度和求解时间上均有较高的优势。