基于配送地点变化的物流干扰管理研究

卜心怡，刘超，钱军

（杭州电子科技大学管理学院，浙江杭州310018）

基于配送地点变化的物流干扰管理研究

卜心怡，刘超，钱军

（杭州电子科技大学管理学院，浙江杭州310018）

在物流配送过程中，通常会出现各种干扰事件影响配送车辆的正常运行，这时原配送计划往往变得不可使用，文章针对客户配送点变化这一干扰事件，运用干扰管理思想，从三个主体对干扰事件进行分析和度量，并以客户不满意度最小，成本最低，路径偏离最少为目标，建立扰动恢复模型。设计了改进的遗传算法对模型进行求解，并结合算例进行仿真实验，与重调度法进行对比分析，验证了干扰恢复模型的有效性。

干扰管理；车辆路径问题；配送点变化；遗传算法

一、引言

随着电子商务及物流行业的迅速发展，物流运输速度已经成为了影响物流总成本和服务质量的最重要环节。然而在实际的物流运输过程中，往往会出现各种干扰事件，如出现新的客户需求，客户时间窗或者配送地点发生变化，车辆出现故障或者天气原因等原因影响了正常配送。因此当在物流配送过程中，出现这些干扰事件时，如何有效地形成新的配送方案，使得配送成本及线路扰动最低成为了车辆路径问题的热点及难点问题。

目前关于车辆路径问题的研究，国内外已经进行了比较全面的研究，Roberto Baldacci等[1]采用精确算法求解了两级带载重约束的车辆路径问题。S.A.MirHassani等人[2]通过建立绿色车辆路径问题模型，用引力算法作为求解搜索方式。得出最短的路径并不一定是绿色车辆路径模型的最优解。Ando N等人[3]建立以运输成本最低，运输时间和碳化物和氮化物排量小作为目标的车辆路径模型，采用改进遗传算法进行求解。Andreas Bortfeldt[4]等人通过变邻域搜索算法求解了具有三维装载约束、有时间窗约束、带回程取货车辆路径问题。

张旭凤[5]等人通过动态规划方法求解了单配送中心、用户信息已知、取货送货混合的车辆路径问题。崔珊珊[6]等在分析井喷需求下，针对时间相应型顾客选取配送时间最短作为目标函数，对时间延迟型客户选取成本最低作为目标函数，来设计不同求解模型，实现客户满意度与运输成本的平衡。这些研究往往问题及限定条件是事先已知，而没有考虑配送过程中可能会发生的干扰事件对配送计划的影响。

一些学者基于配送过程中经常出现干扰事件这样问题出发，提出基于干扰管理思想的车辆扰动恢复模型来解决此类问题。最初Hane等[7]将干扰管理模型用于解决航空机组调度问题。Yu[8]等人率先提出了一个关于干扰管理的数学模型。王征[9]等针对顾客时间窗变化这一干扰因素，以系统整体扰动最小化建立数学模型，采用变邻域搜索算法求解顾客时间窗变化的多车场物流配送干扰管理问题。杨文超[10]等将行驶延迟和顾客更改配送时间这两类时间干扰，采用了统一的方法进行处理，使得扰动恢复模型适用范围变得更加广泛。王旭坪[11]等研究了在配送过程中车辆故障这一干扰问题，采用增派、临近及取消策略进行救援，并根据成本最小及系统扰动最小目标设计了扰动恢复方案。蒋丽等[12]同样针对某一配送车辆发生故障这一问题，研究在配送中心无备车的情况下，通过其他在途车辆救援策略的干扰管理问题。胡祥培[13]基于客户需求量变化引发的物流配送干扰问题，从客户不满意度、配送成本以及路径偏离程度三个方面度量物流配送系统中的扰动，建立模型并采用融合多种邻域函数的禁忌搜索算法实现模型的求解。蒋丽等[14]研究了针对带回程取货的运输过程

中，因客户需求变化引发的干扰管理问题。

以上研究主要针对时间因素扰动、车辆动力扰动和客户需求扰动三类干扰事件进行分析的，同时有考虑了集货与送货相结合情况，但是基于客户配送地点变化干扰事件进行研究的比较少。客户配送点发生变化，可以看做是已有的某个配送点取消配送，同时又出现一个新的需求点，因此出现新客户需要点和某客户需求点取消可以和某客户配送点发生变化进行结合研究。

