基于遗传禁忌混合算法的软时间窗无人配送车路径优化

陈志强，吴 芳

(兰州交通大学 交通运输学院，兰州 730070)

目前食品配送服务仍处于持续发展阶段[1]，需要考虑配送过程中的及时性与配送成本的节约性[2]，尤其在疫情灾害蔓延以及极端恶劣天气无法保证时效等情况[3-5]，利用无人配送车恰是解决这类问题的有效手段.一方面是面对当下肆虐疫情，无人配送车可杜绝人员间直接接触，降低新冠状病毒的传染概率，为疫情隔离者或封闭小区居民提供生活必需品[6]，即使在一些国家的快递配送人员因为担心在配送过程中无法保持安全距离会感染新冠病毒而纷纷罢工的情形下，无人车配送依然可保证正常的配送业务顺利进行；另一方面无人配送车可在极端恶劣天气中代替人员进行物品运输，有效防止配送人员意外发生，提高配送的安全性.此外，考虑到无人配送车在日常配送中也可节省工作人员的工时支出，从而可进一步降低配送成本，因此，推进无人配送车行业发展愈加重要.

2017年初美国硅谷初创公司便推出无人配送车，为即时配送公司DoorDash提供服务，实现了在15至30分钟时间内完成一次配送.次年初，在“中国发展高层论坛2018年会”中，美团公司首次亮相国内的无人配送车.截止目前，国内外部分学者对无人配送路径优化问题也进行了大量研究，并取得一定的成果，王愚勤等[7]针对智能网联无人车配送问题，考虑了最大载重量及车载容量，建立关键点更新策略下的实时调整模型，并通过遗传算法验证了模型可行性.王雷等[8]利用软时间窗约束限定了配送车等待顾客时间，并运用多种群遗传算法(MPGA)确定运输成本.张洪海等[9]、Song等[10]、Roberge等[11]学者分别利用改进A*算法、遗传算法、PSO等算法分析了复杂环境下的无人配送最优路径问题.

顾客满意度往往是评价配送任务的关键指标[12]，上述文献均着重考虑了不同背景下的无人配送成本，部分忽略了服务对象在系统中的需求.其中含软时间窗约束的路径优化研究，满足了无人配送任务的及时性，而未将其作为目标函数追求全部顾客最小等待时间.本文则针对无人配送车进行约束限定，包括容载量约束、续航里程约束及服务范围约束的同时，着重考虑顾客在运输系统中的重要性，引入配送车辆到达时间对客户的影响程度，并以软时间窗及时间成本为目标函数寻求系统中每位顾客最小等待时间及总时间成本最小的最优路径.通过惩罚函数的设定淘汰满意度较低的路径，间接为顾客因等待过久所产生的焦虑感提供缓解措施.最后，基于遗传算法中变异算子与禁忌搜索算法的结合，提高模型求解过程中的收敛能力与最优解的逼近能力，为无人配送车路径优化问题提供不同的求解算法.

1 无人配送车的路径优化问题描述

1.1 问题分析

无人配送车路径优化问题需从三大类方向考虑：

1) 公司经营者角度：对配送公司而言，通过车辆路径优化，实现利益最大化是其追求的核心内容.需保证在满足容量限制约束、最远距离约束的前提下，尽可能多的完成服务工作、更全面的照顾到每一位客户，间接性地增加顾客回购概率，使运输成本、公司形象、经营口碑得到更好的改善[13].因此，本文将时间成本作为极小化目标函数之一，以满足经营者的要求.

2) 顾客角度：顾客是检验每辆配送车路径优化是否有效的关键因素[14-15].为减少顾客因订单到达时间的不确定性，导致配送车过晚到达配送点从而降低顾客期待值，或是过早到达造成配送时间的额外损失.需建立带软时间窗的目标函数，并分别赋予配送车相对客户的早或晚到达惩罚系数，增加配送作业的准时性与满意度.

3) 配送车自身能力要求[16]：需要在满足配送车自身能力限制条件下运行，即要求单辆车往返配送中心过程中行驶总里程在限定续航之内、配送速度考虑安全因素应低于某一阙值、最远可达距离因其公司经营范围不得超出所设定值，以及因自身容量限制需在单趟配送过程中配送总容积少于额定容量，以此可建立部分模型约束条件.

1.2 参数设定

本文以美团公司在北京顺义、亦庄及深圳地区的实际运营数据为参考，设定当前状态下配送车可用数量、点对点间距离、平均行驶速度、配送额定容载量，以及配送车到达理想时间等参数为给定值.并设定每次订单按实际情况只进行简单商品配送服务，第三方商家不参与配货服务，一切货物均由配送公司筹备.配送中心已知且不会发生变化的情况下，所有配送车经各配送点有且只有一次，且均经配送中心出发最终返回配送中心，该问题中顾客只参与取货活动.在此过程中满足配送车额定容量及续航约束下，使配送车辆的时间窗惩罚成本最少、总行驶时间成本最小，解决无人配送车的路径优化问题以满足各参与者的利益最大化.

