客户配送要求变动下的VRPSDP干扰管理优化

赵 亮，梁晓萍，杨华龙，王 征

(大连海事大学交通运输管理学院，辽宁大连116026)

0 引言

在许多实际物流配送问题中，客户同时具有送货和取货两种需求，这样便产生了同时送取货车辆路径问题(Vehicle Routing Problem with Simultaneous Delivery and Pickup VRPSDP)[1]，它是经典VRP的一个变种，其车辆负载并不像其在VRP中那样单调变化[2].随着近年来电子商务等快速发展，客户需求变得触手可及，经常会出现来自客户需求或时间窗变动等配送要求不确定性因素，对原配送计划造成干扰，导致原配送方案无法顺利实施[3].因此，考虑客户配送要求变动的VRPSDP已被业界高度关注.

国内外学者针对配送过程中出现不确定性问题的研究大体可分为3种方法：第1种方法是运用随机动态知识，通过预测未来可能发生的干扰事件，采取相应的措施减小干扰对整个配送系统带来的影响[4]，但是，该方法的局限性主要是预测的准确性无法保证；第2种方法是对车辆路径问题进行重新优化[5]，此方法没有综合考虑原配送方案，很容易造成原计划配送时间的偏离和客户不满意度的增加；于是许多学者提出了第3种方法，即基于干扰管理思想，在原方案基础上进行实时调整以满足要求[6]，但现有研究主要针对的是VRP问题[7].王旭坪等[8]对带回程取货的车辆调度(VRPB)干扰恢复问题进行了研究，但该研究考虑的是送货和取货无交叉的VRPB问题，若客户有同时送货和取货的需求，则将其看成2个客户进行2次服务，这样不仅会出现车辆行驶路线重复的现象，而且还容易增加客户的不满意度.

鉴于此，本文针对客户需求和时间窗等配送要求变动的VRPSDP问题，同时考虑同1位客户的送货和取货需求，并将其看作1次服务，综合分析干扰事件对配送车辆成本和服务时间偏离的影响，构建以广义费用偏离最小化为目标的VRPSDP干扰管理模型，并设计求解算法，以期解决客户配送要求变动下的VRPSDP优化问题.

1 问题描述

物流企业在配送时，通常会以成本最低为目标，通过建立VRPSDP模型，制定一个优化同时送取货的车辆路径方案.显然，当干扰发生时，新的车辆路径方案不包括已经服务完成的客户.因此，本文研究的客户需求和时间窗等配送要求变动的VRPSDP干扰管理模型，是在文献[9]模型的基础上，通过干扰辨识和扰动度量，建立扰动恢复模型，用以制定干扰发生后余下客户的优化配送方案.

干扰辨识是指判断干扰事件是否对原配送方案造成了干扰.主要包括以下4种情况：

(1)当配送车辆所装载的货物量无法满足未服务客户点的需求量时，产生干扰；

(2)当配送车辆剩余的载重量无法满足未服务客户点要求的取货量时，产生干扰；

(3)当客户时间窗提前时，原方案中客户的开始服务时间晚于新时间窗，产生干扰；

(4)当客户时间窗延后时，按初始方案不能对车辆未服务的所有后续客户按要求配送或取货，产生干扰.

客户需求和时间窗变动产生的干扰事件对物流配送车辆路径方案的扰动影响，主要体现在成本和服务时间的偏离上.在成本偏离上：一是，增派车辆而产生的派车成本；二是，由于路径偏离产生的与路径长度有关的运输成本的增减.例如，车辆k原路径为rijk(表示从客户i到客户j的路径)，若车辆从客户i出发前就已知要改变原路线，先去服务客户h再去服务客户j，如图1(a)所示，这时路径的偏离可表示为rijk的减少和rihk、rhjk的增加；若车辆k在从客户i出发后，临时得知需要变更下一个客户点，即车辆已经在需要改变的路线上，此时车辆位置为pk，如图1(b)所示，这时原路线并没有完全减少，而是与新路线有重合部分ripkk，路径的偏离可表示为rpkjk的减少和rpkhk、rhjk的增加.

图1 路径偏离示意图Fig.1 The diagram of route deviation

