时变需求环境下同时取送货的车辆路径问题优化研究

郭富蓉 巩建忠 崔袁丁

摘  要：针对客户需求随时间实时变化且存在同时取送货的车辆路径优化问题，构建最小化配送总成本的优化模型。考虑动态路径优化问题的处理策略，提出滚动周期型动态调度优化方法，将问题划分为一系列静态车辆路径问题进行求解。通过在蚁群算法中引入遗传算法的交叉、变异操作设计混合蚁群遗传算法对问题进行优化。算例表明：本文所构建的模型及动态调度优化方法能够利用在途配送车辆对时变客户需求做出快速响应，有效降低了配送成本的同时极大地提高了配送中心的服务质量。

关键词：时变需求;同时取送货;滚动周期型动态调度优化方法;车辆路径问题; 混合蚁群遗传算法

中图分类号：U116.2                      文献标识码：

0引言

在现有的关于车辆路径问题（Vehicle Routing Problem，VRP）的研究中，一般假定客户的服务地址、需求量及服务时间窗等信息在路径规划前均为静态且已知的。这种条件下，车辆的行驶路径一经确定，在后续配送过程中是相对固定的，因此这类VRP被称为静态车辆路径问题（Static vehicle routing problem，SVRP）。但随着移动互联网及电子商务的飞速发展，人们对更快捷的物流服务需求不断增加，客户的需求是随时发生变化的，这就使得配送中心需要重新规划调整车辆的配送路径以快速响应客户需求的更新，这类信息随时间动态变化的动态车辆路径问题（Dynamic vehicle routing problem，DVRP）更加符合实际生活^[1-2]。与此同时，客户的日常服务需求不仅包括接收来自车辆配送的货物，还要求车辆将邮寄出的货物带回配送中心^[3-4]。因此，本文结合实际考虑时变需求环境下同时取送货的VRP问题。

目前，国内外学者对于时变需求环境下同时取送货的VRP问题已经进行了大量的研究。A. Fabri等^[5]采用动态事件更新策略对该问题进行调度优化;李兵等^[6]考虑新增客户需求和更改已知客户服务地址两种情形，提出虚拟客户的概念将问题转化成SVRP进行求解;Hu等^[7]基于同时取送货VRP问题，建立了动态路径优化模型;Abdallah^[8]研究了带容量约束的动态需求VRP问题;刘虹^[9]针对动态需求下同时取送货的VRP问题设计了“实时柔性点”的调度策略，构建了多行程VRP优化模型，提出了嵌套随机模拟的变邻域禁忌搜索算法的混合算法进行求解;Chen等^[10]针对动态客户需求及带客户时间窗环境下的VRP问题，运用两阶段优化策略对问题进行求解。

综上，既有研究虽然对时变需求VRP问题已经进行了大量深入的研究，但其研究仅考虑了单一的影响因素，对于贴合实际下的多影响因素的VRP研究比较少，而多影响因素下的VRP问题在实际生活中是最普遍发生的，其求解过程也是十分复杂的。因此，本文针对配送中心在调度服务时域内会接收到客户实时动态变化的取送货需求的情况，以配送中心总成本（包括派车成本、行驶成本和时间惩罚成本）最小为优化目标，研究时变需求环境下同时取送货的VRP问题。

1问题描述及模型建立

1.1问题描述

时变需求环境下同时取送货的VRP问题可描述如下：某配送中心拥有一定数量且状态良好的配送车辆，通过为车辆安排合适的服务顺序及配送路径对所属区域内的客户需求节点进行取送貨服务;车辆容量有限且已知，且车辆从配送中心出发，结束配送任务后返回配送中心^[11];客户以服务时间窗的形式只接受单车单次服务^[12]，且在配送过程中会随时随机的出现新增客户取货需求或更改原有的客户需求（包括已知客户的需求取消、需求地址变更及时间窗发生变化）。优化目标是最大限度地利用在途配送车辆完成时变出现的客户需求任务，在最小化配送中心总成本的前提下，求出尽可能满足客户服务时间窗和快速响应时变客户需求的车辆路径规划方案。

1.2模型参数及变量

