带时间窗的甘肃应急物流配送路径优化研究

尹耀杰 马丽荣

摘要：文章对应急物流配送路径进行分析的基础上，构建了带时间窗的应急物流配送路径最短优化模型，提出了遗传优化算法，最后以漳县公路网络为算例进行分析，利用MATLAB软件编程实现，算例结果表明，遗传优化算法更好地解决应急物流配送问题，验证了遗传算法解决应急物流配送路径的可行性。

关键词：时间窗;应急物流;配送路径;遗传算法;甘肃省

自然灾害具有强大的破坏力，给人类带来了巨大的财产损失和人员伤亡，经常造成自然环境破坏，在不同程度上造成重大的经济损失和人们心理恐慌，为降低灾害造成的损伤，在短期内灾区急需大量的救援物资，应急物流开辟了为快速有效地开展救援工作同时提供满足受灾群众生活和医疗物资的需求，而应急物流具有突发性和紧迫性等特点，为了提高应急物资配送的及时性和有效性，要对应急物流车辆配送路径做出科学的决策。然而，由于灾情的不确定性和难以预测性以及救援的紧迫性使得应急管理部门很难准确获得受灾地区对应急物资的需求量。同时，应急车辆配送物资的过程中常常面临路径通行能力差、山体滑坡和道路塌陷损坏等风险，也影响应急物资的精准送达。

如何以最短路径、高满意度、最低成本等为目标在最短的时间内完成突发事件下应急物资的配送问题，成为国内外学者高度关注的问题。李志等研究了以物资分配公平性和需求效用最大化为目标，建立基于多目标的混合整数规划方法应急物资供应点定位-分配模型;杨恩缘，李进等提出了以运输成本最小为目标，结合容量限制及应急配送的多样性和多级性特点，构建了应急物资多级配送选址-路径的混合整数规划模型;陈湉，林勇提出基于离散蜂群的灾害应急物流车辆调度优化问题研究，以供应过量、物资分配不足所造成的损失最小化、车辆调度成本最低为优化目标，以服务时间窗和车辆运载能力为约束条件，构建了应急需求下的車辆调度优化模型，并采用离散蜂群算法求解;张伟，杨斌等以运输距离最短化、运输时间最小化和路径复杂性为目标，建立多目标应急物流路径规划模型;蒋杰辉，马良利用改进智能水滴算法求解应急物资配送中车辆路径优化问题;朱娜，郑亚平采用“矢量投影-理想点法”以车辆运载能力等为限制条件，以应急运输成本、应急时间及救灾点数量为优化目标构建了应急物资分配模型;朱佳翔等以运输时间最少、成本最优以及用户满意度最大等为目标，构建多阶段多目标应急物流配送的灰色动态规划模型。

一、问题的描述

带时间窗的车辆运输路径问题（VRPTW）是应急物流研究的基本问题，也是实现在有限时间内实现物资的及时送达，提高救援效率，将灾害降到最小化的有效途径。本文针对甘肃应急物流运输与配送问题，构建了带时间窗路径最短为目标的车辆配送模型，设计遗传算法对应急物流配送路径模型求解，兼顾考虑多个制约条件，如车辆载重量的限制，受灾点对物资需求时间窗的限制等。假设有一个配送中心对多个受灾点进行应急物资配送，配送中心有容量不同的车辆，受灾点对物资需求的时间各不相同，要求在规定的时间内完成配送任务，规划配送路线并要求每条路线上只有一辆车配送，规定车辆从配送中心出发完成配送任务后再返回配送中心，使车辆配送车辆总运达的路径最短，利用MATLAB软件编程求解，计算出应急物流最短配送路径最优解。

二、构建带时间窗的应急物流配送路径模型

（一）模型参数与变量定义

N={0，1，…，n，n+1}是节点集合，0，n+1表示配送中心，需求点编号为{1，…，n};

di：需求点i的需求量;

K={1，2，…，k}是车辆集合，为了降低配送成本尽可能合理使用配送车辆，采用下列公式确定车辆数：

k=■d■/μc+1