在客户服务时间偏离上，本文引入时间偏离惩罚系数将时间偏离转换成广义时间费用.即在车辆路径方案调整后，若车辆到达客户点时，该客户的时间窗尚未打开，则车辆需要在原地等待，此时，单位时间偏离系数记为α；若车辆到达客户j的时间在客户满意的截止时间(即按原方案到达客户的时间)和硬时间窗之间，此时车辆的到达时间虽然仍在时间窗内，但却晚于原方案到达客户的时间，这样可能也会对客户的满意度造成一定的影响，为此，引入单位时间惩罚系数记为β(β≥0)，其中，β=0表示对客户满意度未产生影响；若车辆到达客户点时，该客户的时间窗已经关闭，该车辆不能再对其服务，则可将惩罚系数定义为一个无穷大的正数M.

2 模型的建立

2.1 模型假设和符号定义

本文做以下假设：

(1)针对1个车场的物流配送系统，且车辆数有限；

(2)车辆所载货物是同质的，所有车辆的载重能力相同；

(3)客户有硬时间窗约束；

(4)每个客户只能由1辆车进行配送服务.

模型中的变量及参数符号定义如下：

N——扰动发生后未服务的客户数量；

Qmax——配送车辆的最大载重量；

v——配送车辆的行驶速度；

S——配送车辆在客户的服务时间；

T——扰动发生的时刻；

——扰动发生后车辆k正在服务的客户；

pk——扰动发生后车辆k在行驶途中(未在客户点)的位置；

Qk——扰动发生后车辆k的剩余送货量；

qj——扰动发生后未服务客户j处的送货量；

Gk——扰动发生后车辆k已装载的取货量；

gj——扰动发生后未服务客户j处的取货量；

L——扰动发生时在途车辆的数量；

K——扰动发生时车场中的剩余车辆的数量；

C1——从车场派出1辆车的固定成本；

C2——单位路径长度的车辆行驶成本；

dij——客户i到客户j的距离；

dpkj——扰动发生后原车辆k从所在位置到客户j的行驶距离；

dk——车辆k按原方案服务扰动发生后剩余客户的总行驶距离；

Sj——原方案中开始服务客户j的时间；

——新方案中开始服务客户j的时间；

Tj——原方案中车辆到达客户j的时间；

——新方案中车辆到达客户j的时间；

δj——客户j的服务时间偏离惩罚；

fijk——配送车辆k行驶在途中(客户i到客户j)的荷载量；

[ETj,LTj]——扰动发生后未服务客户j的时间窗.

2.2 干扰管理模型

针对物流配送过程中客户需求和时间窗的变动，本文建立的扰动恢复模型为

式(1)是使广义总费用偏离最小；式(2)和式(3)表示每个客户被且只被1辆车服务；式(4)和式(5)分别表示在途车辆和新派车辆送货量约束；式(6)和式(7)分别表示在途车辆和新派车辆取货量约束；式(8)和式(9)表示车辆在每个客户送取货前后途中荷载量约束；式(10)增派救援的车辆数不能超过车场中的剩余车辆数；式(11)表示未服务客户的开始服务时间约束；式(12)表示车辆到达未服务客户的时间约束；式(13)为时间偏离惩罚取值；式(14)为变量的取值约束.

3 算法设计

VRPSDP问题是NP难题[10]，启发式算法等已成为求解VRPSDP问题的主要方法[11].对于客户配送要求变动的干扰，物流配送企业需要快速做出调整决策.而禁忌搜索是局部邻域搜索算法的扩展，是一种全局逐步寻优的启发式算法，搜索速度快，适用于大规模的优化计算[12].因此，本文运用禁忌搜索来设计求解算法，设计的算法流程如图2所示.

根据图2，本文设计如下禁忌搜索算法步骤：

Step 1根据干扰产生的条件，判断需求量或时间窗的变动是否对原方案造成干扰，若不造成干扰，则直接执行原方案；若造成干扰，则执行Step2.

Step 2选出可以尝试救援的在途车辆，即该车辆有足够的货物满足扰动客户的新增需求量，有足够的空间装载扰动客户的新增取货量，并可以在扰动客户的时间窗内到达并服务.若存在可以救援的在途车辆，则执行Step3；否则，执行Step4.