2 模型建立

考虑时间成本与时间窗惩罚成本最小并结合实际可构建数学模型，设定在某一确定配送周期内可用配送车数量为m辆，若配送中心全部车辆均外出作业时顾客下单订购货品，则该配送任务拖迟至下一周期完成.同时考虑在某一配送点临近周围可能存在顾客多次下单的情况，根据配送任务所负责的区域将同一周期内下单较近的地点合并为一个配送点，并加以额为时间与实际工作相匹配.同时为保证时间及行程成本最优，令其均由一辆配送车完成相应的配送任务，即每一配送点下单次数不小于1次且不超过单辆车额定容量.

无人配送车路径优化目标函数见下式：

(1)

(2)

式中：n表示配送点个数；m表示最大配送车编号；k表示配送车编号(k=1,2,3,…,m)；θα、θβ分别表示配送车相对客户的早、晚到达惩罚系数；tijk表示第k辆车从i到j的行驶时间，h；sijk表示第k辆车从配送点i到j时，在j点对顾客服务时长，h；pijk表示第k辆车从配送点i到j时，在j点额外时间，h；teij、tlij分别表示配送车从配送点i到达配送点j时，在j点的理想最早、晚时间，h；xijk表示决策变量，当第k辆配送车访问路径ij时为1，否则取0.

约束条件建立如下：

(3)

(4)

(5)

(6)

xijk(tik+si+tijk-tjk)≤0,(i≠j,k=1,2,…,m);

(7)

(8)

md,(k=1,2,…,m).

(9)

式中：sd表示单辆配送车续航里程，km；md表示配送服务最远距离，km；dij表示配送点i至配送点j的距离，km；Q表示单辆配送车的额定载容量，件；Iijk表示第k辆车从配送点i到j时，在j点顾客取货次数，次.

其中：式(1)表示目标函数，优化目标是时间成本最小，包括全部车辆行驶时间、配送点服务时间以及额外损失时间.其中额外时间代表该配送点因顾客下单次数不唯一，或多位顾客同一配送点周围下单造成的时间损失，而各配送点间路程时间均由距离及速度参数所得；式(2)表示带软时间窗的目标函数，指配送物品到达配送点的时间准时程度，即顾客满意程度；式(3)表示单辆配送车行驶总里程不大于续航里程；式(4)表示容量平衡，即每个配送点的驶入车辆与驶出车辆数相同；式(5)表示从配送中心出发的配送车，完成相应任务后必须返回配送中心；式(6)表示单辆车完成一趟配送任务所送出配送物品总数(实际载容量)，不得高于额定载容量；式(7)表示同一路径上连续两个配送站点之间，前一个站点的车辆到达时刻不超过后一个站点的车辆到达时刻；式(8)表示每辆配送车均由配送中心出发；式(9)表示单辆配送车只可在经营公司划定范围内活动.

3 算法设计与求解

结合问题特性设计近似算法或启发式算法，是求解大规模NP问题的常用方法.而单纯利用遗传算法可能受交叉算子的性质影响，使染色体间存在相似性，同时由于较小的变异概率会使种群多样性增加缓慢，易于出现“早熟”现象[17].本文引入领域搜索能力较好的禁忌搜索算法恰能解决这类问题[18-19].利用遗传算法中的变异算子与禁忌搜索算法相结合(TSM算子)，改善遗传算法局部搜索能力，使近优解或全局最优解更易得到，算法步骤如下：

1) 确定编码类型，初始化种群；

2) 评价种群中每条染色体的适应度；

3) 利用轮盘赌选择适应度高的个体；

4) 对该代种群中全部个体选择性交叉，并直接进入新种群；

5) 随机选取部分染色体，利用禁忌搜索算法寻求变异子代并直接进入新种群；

6) 判断目前全部染色体的评价指标，根据每代种群选取数量相同的最优染色体作为下一代；

7) 确定是否满足终止条件.若不满足，返回执行步骤3)；否则，跳出循环，得到满意解.

3.1 染色体编码

利用自然数编码，确定配送车路径选择，编码长度为n+m-1(m≤n)，由大于车辆数(m)的部分表示车辆间隔，间隔间的连续数表示不同车辆的路径选择.染色体编码示意图如图1所示，车辆数为5，配送点数量为10，其编码长度为14，随机排列14以内的正整数，产生五条不同子链，圈外数值均表示从0点(配送中心)出发或返回.

图1 染色体编码示意图

3.2 适应度函数