为此，本文针对车辆在配送过程中出现客户更改配送地点这一问题，基于干扰管理的思想，首先将新客户进行分类，根据不同的客户类型设置了不同的扰动恢复模型；并采用了遗传算法进行求解，最后通过算例对算法在其问题上的处理能力及效率进行验证。

二、问题描述及模型建立

本文将问题设定为有一个配送中心，多个客户需求点，车辆对各个需求点进行配送，最终返回配送中心。车辆在运行过程中，车辆载重不超过其最大载重量，满足顾客时间窗限制，配送中心根据限制条件生成车辆运输成本最小的初始方案。

然而在现实的配送过程中，如果某客户配送地点发生变化，会对初始方案产生了扰动，使的原计划变得不可行，因此需要在初始方案的基础上，快速生成新的费用最低及原计划扰动最小的调整方案。

（一）初始配送方案数学模型

1.问题假设

通过对上述问题的设定，可以问题进行以下描述：

（1）车辆从配送中心出发，按照初始行驶计划，分别对顾客进行配送，最后回到配送中心。配送中心有多辆车辆。

（2）每个客户只允许访问一次，且只能由一辆车辆进行服务。

（3）车辆有载重限制，不需要考虑体积限制，车辆载重不超过其最大载重量。

（4）每个客户都有其服务的时间窗，车辆需尽量满足顾客时间窗要求。

（5）客户配送点发生变化，需求量不发生变化。

（6）货物是同质商品，配送过程不会对商品质量产生影响。

2.参数及变量说明

n：客户数量；

Dij：顾客节点i到j的距离；

ij=0，1，2，3，…，n，其中0代表配送中心；

Q：表示车辆的装载容量；

qi：顾客i的货物重量；

K：车辆数目；

Cij：从顾客节点i到顾客节点j的成本；

[Ei，Li]：表示客户i的服务时间窗，Ei-δ是客户要的取货开始点，Li-δ是客户要的取货结束点；

Tik:车辆k到达顾客i的时间；

δ：超过顾客时间窗的最大容忍时间；

3.初始方案模型

根据上述描述，可以建立初始配送方案模型：

在这里初始模型没有加入违反客户时间窗惩罚，只考虑车辆的运输成本，模型中式（1）为目标函数，表示运输成本最低；式（2）为车辆k装载的货物总量不大于车辆的装载能力；式（3）为每车辆都从配送中心出发；式（4）车辆服务顾客后返回配送中心；式（5）每个顾客只由一辆车辆进行服务；式（6）和式（7）表示变量之间关系；式（8）表示满足顾客时间窗最大容忍要求，超过则客户会拒绝接受。

（二）客户配送点变化的物流干扰管理模型

1.问题描述

当某个客户配送点发生变化后，配送中心没有其他配送车辆，剩余未完成的任务依靠原配送车辆进行配送完成。同时假设发生干扰事件时，以各个配送车辆的位置为起始位置，原配送中心为终点。由于本文是以客户点发生变化为干扰事件，因此当发生干扰时，未配送客户点集合将会随之发生变化，这时需要两个客户点集合加以区分。

2.参数设置与说明

m：发生干扰时，未配送客户数量，未配送客户点集合V（v1，…vm）。

C0：发生干扰时，初始配送计划中，客户点集合。

C：发生干扰时，调整计划中，客户点集合。C={c0，c1，…，cm，cm+1，…，cm+k}，其中c0是初始配送点，c1，…cm是未配送客户点，cm+1…cm+k是发送干扰时的虚拟配送点出发点。

3.扰动度量

在配送过程中，当干扰事件发生后，基于干扰管理思想，需要在满足新约束条件下重新设计一个系统扰动最小的配送方案。如何度量客户配送点变化对系统造成的扰动

大小事建立干扰管理模型的关键。在配送过程中，主要存在三个主体，即客户、物流运营商、配送员，因此当某个客户配送地点发生变化后，主要影响的是客户、物流运营商、配送员这三个主体。

（1）客户：客户在商品质量一定的，最先考虑的是能否按时收货。当某个客户的配送地点发生变化后，需要调整部分剩余客湖的配送顺序，车辆的到达时间就势必发生变化，使得某些客户无法按时收到货物，因此这部分受影响的客户的满意度就会受到影响。因此客户干扰度量就首先要分析配送车辆偏离客户时间窗的程度，目前物流配送方面的研究，主要有两类时间窗：一种是硬时间窗，配送车辆必须按照客户规定时间配送，否则客户将放弃本次服务；另一种是软时间窗，配送车辆如果无法按照客户规定时间配送，则给予配送车辆一定惩罚。

