面向城市商超物流配送的异构车辆调度研究

张淼寒，安裕强 ，潘 楠，孙雨轩，鲍 景，高 瀚，韩宇航

(1.昆明理工大学 民航与航空学院，云南 昆明 650500；2.红云红河烟草(集团)有限责任公司 ，云南 昆明 650000；3.昆明理工大学 信息工程与自动化学院 ，云南 昆明 650500；4.昆明理工大学 管理与经济学院 ，云南 昆明 650500)

0 引言

近年来，随着车辆的快速增长以及城市物流货运量的急剧增加，城市交通日趋拥堵，同时受交通政策、节假日等条件的影响，当前交通网具有一定的实时性和随机性[1].如何高效实现城市物流配送的降本提效已成为国内外学者广泛关注的问题[2].

城市物流配送不同于传统的长途运输配送，其具有流量大、流向多变、节点多、分布广、配送半径小、路径实时性、可选择车辆多等特点[3].因此,城市物流配送的核心问题是涉及多维约束条件下的车辆路径优化问题(Vehicle Routing Problem,VRP).随着相关学者在时间窗、多车型配送、配送成本、多目标优化等多方面展开研究，城市物流的配送调度模型也愈发复杂多变.同时,考虑到传统算法[4]难以高效获得问题解空间，当前相关文献大多倾向于利用元启发式算法[5-7]来求解此类多维复杂环境约束条件下的VRP问题.在时间窗约束的VRP问题[8]中，文献[9-11]在时间窗问题的基础上分别添加了多车型、作业时间及客户需求作为优化目标，同时设计了非支配排序遗传算法、多邻域自适应禁忌搜索算法和精英蚁群算法进行模型求解.在多车型调度问题中，文献[12-13]设计了改进的遗传算法求解异构车辆在动态路径规划及集配货的车辆调度分配方案.文献[14]则考虑了异构车辆对油耗的影响建立了一种多车型的低碳混合整数规划模型.文献[15]综合考虑时间窗和多车型对危险品运输的影响，设计了基于变邻域的混合多目标算法进行求解.在配送成本问题中，文献[16-17]在以总成本最低为目标的基础上分别构建了顾客满意度最大和需求紧迫度有限的物流调度模型，并设计离散多元宇宙算法和改进的遗传算法进行调度方案求解.在多目标优化方面，文献[18]以配送成本、车辆数最少、客户满意适度最大构建多目标路径规划模型，文献[19]则在时间窗约束下，以最小化车辆最大行驶距离和最大化车辆负载之差为多优化目标.文献[20]以总行驶距离、时间窗约束、车辆数量等为多维优化目标并设计局部搜索策略的人工蜂群算法进行多目标模型求解.

虽然上述研究对VRP问题展开了有益探索，但随着智慧城市物流供应链的数字化构建，城市物流调度模型在约束条件及优化目标上也将更加符合实际情况.为此，本文重点研究面向实时交通条件下城市超市配送的异构车辆调度问题，充分考虑包括配送成本、时间窗、道路车型限制、车辆泡货的体积与重量比、车型分配、路径实时性等多维角度下的VRP问题，并提出将配送车辆的泡重比作为约束条件考虑进物流车辆路径规划中，构建符合实际情况下的多目标优化数学模型，最后设计改进的鲸鱼优化算法进行模型仿真求解及数据分析对比.

1 问题描述

随着城市经济化水平的提高以及车辆限制的相关政策不断出台，传统的城市车辆配送模式往往会产生大量的资源浪费，因此考虑如何构建面向交通拥堵实时性、客户时间窗、车型限制、车辆泡重比、调度运输成本等多维约束条件下实现以成本最低、装载量最高为目标的车辆路径调度规划已成为当前要解决的重点问题.

1.1 模型假设

(1)确定配送中心和客户点位置，且可以满足客户需求；

(2)车辆由配送中心出发，完成任务后返回配送中心；

(3)配送中心车辆数目有限，各型号车辆各有Ca辆；

(4)各客户点仅以其所在辖区的主要所在位置来判断所能通行的车辆；

(5)某市内不同客户点所在辖区ψ对车辆型号a的要求约束不相同.

1.2 考虑交通拥堵下的车速实时性

1.3 数学模型的建立

为提高车辆配送效率的同时尽可能的降低配送成本，因此构建以总成本最小，装载率最高为优化目标的城市异构车辆调度模型，目标函数如式(1)所示：

(1)

式中：F1为车辆总固定成本,元；F2为车辆总运费，元；F3为所有司机的工资成本，元；τ为车辆配载利用率；Rak为0-1变量，表示车辆ak是否进行运货，若是取1，否则取0.

车辆的总固定成本包括其起步费及点位费，计算公式如式(2)所示：

(2)

式中：Pak表示车辆ak的固定成本;PSak表示车辆ak的起步价;Pfa表示车辆型号a的点位费;Kak,j为0-1变量，若车辆ak到达客户点j,则Kak,j取1， 否则取0；I={1,2,…}为车辆型号集合,Ca={1a,2a,…}为车辆集合；