Step 3确定候选解.令干扰发生时的当前车辆配送状态为初始解.将扰动客户从原路线中取出，插入每辆在途车辆与下一个客户之间，并结合2-opt局部搜索将干扰客户与其相邻的客户序列互换，生成有限个候选解.

Step 4设计禁忌表.将取出的扰动客户所插入到每条路线中的位置作为禁忌对象，当扰动点插入到某一位置后，在规定搜索次数为l次的禁忌长度内，扰动点插入到该位置的情况被禁忌.在禁忌搜索中，可能出现候选解全部被禁忌现象，或者存在1个优于“best so far”状态的禁忌候选解，此时特赦准则将某些状态解禁，其对应的对象替换最早进入禁忌表中的对象，更新为最优状态.

Step 5判断从车场派车能否进行救援.若能，则派出新的车辆进行救援，处理结束；若不能，则放弃服务该客户.

4 算例分析

本文采用Solomon标准测试算例，选取R207、R211、RC208中每组数据的前30个和前60个客户作为测试算例.由于原算例中没有各个客户的取货量数据，为方便分析，本文采用正态分布随机赋予一定的取货量.假设在T=50时刻客户配送要求发生变动，随机生成的干扰信息如表1所示.

表1 各组数据客户信息变动情况Table 1 Each data changes in customer’s information

本文首先将参数取值为：C1=140，C2=1，且车辆的行驶速度为单位速度，以配送总成本最低为目标，借鉴文献[7]，运用遗传算法运行10次，选取其中最优的初始配送方案作为该算例的初始路径方案.其次，利用禁忌搜索算法对随机生成的干扰事件进行求解，得到干扰管理方案.将其成本偏离、时间偏离和广义总费用偏离与增派车辆方案及全局重调度方案的各项指标进行对比，结果如表2所示.

表2 R207、R211、RC208测试偏离结果比较Table 2 Compared deviation results of R207,R211 and RC208 dataset

分析测试结果，可得出以下结论：

(1)比较6组测试数据的3种方案结果可以看出，若采纳增派车辆方案，则成本偏离较高；若采纳全局重调度方案，虽然成本偏离较低，但时间偏离和广义总费用偏离远高于干扰管理方案，易增加客户不满意度；采用干扰管理方案，广义总费用偏离较其他两个方案至少降低了12.6%.

以数据R207的前30个客户为例，其初始配送方案如图3所示.干扰发生时刻，车辆1已服务完客户28，正在前往客户23的途中；车辆2正在客户27等待为其服务；车辆3已服务完客户24，正在前往客户3；车辆4已服务完客户18，正在前往客户8的途中；车辆5正在客户17等待为其服务.

图3 初始配送路径Fig.3 The original distribution routes

运用本文方法生成的方案如图4所示：得到的广义总费用偏离为545.3，算法的运行时间为6.3 s，符合快速响应的干扰管理要求.若采用增派车辆方案，即保持原有最优行车不变，则需要新增1辆车，这时的广义总费用偏离为629.4.若采用全局重调度方案，即以成本最小化为目标，重新寻找服务剩余客户的最优车辆路径，则得到的广义总费用偏离为1 941.9.

图4 调整路径方案Fig.4 The adjustment routes solution

(2)将R207、R211和RC208中客户数为30和客户数为60时的各方案进行对比，干扰管理方案与增派车辆方案和全局重调度方案下的广义总费用偏离差别明显.当客户数为60时，运用干扰管理方法节约的广义总费用偏离均大于客户数为30时节约的广义总费用偏离；说明客户越多，本文的方法相比较其他方法越占优势.

(3)从算例的搜索时间来看：客户数为30时，其搜索时间大概在7 s左右；客户数为60时，其搜索时间大概在31 s左右.这是由于需将扰动客户插入到每条路线中进行测试，客户越多，搜索时间就会越长.上述所有算例干扰管理方案的搜索时间都不超过35 s，可以满足干扰恢复的及时性要求.