图1 客户时间窗惩罚图

在现实配送过程中，通常不会只是一种时间窗要求，往往需要满足两种时间窗要求，因此本文基于顾客混合时间窗要求进行研究。图中当Ei≤Tik≤Li时，表示车辆k在客户规定时间内到达，惩罚为0。当Ei－δ＜Tik＜Ei或者Li≤Tik≤Li+δ时表示违反了客户时间要求，进而进行一定惩罚，同时值得注意的是，配送车辆如果提前到达客户配送地点，可以选择提前交货，或者选择等待客户时间窗开启，仅需要承担等待成本即可，因此往往受到的惩罚会比较少。

因此每个客户的不满意度可以表示为：

其中Max是一个较大的正数；u1和a1代表早到的惩罚系数，u2和a2代表迟到的惩罚系数；当i客户由k车辆服务时yik=1，当i客户不是由k车辆服务时yik=1。

整个物流系统中客户不满意度的度量方法如下：

其中n为客户数量，F1表示平均客户不满意度。

（2）物流运营商。物流运营商首先关心的是物流配送成本，在配送过程中，当某一客户配送点发生变化时，剩余未配送地点集合将发生变化，因此配送路线随之跟随变化，这将直接影响配送成本。因此客户配送地点变化对物流运营商运输成本的影响程度可以表示为：

（3）配送员。配送员是物流配送任务的执行者，在配送过程中会对原配送路线相对熟悉，当发生扰动时间后，配送路线也将相应发生变化，势必会影响配送员的工作情绪，同时也影响配送效率。

因此在设计配送路线时不仅要考虑配送成本，同时也要考虑路线的变化程度。设a为属于调整后路线，而不在原路线的路段个数。b为属于原路线，而不属于调整后路线的路段个数。β+为原路线中增加一条路段的成本，β－的为原路径中减少一条路段的成本。

因此客户配送地点变化对物流配送员的影响程度可以表示为：

4.干扰管理模型

根据上节中干扰度量函数为依据，采用字典序的多目标规划的方法，构建物流配送干扰管理模型：

干扰管理模型需要满足初始配送模型的限制，其中式（12）为目标函数，表示调整方案与初始方案的偏离最小，即系统的扰动程度最小。W1，W2，W3为目标函数的权重系数。式（14）确保每辆车辆载重量不超过最大限度。式（15）每辆车辆从虚拟出发点出发。式（16）每辆车辆最终回到配送中心点。式（17）表示满足客户时间窗要求。

三、干扰管理模型的求解方法研究

本文所研究的是基于带时间窗的车辆路径问题（VRPTW），该问题已被证明为NP-hard。本文所构建的干扰模型必须考虑优化多个目标，求解过程复杂，加之实际物流调整计划的实时性要求，精确算法难以胜任，因此选择采用启发式算法来求解物流干扰管理问题。遗传算法具有很好的鲁棒性、泛化能力、信息处理潜在的并行性、可扩展性等特点，使得广泛应用于许多领域。由于遗传算法的局部搜索能力差，导致单纯的遗传算法比较费时，并且在求解一些实际问题时，容易产生早熟收敛的问题，结合以上分析本文采用改进的遗传算法来求解配送地点发生变化的物流干扰管理问题。

1.染色体的编码方式。遗传算法有多种编码方式，对于车辆路径问题主要有自然编码方式和基于顾客的编码

方式。本文采用自然编码方式，对客户集合C={c0，c1，…，cm，cm+1，…，cm+k}中的客户进行自然编号，c0配送中心对应自然数0，cm+1到cm+k对应自然数1到m+k。

2.初始化种群。在完成染色体编码后，首先要产生一个初始种群作为初始解，生成的初始解应该具有多样性，防止出现局部最优。由于干扰管理目标函数中有一个目标是路径偏离最低，因此将初始化种群中加入一定比例的初始最优路径，使得求解结果更倾向于最初派送路线，并利于加快收敛速度。

3.适应度函数。度量个体适应度的函数称为适应度函数，它是以数值的方式来描述个体优劣程度的指标，是遗传算法中评价个体好坏的依据，个体染色体的适应度越高表示个体越优秀，反之越劣质。

适应度函数依据目标函数确定的用于区分群体中个体好坏的标准，本文中目标函数是最小问题，因此需要将目标函数进行相应转换，本文的适应度函数：

