ICP策略下带软时间窗的动态车辆路径优化问题研究

鄢栋　陈家琪

摘要：

针对动态车辆路径中出现新的客户请求时，输入信息（可能包括客户请求出现时的车辆位置、客户时间窗、服务时間、需求量等）也随着时间推移而动态改变，在服务客户时由于动态客户需要不停插入，导致不停地进行优化计算，致使车辆路径更新频繁的问题，提出了紧急动态客户和数据包的概念（简称ICP）。通过该策略并使用遗传方法（Genetic Algorithm，GA）与局部搜索方法（Local Search，LS）的混合算法（简称GALS），可提高车辆路径更新质量，降低车辆运输成本并控制配送中心管理成本，从而提高服务质量。通过实验证明了该策略的有效性。

关键词：车辆路径优化；DVRPSTW；遗传算法；LS；数据包

DOIDOI：10.11907/rjdk.172443

中图分类号：TP319

文献标识码：A文章编号文章编号：16727800（2018）003017204

英文摘要Abstract：For the new customer requests that appear in the dynamic vehicle path， the input information （which may include the location of the vehicle when the customer request appears， the customer's time window， service time， demand， etc.） changes dynamically over time. In the service of customers， due to frequently inserting of dynamic customers demand and the vehicle path updating ，which leads to the nonestop optimal calculation.In this paper， the concept of emergency dynamic customer and data packet （ICP） is proposed. Through using this strategy and GALS method ， the transportation cost of vehicle is reduced and the management cost of distribution center is controlled， then the quality of service is optimized.The validity of the ICP method is proved by experiments.

英文关键词Key Words：vehicle routing optimization； DVRPSTW； genetic algorithm； LS；data package

0引言

动态车辆路径问题是指对一系列发货点（或收货点），组织适当的行车路径，使车辆有序通过，在满足一定约束条件（如货物需求量、客户需求、交发货时间、车辆容量限制、行驶里程限制、时间限制等）的情况下，达到一定目标（如路程最短、费用最少、消耗能源最少等）[1]。由于在现代社会中时间约束的重要性，出现了VRPTW（Vehicle Routing Problem with Time Window，有时间窗车辆路径问题）。在具有硬时间窗口（VRPHTW）的车辆路径和调度问题中，根本不允许在时间约束窗口之外进行交付，这对于现实生活中的物流运输是不太合理的。因此，带有软时间窗（VRPSTW）的车辆路径和调度问题引起了人们关注，即其在约束时间窗口外仍然可以通过增加一些惩罚成本进行交付。但由于静态VRPSTW的有些约束条件是规定好的，并不能反映现实世界的真实情况。

因此，更具有实际研究意义的DVRPSTW问题受到越来越多研究者的青睐。黄务兰、张涛[2]提出了基于事件触发（包括不需要调整路线车辆位置变化、完成节点服务，以及需要调整路线的，比如新的请求到达、因阻塞等原因路网发生了变化）的分解策略，根据系统的当前状态，构造一个系统的延迟快照，每个快照被视为一个VRPTW，从而把DVRPTW分解成一系列的VRPTW问题。然后在LNS算法基础上，提出一个双缓冲区来改进LNS算法，求解静态VRPTW问题。

洪联系[3]用混合节约算法与禁忌搜索算法优化动态车辆路径问题，目标为最小化车辆旅行距离与车辆数量。根据动态需求的特点，按照一定规则和策略，将整个配送过程分为若干个相等或不等的时间段进行处理。在每个时间段的结束时刻，实行动态需求的插入，并根据车辆当前位置和更新后的信息制定出新的路线方案。通过比较相同数据下单个节约算法、单个禁忌搜索算法、混合算法输出的总目标值，得出结论。

