考虑路径一致性和工作量平衡的车辆路径优化问题

发布时间：2020-07-30 05:29

【摘要】：在物流运输行业中,高质量的运输服务是提高顾客满意度的关键因素,因此本文提出运输路径一致性的策略,为物流运输企业实现高质量服务提供新的路径规划和车辆部署方案。路径一致性策略旨在允许周期内每天可访问无需求顾客点的前提下,限制每位司机在周期内可行驶不同路径的最大数量,从而增加司机对行驶路径的熟悉程度,提高运输服务的质量和可靠性。基于路径一致性策略所得到的实际路径行驶方案是指周期内每天只访问有需求顾客点的路径行驶方案,虽然它一定程度上破坏了司机对行驶路径的熟悉度,但影响到了顾客所享受到的服务司机一致性以及到达时间一致性效果。因此本文着重研究考虑路径一致性的周期性车辆路径问题,目标是最小化司机在周期内的总工作时间,总工作时间包括行驶时间和服务时间。为了求解这个问题,本文建立了一个混合整数线性规划模型,并用现有的混合整数线性规划求解器CPLEX进行求解。为求解大规模算例,本文开发了一个带禁忌搜索改进的大型邻域搜索算法。算法中包含了节约里程算法获得初始解,四种算子进行邻域搜索和邻域变换,以及禁忌搜索算法进行改进等步骤。最后,本文采用了一致性车辆路径优化问题中的基准数据,进行了小,中,大规模下的数值试验,验证所提出模型和算法的有效性及求解效果;并分析基于路径一致性策略所派生出来的实际行驶路径方案所带来的服务司机一致性和到达时间一致性所的效果。此外,本文以考虑工作量平衡的周期性车辆路径优化问题作为扩展研究,将周期内司机间的最大工作量差异值控制在小范围内,从而保证每位司机在周期内的工作量处于同一个水平。为求解这个问题,本文建立了数学模型,并应用了局部分支算法。数值实验部分比较了CPLEX求解结果与局部分支算法的求解结果;并分析了工作量平衡对总工作时间的影响。
【学位授予单位】：上海大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：U116.2;F540
【图文】：

算法,车场,行驶时间,初始解

∈ 中选择行驶某一条路径，并且也能保证在周期内的任意天里行驶同一条路径，从而实现了路径一致性。为了更清晰的阐述 LNS-TS 算法的第一阶段，本文给出了一个周期天数 T=5 的例子，如图 4.1 所示。图 4.1 LNS-TS 算法第一阶段的基本框架图 4.1 中提到的 LNS-TS 算法第一阶段中初始化过程，变异过程和禁忌搜索改进过程在接下来的章节中会仔细介绍。4.1.1 解的初始化在初始化过程中，本文用到了 C-W 最大化节约里程算法。这个算法的基本思想是：通过节约最多的路径行驶时间将两个环整合成一个环（最开始的时候，一个环中包含车场和一个顾客，行驶路径是从车场出发，访问完这个顾客后，回到车场。更新后的环，也是以车场为起点和终点）。重复这个操作，直到这些环在容量和行驶时间的约束下再也无法整合出新的环时停止。C-W 节约里程算法相对于随机生成的方法来说，所生成初始解的质量较高，从而能够加快后续邻域搜索的进程。在使用 C-W 最大化节约里程算法生成初始解的时候，需要注意的是，对于子集合内只包含一天的情况来说

局部分支,邻域

的解空间进行分支，分支过程如图6.1所示。它的应用范围主要是用于求解小，中规模的算例。在图 6.1 中，本文先定义了几个输入参数，其中，“ ”是控制邻域大小的参数，其取值需要在合适的范围以保证既能够加快求解时间，又能够在这邻域中找到新的更好的解。“N”是允许的迭代次数，“ ”是允许的连续未提高解质量的次数，当达到其中任意一个数值时，整个算法停止。“OBJ”是目标值，也代表目前找到的最好的解，在整个过程中，“ ”指的是在第 n 次迭代时找到的最好的解

【参考文献】