模型中，式（1）为配送中心总成本（包括派车成本、行驶成本和时间惩罚成本）最小化的目标函数;式（2-3）保证每个节点都仅被一辆车服务且只能被服务一次;式（4）表示消除子回路，其中S为需求节点的任意子集;式（5-6）保证车辆从配送中心或当前车辆所在位置出发，直到完成任务后，最终返回配送中心;式（7）流平衡约束，即确保车辆访问了一个节点就必须从该节点离开;式（8）指车辆离开配送中心时的初始载重量不得超过其最大载重量;式（9）任意车辆在取送货过程中的载重量不得大于车辆最大载重量;式（10-11）容量约束，车辆完成客户节点j取送件任务后的载重量与完成上一节点任务后的载重量之间的关系;式（12-13）时间窗约束，满足所有客户节点及配送中心的时间窗约束;式（14）时刻的发车数不超过此时配送中心的车辆总数;式（15）为决策变量的取值约束。

2 滚动周期型动态调度方法及求解算法设计

针对时变需求环境下同时取送货VRP问题的特点，本文在分析研究现有文献^[13-15]提出的动态调度策略的基础上，采用滚动周期型动态调度方法对问题进行求解。考虑时变客户需求的服务属性及累计情况，将配送中心的调度服务时域划分为一系列不等的路径重新调度周期，将在该周期内更新接收到的时变客户需求插入到正在进行配送任务的车辆路径中，并利用混合蚁群遗传算法对插入客户需求后的配送路径进行优化，从而将时变需求环境下同时取送货VRP问题转化为若干个SVRP问题进行求解。滚动周期型动态调度方法如图1所示：

2.1路径重新调度时刻

配送中心路径重新调度时刻的划分决定路径重新调度周期的时间长短，也将决定配送路径及调度方案的优劣。因此依据实时更新的客户需求及配送车辆信息，若有以下几种情况时，则判定当前时刻为路径重新调度时刻。

（1）已知客户更改原有的客户需求（包括已知客户的需求取消、需求地址变更及时间窗发生变化）;

（2）新增客户取货需求的累计数量达到最大累计数量Q;

（3）距上一调度的时间达到最大间隔时间T，且该时间段内存在新增客户取货需求;

（4）某一时刻，配送中心派出车辆到达新增客户节点时刻将大于等于该客户最晚接收服务的时间窗时，该时刻即为路径重新调度时刻。

2.2 需求插入算法

通过插入法将时变客户需求尽可能插入到在途配送车辆的服务路径中，从而利用在途配送车辆对其进行服务以降低配送中心总成本，不能插入的则由配送中心派车完成。为此本文根据Solomon^[16]及Zheng^[17]等提出的PFIH插入法设计需求插入算法，具体步骤如下：

2.3路径重新优化算法

本文以蚁群算法为基础，引入遗传算法的交叉、变异操作，设计混合蚁群遗传算法对插入时变客户需求的车辆配送路径进行优化，以求解时变需求环境下同时取送货的VRP优化问题。

（1）蚁群算法

（2）遗传算法

遗传算法（Genetic Algorithm，GA）通过对个体适应度进行交叉、变异等操作搜索最优解，是模拟达尔文的遗传选择和自然淘汰生物进化过程的搜索最优解的方法。GA算法中的交叉、变异操作能够产生新的个体，保持群体的多样性，以防出现未成熟收敛^[20]。

（3）混合蚁群遗传算法的算法流程图如图2所示。

图2混合蚁群遗传算法流程图

3算例分析

3.1实验设置

时变客户需求信息包括新增客户取货需求、已知客户的需求取消、需求地址變更及时间窗发生变化，具体信息见表2。

3.2 模型计算结果及分析

配送中心调度服务时域开始后，依据实时更新的车辆状态及陆续接收到的时变客户需求信息判断路径重新调度时刻，并对路径重新调度周期的时变客户需求进行调度优化，结果如图3及表4所示。

4结语

时变需求环境下同时取送货的VRP问题是时变需求VRP、同时取送货VRP和带时间窗VRP问题的综合，属于经典VRP问题的衍生，更符合实际情况。针对基于动变需求下同时取送货的车辆路径问题，本文构建时变需求下同时取送货VRP问题的调度优化模型，提出一种滚动周期型动态调度优化方法，将配送中心调度服务时域分为若干路径重新调度周期，利用正在进行配送任务的车辆对每个路径重新调度周期内累计的时变客户需求进行快速响应;在求解算法中，考虑到蚁群算法在迭代过程中存在信息素停滞问题，将遗传算法的交叉与变异操作引入蚁群算法，从而扩大搜索解空间，避免陷入局部最优。