A：弧的集合;

xijk={0，1}，表示车辆k是否从i点出发前往j点，如果车辆k是从i点出发前往j点，则xijk=1，否则xijk=0;

Cij：表示i点和j点之间的距离;

Wik：表示车辆k对i点的开始服务时间;

si：表示受灾点i的服务时间;

tij：表示从i点到j点的行驶时间;

Mij：一个足够大的数，可以取10的7次方;

ai：受灾点i的左时间窗;

bi：受灾点i的右时间窗;

E：配送中心的左时间窗;

L：配送中心的右时间窗;

Ck：车辆k最大装载量;

s+（i）：表示从i点出发的弧的集合;

s-（i）：表示回到j点的弧的集合。

（二）模型设计

min■■cijxijk（1）

■■xijk=1 ？坌i∈N（2）

■x0jk=1 ？坌k∈K（3）

■xijk-■xjik=0 ？坌j∈N，？坌k∈K（4）

■xi，n+1，k=1 ？坌k∈K（5）

wik+si+tij-wjk≤（1-xijk）Mij，？坌k∈K，？坌（i，j）∈A（6）

ai（■xijk）≤wik≤bi（■xijk） ？坌k∈K，？坌i∈A（7）

E≤wik≤L，？坌k∈K，？坌i∈{0，n+1}（8）

■■xijk≤C ？坌k∈K（9）

xijk=10 ？坌k∈K，？坌（i，j）∈A（10）

其中目标函数（1）表示车辆最短应急物流配送路径;（2）～（10）是约束条件，（2）表示每个需求点只能被分配到一条配送路径上;（3）表示每条配送线路上从配送中心出发只能前往一个需求点;（4）表示车辆k在路径上的流量限制;（5）表示车辆配送完毕都必须返回配送中心;（6）表示配送时间连续性;（7）表示需求点时间窗约束;（8）表示配送中心时间窗约束;（9）表示载重量约束;（10）表示变量取值的约束。

三、基于遗传算法（GA）的应急物流配送路径模型求解

（一）算法设计

1. 编码

在使用GA求解VRPTW问题时，可以采用整数编码的形式对染色体进行编码，当配送车辆数最多为K， 且节点数目为N时，染色体长度为N+K-1，那么表达该染色体的基本形式为（1，2，3，…，N，N+1，…，N+K-1）。

2. 遗传适应度函数

当编码的解码不能保证都满足每条配送路线上对时间窗的约束和载重量的约束条件时，为了解决违反约束问题，进行求解时采用惩罚函数。构建的惩罚函数如下：f（s）=c（s）+αq（s）+βw（s），c（s）表示车辆总行驶距离，q（s）表示各条路径违反的容量约束之和，w（s）表示所有顾客违反的时间窗约束之和。因为违反容量约束相对来说不太容易，所以将α设为10。而較容易违反时间窗约束，所以将β设为100。

目标函数值越小越优越，因此在选择环节，将惩罚函数的倒数设置为适应度函数，即为1/f（s）。

3. 初始化种群

先构建带时间窗车辆路径问题的初始解，再进行初始化种群。

设节点数目为m。

第一步：任意选择某一节点i∈{1，2，3，…，m};

第二步：使用车辆数的初始化k=1;

第三步：遍历节点生成序列Sq=[i，i+1，…，m，1，2，…，i-1]

第四步：遍历节点j至节点m，形成初始解。按序列Sq遍历节点Sq（j），将节点Sq（j）添加到第q条路径中，在添加到对应线路中时要考虑车辆的载重量和左时间窗的约束条件。

得到的初始解就是一个配送方案，通过将个体赋值的方式转换为种群初始化。

4. 选择

从群体中选择优良个体来繁殖子代的过程，并进行优胜劣汰操作，通过基于适应度的过程选择个体解决方案，即从群体中选择多个适应度值大的个体进行交叉、变异以及局部搜索过程。

5. 交叉

交叉是指两个父代个体的部分结构加以替换重组而生成新的个体，然后从前到后把重复的基因位删除，形成两个子代个体。

6. 变异