依据上述编码方式，随机选取同种群数量一致的染色体作为初始种群.并利用惩罚函数(见式10)处理未满足约束条件的个体，即当某一个体违反额定容量限制，或是超出配送车续航里程时，赋予该个体罚函数降低适应度，通过迭代淘汰该基因型.

(10)

现对求解多目标最小值问题考虑线性加权，并加入罚函数得到个体适应度函数见式(11)：

(11)

式中：fimin、fimax分别表示各目标函数fi在当前种群中的最值；Infi表示罚函数惩罚参数；μi表示无量纲变量的加权系数，并且适应度值(Fi)直接与选择概率正相关.

3.3 算子操作

3.3.1 选择算子

采用轮盘赌确定新种群个体，并在更新种群时保留上一代优秀个体，防止基因型交叉对最优个体的覆盖.

3.3.2 交叉算子

利用随机数确定交叉染色体及交叉位点，每一个体产生两个交叉位点，交叉个体两两配对，将处于交叉点中间部分基因片段分别置于对方首段，并删除尾端重复基因，其过程如图2所示.

图2 交叉算子操作示意图

3.3.3 变异算子

根据变异概率随机选取染色体进行基因片段的交换、翻转或是插入，并在变异体的基础上利用禁忌搜索算法寻找领域最优解.本文搜索算子采用两交换法，其领域互换操作(SWAP)的领域解数量为n(n-1)/2个，且会因配送点个数的不同发生较大变化.若每次迭代对全部领域解进行搜索比对，运算效率将会大打折扣，因而本文从中随机选择部分领域解进行寻优处理，其选择个数为4(n-1)个，当且仅当n≥8时算式成立.

4 实例计算与结果分析

4.1 算例描述

本文参考美团公司在北京顺义地区的实际运行状况，基础模型参数设定如表1所列.本文选取其中一个配送中心进行研究，设定该配送中心某一时段内产生45次订单配送任务，其中16次订单为同一配送点的重复订购.车辆行驶各点间平均速度取15 km/h，路程时间依据各点间距离与平均速度计算所得，配送车最早理想到达时间与最晚理想到达时间分别为相对原点(配送中心)路程时间前后的0.05 h与0.1 h，配送点坐标及各类时间参数如图3所示.

表1 基础模型参数

图3 配送点坐标及各类时间参数

4.2 问题求解

通过实例问题与算法的分析，设置最大进化代数为300代、变异概率为0.5、交叉概率为0.2、初始种群数目为300、禁忌长度取5、领域解数量经计算在本文中只取112个，此时可更快地获得较好的结果，且不会轻易陷入局部最优解.同时鉴于国内众多配送公司对顾客满意度的重视，设软时间窗目标函数权重为0.66，时间成本权重为0.34.

运用Matlab软件建立遗传禁忌搜索混合算法，并对该算例进行求解，经多次迭代后，得到无人配送车最佳开行方案.为反映迭代过程解的收敛性，绘制评价函数变化曲线如图4所示，并得到最优总时间成本为5.14 h，最优软时间窗目标为0.84.计算结果显示各配送点最早到达时间均满足最早理想时间的要求，且由配送车到达时间超出理想时间范围外最大参数(最大晚到时间差)反映当前路径下车辆晚到情况，其各车辆所经最优子链及参数如表2所列.

图4 评价函数收敛曲线

表2 最优路径及参数

问题求解过程中在迭代至250次时，评价函数便已逐步收敛，对照多次运行结果该算法降低了陷入局部最优解的可能性，充分验证算法有效性.针对运算结果，各项数值均满足约束条件，各子链为该算例下的最优路径，其中存在2辆配送车不参与本次配送任务，为时间成本的节省及顾客满意度的提高寻找到最优方案.

5 结论

无人车辆配送系统利用无人车辆替代人工配送，有利于降低人工费用支出等运营成本，有利于实现配送业务的自动化，有利于提升配送效率和服务质量，尤其有利于应对特殊时期或特殊事件影响下配送需求订单“爆仓”而服务能力严重不足的矛盾.

本文针对无人配送车路径优化问题进行研究，重点考虑顾客层面感知满意度的重要性，使用带软时间窗的目标函数及惩罚函数，淘汰满足总时间成本最小而存在个别满意度较低的全部路径.并利用遗传算法中变异算子与禁忌搜索算法的结合，克服了“早熟”导致的缺陷，提高了解的精确度，为最优路径选取提供适当的算法.本文所研究内容可在配送系统中尽可能降低总时间成本，推动资源的有效利用.并且在“零接触”的配送模下，满足大多数生活物质送到准时性的要求，降低因配送延时所引起的不满情绪.

本文所提出的方法对于快速寻找较为满意的路径成效明显，但忽略了现实道路拥堵延误与配送特殊服务对配送时间造成的影响，也忽略订单优先级等问题，后期应结合现实情况进行更加深入细致的研究.