长期车辆合乘问题的复合变邻域搜索算法  

Hybrid variable neighborhood search algorithm for long-term carpooling problem

作　　者：郭羽含 伊鹏 GUO Yuhan;YI Peng(School of Software,Liaoning Technical University,Huludao Liaoning 125100,China)

机构地区：[1]辽宁工程技术大学软件学院,辽宁葫芦岛125100

出　　处：《计算机应用》2018年第10期3036-3041,3052,共7页journal of Computer Applications

基　　金：辽宁省教育厅科学技术研究一般项目(LJYL051)~~

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP399[自动化与计算机技术—控制科学与工程]