其中Z为目标函数，c为目标函数函数界限的保守估计值。

4.选择。遗传算法中使用选择算子对种群中的个体进行优胜劣汰操作，根据每个个体的适应的大小进行选择，适应的较高的个体被遗传到下一代群体中的概率比较大；反之亦然。为防止随机操作造成误差，本文采用选择算子采用轮盘赌选择与精英保留策略相互结合的方式，即防止随机误差，又加快收敛速度。

5.交叉。在遗传算法中，通过交叉运算将两个染色体交换部分基因，形成新的染色体，从而产生新的个体。交叉算子在遗传算法中起着关键作用，是产生新个体的主要方法，很大程度决定了遗传算法的搜索速度。本文采用两点交叉（Two-point Crossover）方式进行交叉运算。主要分为两步：（1）在相互配对的两个个体编码串中随机设置两个交叉点；（2）交换两个个体在所设定的两个交叉点之间的部分染色体。由于本文采用十进制编码，两点交叉会出现重复，因此需要加入去除重复这一步。

6.变异。变异是指将染色体编码串的部分基因改换成其他基因，进而形成新个体的现象。在遗传运算中，通过变异算子可以维持种群的多样性，防止早熟，有效提高局部搜索能力。本文采用均匀变异方法来进行变异操作，均匀变异是指用符合某一范围均匀分布的随机数，以某一较小的概率替换某一个体染色体中各个基因上原有的基因值，具体操作过程如下：首先依次设定编码体中的每个基因座的变异点，然后对每个变异点，以变异概率从基因取值范围取随机数来替代原有基因值，最后进行去重工作。

均匀变异操作可以在整个搜索空间内自由寻找，可以很好地确保种群的多样性，防止过早陷入局部最优。

四、模型仿真及分析

（一）初始设置及初始配送路线

本文仿真实验在matlab2014a版本上进行运行。为了验证模型的有效性，本文借鉴文献[12]中的方法，在100*100平面采用全随机方式选取29个点，具体信息如表1所示。初始配送点为点1（50，50），配送点之间的距离为直线距离，假设配送车辆的载重量为10，车辆速度为每个单位时间行驶1单元距离，车辆在配送点的服务时间为0，从0时开始对这29个点进行配送。

表1 客户点信息表

根据初始配送要求，求出初始配送路线如图2所示。

车辆1配送路线：1-4-12-24-10-2-5-25-1（满载率：92.0%）

车辆2配送路线：1-8-21-30-15-19-1（满载率：99.0%）

车辆3配送路线：1-17-28-3-11-16-22-6-7-1（满载率：82.0%）

车辆4配送路线：1-27-9-20-18-23-29-1（满载率：97.0%）

车辆5配送路线：1-26-13-14-1（满载率：73.0%）

图2 初始配送路线图

（二）干扰分析

假设在配送途中车辆3在行驶到配送点28时，客户11的配送位置由原来的（15，44）变为（30，50），本文在不考虑其他车辆援助情况下，为完成配送任务，分别采用重调度法和本文方法重新设计配送路线，调整后配送路线如图3所示。

通过两种方法求解结果进行对比如表2所示。我们通过这两种方法与初始配送路线进行对比得出结论：重调度法仅以最小配送成本为目标进行路线设计，虽然使得配送距离比本文方法少，但是具有较高的客户不满意度，拉低物流运营商整体服务水平；而本文方法在增加了少量配送成本的基础上，大大降低了客户不满意度。从物流运营商长远角度考虑，采用本文方法运输成本可能会部分增加，但是可以很好地降低客户不满意度，增强客户粘性，进而与客户建立长期的稳定关系，有利于物流运营商长远发展，现实持久盈利。

F252

A

1004-2768（2016）11-0019-04

2016-09-20

浙江省哲学社会科学规划课题“面向协同网络组织的新服务开发激励模型与策略研究”（13NDJC038YB）；“管理科学与工程”省高校人文社科重点研究基地优秀硕士学位论文培育“基于配送地点变化的物流路线优化研究”（GK150203204004/016）

卜心怡（1961-），女，上海人，杭州电子科技大学管理学院教授，研究方向：系统分析和决策优化、服务管理、供应链管理；刘超（1990-），男，山东潍坊人，杭州电子科技大学管理学院硕士研究生，研究方向：物流系统分析与仿真、供应链管理；钱军（1991-），男，安徽宣城人，杭州电子科技大学管理学院硕士研究生，研究方向：物流系统分析与仿真、供应链管理。