车辆的配送成本分为泡货与重货2种方式计算.式(3)为车辆总配送成本计算公式，式(4)为泡货及重货计算方式，式(5)为车辆ak泡重比的计算方式：

(3)

(4)

(5)

式中：Sak为车辆ak的运输成本，元；经查相关陆运资料，选泡重比参数μak为5作为分界线进行计算，若泡重比小于等于5则运用重货单价计算，否则按泡货单价进行计算；q1为重货的运输单价，元/(kg·km)；q2为泡货运输单价，元/(m3·km)；Wj为客户点j所需的货物重量，kg；Vj为客户点j所需要的货物体积，m3；loj为发货点o到j个客户点的距离，m；ljj′为距离矩阵中j客户点到j′客户点的距离，m.

以作业时间为标准来计算司机的工资成本，如式(6)所示：

(6)

式中，G表示工人单位时间工资，元/小时.

车辆ak的装载率及总车辆装载率τ由式(7)、(8)得到：

(7)

(8)

式中：Wakmax和Vakmax分别为车辆ak的最大装载重量和最大装载体积;Ψ表示辖区的集合,ψ∈Ψ,Ψ={1,2,…}；Jψ表示辖区ψ的客户点j的集合Jψ={1ψ,2ψ,…}.

在配送过程中，每个收货点只能访问一次，约束如式(9)所示：

(9)

在调度配送过程中需满足各型号车辆的最大数量限制.各型号的车辆数量由配送公司自身条件决定.约束如式(10)所示：

(10)

配送车辆ak在配送过程中需满足最大装载重量和最大装载体积限制：

(11)

(12)

在辖区ψ内的车型为a的车辆一次出车能去的客户点数为ζ，该限制由公司拟定，约束如式(13)所示：

∑Kψak,j≤ζ，∀a∈I,∀k∈Ca

(13)

在车辆配送过程中需满足各收货点配送时间窗的限制，约束如式(14)所示：

(14)

式中，Tak,0为车辆ak驶出配送中心的时间.

车辆ak在配送过程中需满足最大行驶距离约束，如式(15)所示：

∑(ljj′·Kak,j)+loj≤Lakmax，∀a∈I,∀k∈Ca

(15)

式中，Lakmax为车辆ak的最大行驶距离.

2 算法描述

2.1 传统鲸鱼群算法更新策略

在传统鲸鱼群算法中，算法的更新通过鲸鱼群的跟随搜索、围捕猎物、搜索猎物来实现，每个个体都有可能执行这3种行为之中的其中一种.在对每个个体的变量进行更新时，将生成一个随机数rand判断该个体的该变量执行哪一种行为，如公式(16)所示：

(16)

(17)

式中，g为当前迭代次数；G为总迭代次数.鲸鱼群优化算法采用跟随搜索的寻优方式，使得鲸鱼群优化算法在解决大规模优化问题时极易陷入局部最优，并且鲸鱼群优化算法涉及到的参数较多，导致参数寻优能力受参数变化影响较大.

2.2 改进策略

2.2.1 指数型温度下降

随着迭代次数的增加，传统模拟退火的降温策略在后期易使算法陷入局部最优，后期的全局寻优能力较弱，因此为提高算法的全局搜索能力.本文所提温度下降公式如下所示：

T=T0exp(-Cg)

(18)

在迭代初期，温度值较高，粒子对能量值较高的状态接受率较高;随着迭代次数的增加，温度值会急速下降并逐渐趋于稳定;在后期,温度值较低，粒子对能量值较高的状态接受率较低，符合现实情况.

2.2.2 变量交叉扰动

为使个体的搜索更具有方向性，引入变量交叉扰动方式，包括单变量交叉扰动与多变量交叉扰动.在原种群维度D中，首先随机选中多个变量r，进行交叉产生新个体，若新个体的目标函数值为正无穷，即不满足约束条件，将新个体删去，改为采用单变量扰动产生新个体;如果新个体不满足约束条件则退出扰动，不再产生新个体.多变量交叉扰动与单变量交叉扰动公式如式(19)、(20)所示：

(19)

(20)

2.2.3 种群分级

为平衡算法的全局寻优能力与局部寻优能力，采用种群分级的思想对种群个体进行划分.首先对目标函数值进行排序，选定一个阈值，目标函数值大于等于该阈值，说明其位置较差，需要跟随最优个体搜索，所以这一类个体将采用公式(16)进行跟随搜索；目标函数值小于该阈值，说明该个体位置较优，如果继续进行跟随搜索可能会陷入局部寻优，因此这一类个体将通过公式(19)、(20)进行交叉搜索.

2.3 基于改进混合鲸鱼群算法步骤

基于改进混合鲸鱼群算法步骤如下：

Step 1：初始化算法参数，随机初始化种群；

Step 2：计算当前温度T；