综上，本文的干扰管理方案在时间偏离和广义总费用偏离方面有着明显的优势，可以减小配送成本并提高客户满意度，从而保证了物流公司和客户的整体利益.

5 结 论

本文研究了有客户需求和时间窗变动的VRPSDP干扰管理问题，以广义总费用偏离最小为目标，建立了客户需求和时间窗变动的干扰管理模型，从而可以全面地刻画各扰动因素的影响，且能够在较短时间内生成满意的物流配送车辆调度调整方案.

需说明的是，本文模型是在硬时间窗约束下构建的，由于天气等外部不确定性因素可能会导致原方案无法实施.因此考虑外部不确定性因素的VRPSDP干扰管理问题值得进一步的研究.

[1]MIN H.The multiple vehicle routing problem with simultaneous delivery and pick-up points[J].Transportation Research Part A：General,1989,23(5)：377-386.

[2]张亚明,李娜.基于精英单亲遗传算法的冷链物流VRP模型优化研究[J].数学的实践与认识,2016,46(4)：87-96.[ZHANG Y M,LI N.Research on elite selection based partheno-genetic algorithm under optimized cold-chain logistics VRP model[J].Mathematics in Practice and Theory,2016,46(4)：87-96.]

[3]丁秋雷.客户时间窗变化的物流配送干扰管理模型—基于行为的视角[J].中国管理科学,2015,23(5)：89-97.[DING Q L.Model of disruption management for the change of time window based on human behavior in logistic disruption[J].Computer&Operations Research,2015,23(5)：89-97.]

[4]SCHYNS M.An ant colony system for responsive dynamic vehicle routing[J].European Journal of Operational Research,2015,245(3)：704-718.

[5]ZHANG T,CHAOVALITWONGSE W A,ZHANG Y J.Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries[J].Computers&Operations Research,2012,39(10)：2277-2290.

[6]王征,胡祥培,王旭坪.行驶时间延迟下配送车辆调度的干扰管理模型与算法[J].系统工程理论与实践,2013,33(2)：378-387.[WANG Z,HU X P,WANG X P.Disruption managementmodeland algorithm for distribution vehicle scheduling problems under accidental travel time delay[J].System Engineering Theory&Practice,2013,33(2)：378-387.]

[7]杨华龙,叶迪,张倩,等.时间窗变动的车辆调度干扰管理模型与算法[J].运筹与管理,2017,26(10)：56-64.[YANG H L,YE D,ZHANG Q,et al.Disruption management model and algorithm for vehicle scheduling with time window changes[J].Operations Research and Management Science,2017,26(10)：56-64.]

[8]王旭坪,阮俊虎,孙自来,等.带回程取货车辆路径问题的干扰回复模型[J].系统工程学报,2013,28(5)：608-616.[WANG X P,RUAN J H,SUN Z L,et al.Disruption recovery modal for vehicle routing problem with backhaul[J].Journal of Systems Engineering,2013,28(5)：608-616.]

[9]王超,穆东.基于模拟退火算法求解VRPSPDTW问题 [J].系统仿真学报,2014,26(11)：2618-2623.[WANG C,MU D.Solving VRPSPDTW problem using simulated annealing algorithm[J].Journal of System Simulation,2014,26(11)：2618-2623.]

[10]LAI M Y,LIU C S,TONG X J.A two-stage heuristic for pickup and delivery vehicle routing problem with time windows[J].Journal of Industrial&Management,2017,6(2)：435-451.

[11]柴获,何瑞春,马昌喜,等.求解带硬时间窗车辆路径问题的改进UMDA算法[J].交通运输系统工程与信息,2016,16(2)：176-182.[CHAI H,HE R C,MA C X,et al.A univariate marginal distribution algorithm hybridized with insertion heuristics for the vehicle routing problem with hard time windows[J].Journal of Transportation Systems Engineering and Information Technology,2016,16(2)：176-182.]

[12]胡祥培,孙丽君,王雅楠.物流配送系统干扰管理模型研究[J].管理科学学报,2011,14(1)：50-59.[HU X P,SUN L J,WANG Y N.A modal for disruption management in urban distribution systems[J].Journal of Management Sciences in China,2011,14(1)：50-59.]