刘霞等[4]研究的是带软时间窗的动态车辆路径问题，首先将计划周期划分为固定时间间隔的时间片段并设置一个中断时间作为算法终止条件之一，从而将问题静态化；然后利用插入法求解DVRPTW的初始线路（初始解），采用线路间局部搜索和线路内局部搜索对初始解进行优化。对于违反时间窗的车辆，增加一个延迟时间惩罚参数；最终通过Solomon的算例，进行实验并分析结果，求得最优路线。

对于DVRPSTW问题的求解，大多是将时间窗进行划分，把DVRPSTW问题转换为一系列的静态子问题，从而求解VRPSTW问题。对于动态需求，大多数是在当前时间段（一般是结尾处）插入一个动态客户，并计算插入的必要条件，插入后进行路径实时优化，最后得出最优路径，接着再插入下一个动态客户。这样由于不断地进行插入和优化计算，从而导致不停地更新车辆路径，进而增加了车辆运输成本与配送中心管理成本。因此，为了减少动态过程中的插入和优化计算负载，提高车辆路径更新质量，减少车辆运输成本（车辆数量）并控制配送中心管理成本（车辆行驶总距离），本文基于插入（紧急需求插入）和数据包（用来存放非紧急客户的动态客户暂存区）的概念，提出一种紧急需求插入和数据包的求解新方法。

1DVRPSTW问题描述与数学建模

带软时间窗的动态车辆路径问题（DVRPSTW）可以描述如下：G=（I，E）是有向图，其中I = （1，2，…，N）是顶点集，表示客户。E={（i，j）：i≠j∧i，j∈I}是弧集。顶点0（Distribute Center）表示有M个容量为Q的相同车辆的配送中心，且是路线的起点和终点。顶点集I = （1，2，…，N）指定一组N个客户的位置。I中的每个顶点具有相关联的需求qi≥0，服务时间si≥0，以及服务时间窗口[ei，li]。每个弧（i，j）具有相关联的恒定距离dij≥0和行驶时间tij（tij=dijv），v是车辆速度。车辆到达客户i的时间表示为Ri（Reach），车辆m访问客户i时的剩余容量表示为gim，且gim≤Q。T是车辆工作时长。在对车辆进行路径规划时，将工作日T划分为Nt个不同长度的时间片段。那么当在某一时刻Tl：

（1）设G=（ITl，ETl）。

（2）车辆m最终确定服务的客户集记为Csd，即包括已知的静态客户和即将服务的动态客户，如图1所示。

（3）用NTl表示工作日之前和工作日内接收的动态客户。

（4）则ITl=NTl∪{o，Csd}，NTl∩{o，Csd}=，其中o是Tl时刻的配送起点，不同于配送中心0。

（5）定義决策变量xijm={0，1}，表示如果存在车辆m从客户i到客户j的路线时，xijm=1，其他情况xijm=0。

本文目标是最小化车辆数量（在路径图中体现为路径数）和最小化配送中心的运输成本（在路径图中体现为路径总距离）。采用线性加权权重法[5]衡量目标子函数，则本文的目标函数可以定义为：

minf=α∑i∈NTl∑m∈Mxi0m+β∑i∈{o，Csd}∑j∈{0}∪{o，Csd}∑m∈Mdijxijm（1）

满足如下约束条件：

（1）车辆从配送中心出发，服务客户后必须返回配送中心。用公式表示为：

∑i∈{0}∪{o，Csd}∑j∈NTlxijm=1，m∈M（2）

∑i∈NTlxi0m=1，m∈M（3）

（2）每个客户有且只能由一辆车为其服务，用公式表示为：

∑j∈NTl∑m∈Mxijm=1，i∈ITl∧i≠j（4）

∑i∈ITlxikm=∑j∈NTlxkjm，k∈NTl，m∈M（5）

（3）每辆车运输量不能超过车辆本身的装载能力，即：

∑i∈NTl∑j∈{0}∪NTl∧j≠iqixijm≤gim，m∈M（6）

（4）时间参数计算。

等待时间：

Wi=ei-Ri，若ei≥Ri0，否则 ，i∈NTl（7）

客户j的到达时间：