变异过程是将父代染色体先选择两个位置，将这两个位置上的基因互换形成子代染色体。

7. 终止条件

遗传算法具有随机搜索特性，需要设置终止条件以在可接受时间内获得最优解。比如设置最大进化次数为终止条件，或达到最大迭代数时终止算法运算，再如判断种群适应度值的收敛性，种群适应度值不被继续优化时终止算法运算。

（二）遗传算法的运算流程

遗传算法（GA）是借鉴生物界的进化论，适者生存，优胜劣汰的遗传机制演化而来，是一种随机化搜索全局寻优的生物进化过程算法，具有内在的隐并行性和更好的全局寻优能力，采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，使群体不断进化，逐渐接近最优。GA是解决VRPTW问题的有效方法之一，在求解应急物流配送模型中得到了广泛的应用。其流程图1所示。

四、 算例分析

以漳县公路网络应急物流配送为算例进行分析，漳县有13个乡镇，其分布状况如图1所示，假定武阳镇是配送中心，配送中心有5辆载重量为68t的汽车，各乡镇对物资的需求量由各乡镇的人数来确定，需求点相关信息见表1。

本算例采用MATLAB软件对设计的GA算法进行编程实现，通过仿真运算结果发现，在求解配送路径优化问题时，带时间窗的遗传算法收敛速度快、程序运行时间短、效率高，有效实现了时间约束条件下应急物流配送路径优化，在应急物资配送中调用了3辆汽车，具体的最优配送方案如图2所示，车辆行驶路径及载重量如表2所示。通过求解轨迹结果可以得出基于时间窗的总行驶里程最短的路径安排。

五、结语

本文针对配送中心如何向灾区配送应急物资这一问题，提出了一个基于时间窗的遗传算法的应急物流车辆配送路径优化方案，考虑应急物流的时间约束性，构建了以配送路径最短为目标，满足多个约束条件下优化问题模型，结合模型特点使用遗传算法进行求解，找到目标函数最小时对应的应急物流配送路径。研究结果表明，遗传算法能有效解决应急物流配送路径问题。本文假定只考虑一个配送中心的情况下车辆配送路径优化，实际上，应急物流错综复杂，如应急物资有帐篷、衣物、食品、药品等性质不同的物资，配送要求不同，再如多配送中心问题研究、应急道路状况等，针对复杂情况下对应急物资配送规划是未来研究的重点难点。

参考文献：

[1]李志，焦琴琴，周愉峰.震后应急物资供应点的多目标动态定位-分配模型[J].计算机工程，2017，43（06）：281-288.

[2]杨恩缘，李进，严翌娴，黄文耀.震后多品种应急物资多级配送中的选址-路径模型[J].灾害学，2016，31（02）：200-205.

[3]陈湉，林勇.大数据背景下台风灾害应急物流车辆调度优化仿真[J].灾害学，2019，34（01）：194-197.

[4]张伟，杨斌，朱小林.多目标应急物流路径选择研究[J].江苏科技大学学报（自然科学版），2017，31（02）：219-224.

[5]蒋杰辉，马良.多目标应急物资路径优化及其改进智能水滴算法[J].计算机应用研究，2016，33（12）：3602-3605.

[6]朱娜，郑亚平.复杂物流网络下的应急物资分配模型[J].数学的实践与认识，2016，46（19）：133-140.

[7]朱佳翔，谭清美，蔡建飞.基于双重不确定性的应急物流配送策略[J].系统工程， 2016，34（03）：1-7.

[8]李洋，陆娟.物流运筹学[M].北京：科学出版社，2017.

[9]余胜威.MATLAB优化算法案例分析与应用[M].北京：清华大学出版社，2014（09）：227-261.

*基金项目：甘肃省社科规划项目“基于群智能算法的甘肃省应急物流配送中心选址及路径优化研究”（编号：20YB114）;甘肃省科技厅软科学项目“基于多目标的甘肃省应急物流配送路径优化问题研究”（编号：20CX9ZA023）。

（作者单位：兰州石化职业技术大学国际商务学院）