本文考虑了车辆行驶速度恒定情形下的路径优化问题，而因交通事故、车辆堵塞、天气变化等因素影响，车辆行驶速度实时发生变化更符合现实情形，因此考虑时变车辆行驶速度下VRP优化问题是下一步的研究方向。

参考文献

[1] 张玉州，张子为.考虑动态客户需求的物资配送问题求解方法[J].西安交通大学学报，2020，54（08）：124-131.

[2] 李桃迎，吕晓宁，李峰，陈燕.考虑动态需求的外卖配送路径优化模型及算法[J].控制与决策，2019，34（02）：406-413.

[3] 龙磊，陈秋双，华彦宁，徐亚，李晨.具有同时集送货需求的车辆路径问题的粗粒度并行遗传算法[J].系统仿真学报，2009，21（07）：1962-1968+1973.

[4] 祁文祥，陆志强，孙小明.带软时间窗的集货与送货多车辆路径问题节约算法[J].交通运输工程学报，2010，10（02）：99-103+109.

[5] A. Fabri，P. Recht.On dynamic pickup and delivery vehicle routing with several time windows and waiting times.Transportation Research Part B： Methodological，2006（4）： 335-350.

[6] 李兵，郑四发，曹剑东，杨扬，耿华，连小珉.求解客户需求动态变化的车辆路径规划方法[J].交通运输工程学报，2007（01）：106-110.

[7] Hu Z H，Sheu J B，Zhao L，et al.A dynamic closed-loop vehicle routing problem with uncertainty and incompatible goods[J].Transportation Research Part C，2015，55（6）： 273-297.

[8] Abdallah A M F M，Essam D L，Sarker R A.On solving periodic re-optimization dynamic vehicle routing problems[J].Applied Soft Computing，2017，55（6）：1-12.

[9] 劉虹，傅晓敏.考虑同时取送随机需求的多行程车辆路径研究[J].西安电子科技大学学报（社会科学版），2019，29（03）：87-95.

[10] Chen S F，Chen R， Wang G G，et al.An adaptive large neighborhood search heuristic for dynamic vehicle routing problems[J].Computers and Electrical Engineering， 2018，67（4）：596-607.

[11] 张文博，苏秦，程光路.基于动态需求的带时间窗的车辆路径问题[J].工业工程与管理，2016，21（06）：68-74.

[12] 李国明，李军华.带软时间窗的随机需求车辆路径问题的算法研究[J/OL].计算机集成制造系统：1-20[2021-03-23].http：//kns.cnki.net/kcms/detail/11.5946.TP.20191129.1529.028.html.

[13] 周鲜成，王莉，周开军，黄兴斌.动态车辆路径问题的研究进展及发展趋势[J].控制与决策，2019，34（03）：449-458.

[14] 谷振宇，刘国荣，白晓辉等.一种快递配送过程中处理新增取件需求的动态调度方法[P].

[15] 刘国荣. 动态需求下快递同时取送路径优化问题研究[D].重庆大学，2018.

[18] Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research. 1987，35（2）： 254-265.

[17] Zheng J， Liu G， Gu Z， et al. Delivery vehicle routing problem with simultaneous delivery and pickup in E-commerce environment[C]. 2017.

[18] 李卓，李文霞，巨玉祥，陈晓明，何晓平.混合蚁群算法求解带软时间窗的车辆路径问题[J].武汉理工大学学报（交通科学与工程版），2019，43（04）：761-766.

[19] 汤雅连，蔡延光，杨期江.求解带软时间窗多车场多车型车辆路径问题的一种改进蚁群算法（英文）[J].Journal of Southeast University（English Edition），2015，31（01）：94-99.

[20] 范厚明，徐振林，李阳，刘文琪，耿静.混合遗传算法求解多中心联合配送路径问题[J].上海交通大学学报，2019，53（08）：1000-1009.

[21] 万旭，林健良，杨晓伟.改进的最大一最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统，2005，11（4）：572-576.