Rj=∑i∈ITl∑m∈M[xijm*（Ri+Wi+Si+tij）]，

j∈{0}∪NTl∧j≠i（8）

车辆必须在客户i的时间窗口关闭前到达，否则增加一个惩罚参数Pi，并重新分配路径，即：

Ri≤li，i∈ITl（9）

Pi=Ri-li，Ri>li（10）

2紧急需求插入与数据包求解方法描述

在时刻Tl，假设某辆车的配送路径为（v0，v1，…，vk，…，vK），vk∈ITl（该路径作为初始路径，用遗传算法求解），如果一个顾客v*插入到该路径中，而路径仍是有效的，且满足需求公式：

qv*+∑Kv=1qvk≤gvkm，vk∈ITl（11）

并且满足：

（1）当v*插在上述配送路径的最后一个，则：

Wvk+Rvk+Svk+tvk，v*≤Lv*（12）

（2）当v*插在上述配送路径中间，假设在vk和vk+1之间（k∈[0，k-1]），则：

Wvk+Rvk+Svk+tvk，v*≤Lv*（13）

max{Wvk+Rvk+Svk+tvk，v*，Ev*}+Sv*+tv*，vk+1≤Rvk+1+Wvk+1+Dvk+1（14）

其中Dvk+1表示顾客vk+1的最大延迟时间，为：

Dvk=Lvk-（Rvk+Wvk），k=Kmin{Lvk-（Rvk+Wvk），Dvk+1+Wvk+1}，k∈[1，k-1]（15）

如果动态客户发送动态需求的时刻记为t0，t1，…（t0

“紧急动态客户”采用实时插入的方法，“非紧急动态客户”采用数据包策略，即把“非紧急顾客”都放到数据包里，待达到优化条件时，再一起发送给优化模块。整体方法流程如图2所示。

3DVRPSTW算法描述

带软时间窗的动态车辆路径问题（DVRPSTW）算法采用了结合遗传算法和局部搜索算法的混合算法。其思想是第一步采用遗传算法产生路径初始解，然后使用该解作为局部搜索搜索算法的初始值，然后用重定位法和2-opt法进行优化运算。在该混合算法中，时间窗被划分为不同长度的时间片段，在每个时间片段的结尾处收集静态和动态客户集，如果是紧急动态客户，则立即插入线路中并优化，如果是非紧急动态客户，则先加入到数据包中，待达到优化条件再进行优化，直到优化模块更新信息，输出最优路径。在每个时间片中，该问题类似于静态VRPTW。因此，通过已经描述的混合算法，对于具有不同起始位置的车辆，该问题在每个时间片结束时作为部分静态问题来解决。算法步骤如下：①首先获取车辆m的实时数据，设其初始数据在配送中心，开始时间为0；②确定车辆m最终服务的客户集Csd；③判断当前时间是否超过了时间片与惩罚参数Pi（即最大延迟时间）之和，如果超过，则结束，转步骤⑨；否则，还有动态客户的需求没有到达或未到时间片的结尾，执行步骤④；④在每个时间片的结尾处构成了静态子问题。在时间片开始之前，静态子问题中的客户集是由当前时间片还未提交的客户以及上一个时间片内出现的即时新客户组成（这里不考虑上一个工作日）；⑤采用遗传算法的精英策略产生线路初始值；⑥采用重定位法和2-opt法对步骤⑤中产生的初始值进行优化。如果时间片结束，终止优化计算，到下一步骤⑦，否则，循环执行⑥；⑦提交已优化的线路给下一个时间片内的车辆，并移除已优化线路中的客户节点；⑧更新信息；⑨配送任务完成，车辆返回配送中心，并输出最优路径解。

其中⑥、⑦、⑧构成优化模块。算法流程如图3所示。

4实验结果分析

本文测试采用Lackner的benchmark数据c101、r101、rc101、c201、r201、rc201 这6类数据集，取α=1 000，β=1，T=1/20[5]，优化计算5次，选择5次运行中的最优解进行分析，成本距离与车辆数分别如图4、图5所示。

