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

摘要：

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

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

所属期刊栏目：38

分类号：TP18;TP399(自动化基础理论)

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

在线出版日期：2018-11-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：3036-3041,3052