Step 3：通过个体变量计算车辆订单信息与车辆路径信息；

Step 4：计算种群目标函数值，保存全局最优个体与全局最优个体的目标函数值；

Step 5：执行种群分级操作；

Step 6：目标函数值较大的个体根据公式(16)执行跟随搜索操作；

Step 7：目标函数值较小的个体根据公式(19)、(20)进行交叉搜索操作；

Step 8：是否达到最大迭代次数，是则退出；否则返回Step 2.

其算法流程图如图1所示.

图1 算法流程图Fig.1 Algorithm flow chart

3 算例分析

3.1 仿真结果

为验证问题模型及所提改进算法的有效性，首先选取北京市内多个商超类型客户点的运输配送业务为背景，并采用中国外运股份有限公司2021年提供的公开数据集生成仿真算例；然后用文中设计的混合鲸鱼群算法进行求解，制定合理的配送方案；最后选取粒子群算法、模拟退火算法及鲸鱼算法进行算例对比，以验证本文所提出的面向城市超市配送的异构车辆智慧调度模型及算法的普适性.其中，文中所用各型号的车辆信息如表1所示，订单信息如表2所示，城区交通拥堵延迟系数情况如表3所示.

表1 各型号的车辆信息表Tab.1 Vehicle information of each model

表2 订单信息表Tab.2 Order information

表3 北京市配送城区交通情况Tab.3 Traffic conditions in various urban areas of Beijing

为保证横向对比算法的公平性，PSO、WOA、SA、WOA-ISA 4种算法的种群数量NP=200,迭代次数G=200；PSO算法中的学习因子c1、c2等于1.5，粒子速度vmax=5，vmin=-5;WOA算法中l=1,初始温度设置为100°.将4种算法各运行30次取得其中的结果.其中，WOA-ISA算法的规划结果如表4所示，任意一次算法求解的收敛曲线如图2所示，4个算法运行30次的平均目标函数值如图3所示，目标函数最值对比如图4所示.进一步将图5的5个指标归一化处理进行对比分析，4个算法的指标对比如表5所示.

图2 单次函数值对比Fig.2 Comparison of single function value

图3 平均函数值对比Fig.3 Comparison of average function values

图4 目标函数最值对比Fig.4 Comparison of objective function maxima

图5 归一化指标对比图Fig.5 Comparison chart of normalized indicators

表4 随机选取WOA-ISA算法30次运行过程中某次的规划结果Tab.4 Random selection of the planning results of a certain time of the 30 runs of the WOA-ISA algorithm

3.2 仿真实验结果分析

由图2和图3可以看出，相较于SA算法、PSO算法和WOA算法，本文所提出的WOA-ISA算法的全局搜索能力较强，在100代左右，其他算法趋于收敛的同时本文所提算法仍保持着高效的搜索模式.从图4的最值比较中也可以得出WOA-ISA算法在求解过程中的优异性.这主要得益于算法中的种群分级以及变异交叉扰动操作，使得算法具备跳出局部最优解的能力，提高了算法的全局搜索性能，这也说明了本文所提改进策略的优越性.由图3可知，本文所提算法相较于SA、PSO、WOA算法,其目标函数值分别降低了42%、35%及26%.

进一步根据图5、表5可知：相较于SA、PSO、WOA算法，无论是配送成本、泡重成本、配送车辆数量、最长配时及装载率，本文所提算法均有着较强的竞争力,在运输固定成本上分别降低了6%、15%、12%,泡重成本减少了42%、36%、35%,配送时间降低了20%、24%、14%,装载率提高了17%、9.2%、5.8%，经过拥堵路段的次数降低了37%、25%及29%,发车数量减少了近2辆.达到了配送成本最小、车辆装载利用率最大、发车数辆最少的多目标优化.本文所提的WOA-ISA算法相较于其他算法具有更好的收敛性以及收敛速度，同时具备跳出局部最优解的能力，具有更好的全局搜索性.因此相较于其他的智能优化算法，WOA-ISA算法在解决面向城市超市配送的异构车辆智慧调度模型问题上，可以高效地提供更为有效的调度方案，在降低成本的同时极大提高了车辆的配送效率.

表5 算法指标对比Tab.5 Comparison of algorithm indexes

4 结论

本文在城市物流配送快速发展的背景下，充分考虑到当前物流调度模型的不足，建立以车辆泡重比、司机工资成本、运费成本、车辆物理约束、时间窗约束、车辆配送的实时性、拥堵系数为约束条件，以配送成本最小，车辆装载利用率为多维优化目标的异构车辆智慧调度数学模型.同时针对鲸鱼算法在求解大规模目标问题时存在的缺陷，设计了一种包括变量交叉扰动、种群分级等策略的混合鲸鱼群算法.最后通过仿真实验表明，本文所提算法能够有效应用于该类复杂大规模问题，提高车辆装载率、降低配送费用、减少配送公司发车次数，为数字化物流系统的构建提供理论参考.