从图4的成本距离数据看，本文采用的基于ICP策略得出的结果比其它插入后进行实时优化的策略更优，而且整体数据较为稳定。本文平均使用的车辆数大约为10辆，平均成本距离为1 057.68（车速为1）。设想在大规模车辆调度的实际问题中，优化效果会更明显。

另外可以看到，201数据集的数据中，车辆数明显少于101数据集的数据，这是由于其数据集的特点所造成的。201的数据集时间窗宽，但客户坐标是随机的；101数据集时间窗窄，客户坐标也是随机的。这说明车辆使用数量与时间窗大小有关，时间窗越宽，使用的车辆数越少；反之，车辆使用越多。

同時，实时插入策略虽然在平均车辆数的趋势上减少，在201数据集上使用的车辆数也大大减少，但是距离成本却很高。这说明实时插入虽然时效性很好，企业花费的距离成本却大幅上升。总体来看，本文的ICP策略减少了企业的服务成本，提高了总体服务质量。所以，可以根据具体的企业需求选择策略，如果企业要求的是在可控成本内的时效性以及尽量减少车辆使用，则选择实施插入策略；如果企业要求总体减少服务成本输出，则最好选择ICP策略，这样既保证了时效性，又能减少企业服务成本。

5结语

本文研究带软时间窗的动态车辆路径问题，在动态车辆路径问题的基础上添加了时间窗，可更加贴近现实生活中车辆早到或延迟的情况，采用时间片的方法收集动态客户需求，将问题静态化，同时针对紧急动态客户采用即时插入方法，非紧急动态客户采用数据包策略，这样既保证了运输系统的实时性，又减少了优化模块的优化计算，从而减少车辆使用数量和企业管理成本。在未来研究中，可以考虑多个中心仓库的DVRPSTW问题，或者考虑在车辆损坏、天气变化以及多个工作日中的DVRPSTW问题，以求解更复杂的现实情况。另外，对于共享资源以及绿色路径的优化也是未来的一个研究方向。

参考文献参考文献：

[1]潘莹，陈家琪.基于MultiAgent仿真的动态车辆路径算法研究[J].信息技术，2015（5）：121124.

[2]黄务兰，张涛.基于改进遗传算法的带时间窗车辆路径问题研究[J].微型机与应用，2016，35（13）：2124.

[3]洪联系.带时间窗口动态车辆路径规划模型及其求解算法[J].计算机工程与应用，2012，48（4）：244248.

[4]刘霞，齐欢.带时间窗的动态车辆路径问题的局部搜索算法[J].交通运输工程学报，2008，8（5）：114120.

[5]王君，李波，卢志刚.带时间窗动态车辆路径问题的优化调度策略[J].计算机工程，2012，38（13）：137141.

[6]XIAO J， LU B. Vehicle routing problem with soft time Windows[M]. Advances in Computer Science and Information Engineering. Springer Berlin Heidelberg，2012：317322.

[7]MAK K L， GUO Z G. A genetic algorithm for vehicle routing problems with stochastic demand and soft time windows[C].Systems and Information Engineering Design Symposium， Proceedings of the.IEEE Xplore，2004：183190.

[8]WEI L， ZHUO F. A variable neighborhood tabu search algorithm for the heterogeneous fleet vehicle routing problem with time windows[C].International Conference on Logistics Engineering and Intelligent Transportation Systems， 2010：14.

[9]ABBATECOLA L， FANTI M P， UKOVICH W. A review of new approaches for dynamic vehicle routing problem[C]. IEEE International Conference on Automation Science and Engineering，2016：361366.

[10]FAN XC， LI NL， ZHANG BY， et al. Research on vehicle routing problem with soft time windows based on tabu search algorithm[C].International Conference on Industrial Engineering and Engineering Management，2011：420423.

责任编辑（责任编辑：黄健）