基于分布式变邻域搜索的长期车辆合乘问题求解研究

发布时间：2020-09-22 16:17

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

路径图,路径,司机,回退

图 2.1 路径示意Figure2.1 Path schematic在路径规划中，司机只能访问用户顶点一次，当司机到达一个用户顶点时，开始窗约束，由于有些较短路径可能无法满足某些用户的时间窗约束，本文在此引入约束，每位用户都各自设置一个最迟忍耐时间wt ，如果司机无法在用户的时间窗户出发地，便检验司机是否能在用户最迟忍耐时间内到达用户出发地。以图 2.2机d 进行路径规划，首先访问用户1c ，2c ，3c 。司机d 无法满足用户3c 的软时间如图 2.2(a)所示。则司机d 进行回退访问，如图 2.2 (b)所示。司机d 从1c 开始访目的地，合乘小组无法满足到达目的地的硬时间窗约束，司机d 进行回退访问，c)所示。司机d 从3c 开始访问，由于不能访问2c ，则司机直接访问目的地，由于合有用户2c 没有被访问，则该条路径规划失败，如图 2.2 (d)所示。如图 2.2 (e)所示d 无法满足用户3c 的软时间窗约束，则司机d 进行回退访问，此时访问序列中仅，故将1c 从第二访问顶点中删除。司机d 对2c 进行访问，若司机d 无法满足用户间窗约束，则司机d 进行回退访问，此时司机访问序列仅剩司机d ，故将2c 从第

序列,路径规划,数学模型,司机

目的地，合乘小组无法满足到达目的地的硬时间窗约束，司机d 进行回退访问，如图2.2 (c)所示。司机d 从3c 开始访问，由于不能访问2c ，则司机直接访问目的地，由于合乘小组内有用户2c 没有被访问，则该条路径规划失败，如图 2.2 (d)所示。如图 2.2 (e)所示，若司机d 无法满足用户3c 的软时间窗约束，则司机d 进行回退访问，此时访问序列中仅剩司机d ，故将1c 从第二访问顶点中删除。司机d 对2c 进行访问

示意图,乘方

合乘方案表述了能够比较直观的体现合乘小组的具体细节信息，本节对 LTCPP 合乘方案中进行表述，即在待求解问题和算法生成的解决方案之间建立一个完整的映射P 的合乘方案表述包括合乘方案中各个合乘小组的用户信息，在合乘小组内用该用户接送组内其他用户的行驶路径和接送时间等信息。因此，合乘方案表。第一层仅显示各个合乘小组的用户编号信息，而第二层则记录组内用户是用户作为司机时接送组内其他用户的行驶路径、总行驶时间、接送其他用户的离和到达目的地时间。上所述，在合乘方案的第一层表述为合乘小组集合 1 2, ,...,nS P P P，其中各含的用户表述为 , ,..., kP i j m。第二层表述合乘小组内每位用户i 作为轮值司机时的详细信息，其中包括用户iR 、出发时间及到达其他用户所在地点的时间iT 、是否与其他用户合乘i 、itance 、行驶时间it 及到达目的地时间iavt 。合乘方案表述示意图如图 3.1 所示。

【参考文献】