基于入侵杂草算法的城市生鲜配送优化研究

金峰 董宝力

摘  要：针对实际道路阻抗下的城市“最后一公里”生鲜配送路径优化问题，在保证骑手安全情况下，又能够以最快速度将货物送到客户手上，降低配送成本，从配送过程中电动车遇到的实际道路阻抗因素出发，建立了以最大化顾客满意度，最小化配送成本的多目标优化模型，并利用入侵杂草算法和遗传算法对模型进行分别求解。实验结果验证了模型和入侵杂草算法的有效性。

关键词：生鲜配送;路径优化;入侵杂草算法

中图分类号：F252.14    文献标识码：A

Abstract： In order to optimize the“last-mile”urban fresh food distribution route under actual road impedance， we set up a system that maximizes customer satisfaction and minimizes distribution costs， based on the actual road impedance factors encountered by electric vehicles in the distribution process， in order to ensure rider safety， deliver goods to customers as quickly as possible， and reduce distribution costs. A multi-objective optimization model was used to optimize the model and the invasive weed algorithm and genetic algorithm were used to solve the model separately. The experimental results validate the effectiveness of the model and the invasive weed algorithm.

Key words： fresh food distribution; path optimization; invasive weed algorithms

0  引  言

在“最后一公里”的生鮮产品配送过程中，安全、准时是最重要的两点因素，而配送时通往同一个地点有多种道路可以选择，不同的道路有不同的路况，有明确将机动车道与非机动车道分开的道路更利于配送人员安全、准时地配送。因此合理规划和选择配送路径对于提高顾客满意度、降低配送成本具有重要意义。因此，在配送过程中，应在保证准时配送的基础上，尽量选择利用非机动车道的道路，将货物安全的送到客户手上。

本文所描述的城市配送问题其本质上就是一个VRP（Vehicle Routing Problem）问题。现有的文献对VRP问题的研究已经比较成熟。李桃迎等采用“商家—客户”配对策略，对动态需求的外卖配送问题进行了研究，但没考虑到道路状况问题;贾现召等采用灰色关联度矩阵，应用改进的Floyd算法对实时路况下的生鲜农产品配送问题进行了优化;王恒等在时间窗的约束下，考虑到道路路况的条件下提出改进的自适应遗传算法对生鲜农产品配送路径进行了求解;仝自强等在考虑实时路况的约束下解决了成品油二次配送的路径优化问题;徐肇元利用两阶段启发式算法对外卖配送问题进行了研究，但没考虑到配送过程中的道路阻抗因素。上述文献中对于实际道路状况的研究都是针对于机动车的，对于电动车在行进过程中的道路阻抗因素研究还有所欠缺。综上所述，本文在考虑了时间窗约束以及电动车道路阻抗因素的条件下，建立了满足顾客需求并且总配送时间最短的配送路径模型。

1  问题描述以及模型建立

1.1  问题描述

本文描述的问题实际上是“一对多”的VRP问题，从一个配送中心出发，送到各个客户点。在配送中心有M位骑手可供使用调度，每位骑手各自有一辆最大载货量为Q的电动车可供使用。在某一时刻T，有N个客户点需要配送货物，每个客户点各有一个时间满意度T——即在T时刻内订单到达会满意配送服务，超过这个时间点则会有时间窗惩罚成本。第i个客户点需求的数量为q，最大q应不超过载货量Q。在配送过程中，不同的道路有各自不同的实际情况，有的道路是属于机非混合道路，有的道路属于非机动车道路，为了保障骑手安全行驶，在机非混合道路的行驶速度应不超过15km/h，非机动车道路应不超过25km/h。因此在其他条件相同的情况下，选择拥有非机动车道的道路收益更大。如图1所示，骑手从原点出发，在道路网络中有不少机非混合道路，如何选择道路会影响骑手的配送效率。对于骑手而言，在其他条件相同的情况下，走粗线的非机动车道明显比细线的机非混合车道效率更高。

在这些约束下，要求合理安排配送路线，使顾客满意度最大化，配送成本最小化。为了有效说明上述问题，做出以下几点假设：

（1）每辆车的货物容积一样;

（2）每辆车在一次订单的配送过程中只能被调用一次;

（3）为了保证安全准时，本文使用允许使用的最高速度来表示行驶速度（启动的时间忽略不计）。

1.2  阻碍电动车行驶的因素

一般的BPR（道路阻抗）函数都是针对机动车而建立，主要是通过对道路交通流量的研究来得出道路通行的效率，从而得到不同交通流量道路上的通行时间。它的前提条件是因为机动车经常有排队和等候行为，而电动车相对而言在道路上行驶时更为畅通，不能简单地将针对机动车的BPR函数套用到电动车身上。影响电动车实际通行效率主要是以下因素。在我国的道路系统中，并非所有的道路都设置了非机动车专用车道，有一定数量是机非混合的车道。机非混合车道对于非机动车而言需要更加注意骑行安全，降低骑行速度，国家规定，最高不能超过速度v=15公里/小时，正常电动车的骑行速度不能超过25km/h。

1.3  模型建立

本文以最大化顧客满意度和配送总成本最小化为目标，建立了城市配送路径的多目标优化模型：

MinZ=C+∑c*y+∑∑∑ctx                                   （1）

s.t. ∑y=1    i=1，2，3，…，N                                          （2）

∑q*y≤Q    k=1，2，3，…，M                                      （3）

∑x=1    k=1，2，3，…，M                                          （4）

∑x=1    k=1，2，3，…，M                                          （5）

t=∑∑t+tx    j=1，2，3，…，N                                 （6）

x=    i，j=1，2，3，…，N; ？坌k                                      （7）

y=    i=1，2，3，…，N; k=1，2，3，…，M                               （8）

t=d/v    i，j=1，2，3，…，N                                           （9）

其中：N是客户点的数量;M是配送车辆的数量;Q是每辆车的最大载货量;c是每辆车使用一次的固定成本费和人工费用;c是单位时间内所花费的成本;t是配送车辆从i到j客户点的行驶时间;q是客户点i的需求量;t表示到达客户点j的时间;x是0-1变量，当第k辆车通过客户点i，j时为1，否则为0;y也是0-1变量，表示第k辆车被使用来服务第i位顾客;d表示i点与j点之间的距离;v表示i点与j点之间的速度，若i与j点之间有机非混合车道和非机动车道，则d和v分别按照两种计算，所花费的时间t则加起来得到。目标函数（1）中的第一项C是时间窗的惩罚成本，时间窗的作用是限制配送时间，为了让货物能准时送到顾客手上，顾客满意度可以用配送时间长短来表示。根据调查结果本文设立软时间窗，具体的惩罚函数如式（10）所示。

C=                                     （10）

根据客户的要求，只要配送车辆在0，T时间范围内送达就不需要支付惩罚费用，而超过了这个时间点则需要根据超时的长短来支付相应的费用，并且由于超时会对产品的质量产生影响，惩罚费用随时间呈指数增长，如图2所示。

第二项表示每次使用车辆的固定成本和人工费用;第三项表示配送成本;式（2）表示客户i只能被一辆车服务;式（3）表示一辆配送车的容量限制;式（4）和式（5）表示确保从配送中心出发返回配送中心;式（6）表示从客户点i到达客户点j需要车辆的行驶时间;式（7）、式（8）是0-1变量;式（9）表示从客户点i到客户点j所花的时间是ij点之间的距离除以ij点之间的速度。上述问题是一个已经被证明为NP难问题。

2  入侵杂草优化算法

IWO是2006年由A. R. Mehrabian等提出的一种从自然界杂草进化原理演化而来的随机搜索算法，模仿杂草入侵的种子空间扩散、生长、繁殖和竞争性消亡的基本过程，具有很强的鲁棒性和自适应性。IWO算法是一种高效的随机智能优化算法，以群体中优秀个体来指导种群的进化，以正态分布动态改变标准差的方式将由优秀个体产生的子代个体叠加在父代个体周围，再经过个体之间的竞争，得到最优个体。算法兼顾了群体的多样性和选择力度。入侵杂草算法可以由以下几个步骤实现：

（1）初始化种群

在D维空间随机产生N个可行解（杂草）。

（2）种群繁殖

种群的繁殖是根据杂草的适应度高低来进行的，适应度高的杂草所繁殖产生的后代多一点;反之，适应度低的杂草所繁殖的后代少一些。具体产生的种子数目由公式（11）决定：

Weed=s-s+s                                      （11）

其中：f代表当前杂草对应的适应度值;f和f分别代表当前杂草种群中杂草适应度的最大和最小值;s和s代表当前杂草种群中杂草产生种子的最大和最小数量。

（3）空间扩散

种群产生的种子符合标准正态分布，设定步长为 -σ≤H≤σ。σ变化的公式为：

σ=σ-σ+σ                                      （12）

其中：n表示非线性因子，iter表示最大进化代数，iter表示当前进化代数，σ表示标准差的最终值，σ则是标准差的初始值。

（4）竞争择优

算法经过若干代进化以后，野草和种子的数目会达到预设的最大种群规模Q_max，种群中野草和种子按照适应度大小进行排序，选取适应度较好的前Q_fmax个个体，淘汰其余的个体。

3  仿真实验分析

案例计算：

本文以某生鲜超市的“最后一公里”配送实例为仿真对象进行分析。在某块区域范围内，某个时间点需要为17位顾客进行配送，每辆车可容纳的体积约为0.6立方米，每位骑手的成本约4.5元，单位时间所需要的成本为0.1元/min，车辆固定调度成本为10元/辆。表1表示各个顾客的坐标和能够接受的配送时间，图3表示配送中心以及各个顾客之间的路况，坐标原点为某生鲜超市所在地，为方便坐标图中将各点表示出来，所有的点坐标在图中缩小100倍，不影响实际的计算。

运用Python编写代码对该模型进行求解，模型的具体参数如下所示：初始种群规模N=3，非线性因子n=3，种群的最大种子数和最小种子数为s=20，s=1， 种群的最大和最小杂草数为N=20，N=5，最大迭代次数为500次。同时也用遗传算法对该问题进行模拟仿真，以此来对比两种算法的优越性。遗传算法（GA）的选择算子使用轮盘赌的方式获取，交叉概率选择P=0.7，变异算子选择P=0.04。对两种算法进行分别计算得到结果如图4所示。

从图4中可以发现：遗传（GA）算法在大约300代开始收敛趋于稳定，此时的目标函数值（总成本）为84.6元;入侵杂草（IWO）算法在大约200代就开始收敛趋于稳定，此时的目标函数值（总成本）大约为65.2元。由此可以说明，入侵杂草算法比遗传算法拥有更快的收敛速度和更优的优化结果。

经过仿真模拟得到的最优配送路径如图5、表2所示。

4  结  论

本文针对城市“最后一公里”的配送问题上，由实际配送中遇到的道路状况出发，为保证骑手安全，提出以最大化顾客满意度，最小化配送成本的多目标优化模型。并且利用杂草入侵算法和遗传算法对该模型进行了求解，结果表明入侵杂草算法比遗传算法拥有更快的收敛速度和更优的結果。本文在计算点与点之间的距离时，虽然是使用的实际道路中需要行进的距离，但是本文中的道路已被简化，现实中的斜路弯路都被简化成了直路且只保留了大路，城市中的各种羊肠小道不在考虑范围之内，如何将这些弯路斜路以及小路一起考虑进去将会是下一步需要研究的点。

参考文献：

[1] 李桃迎，吕晓宁，李峰，等. 考虑动态需求的外卖配送路径优化模型及算法[J]. 控制与决策，2019，34（2）：406-413.

[2] 贾现召，戚恒亮，贾其苏，等. 实时路况下同城生鲜农产品配送路径优化[J]. 江苏农业科学，2017，45（17）：292-295.

[3] 王恒，徐亚星，王振锋，等. 基于道路状况的生鲜农产品配送路径优化[J]. 系统仿真学报，2019，31（1）：126-135.

[4] 仝自强，李鹏翔. 考虑实时路况和车辆周转率的成品油配送路径优化研究[J]. 工业工程与管理，2019，24（2）：109-115.

[5] 田源. 机非混合道路交通流模型校正以及道路阻抗函数的研究[D]. 北京：北京交通大学（硕士学位论文），2012.

[6]  Alireza Goli， Erfan Babaee Tirkolaee， Behnam Malmir， et al. A multi-objective invasive weed optimization algorithm for robust aggregate production planning under uncertain seasonal demand[J]. Computing， 2019，101（6）：499-529.

[7] 何南，赵胜川. 城市道路阻抗函数模型研究——以大连市为例[J]. 公路交通科技，2014，31（2）：104-108.

[8] 张新，李珂，严大虎，等. 改进入侵杂草算法求解柔性作业车间调度问题[J]. 系统仿真学报，2018，30（11）：4469-4476.

[9] 陈旭，陆丽丽，曹祖平，等. 道路阻抗函数研究综述[J]. 交通运输研究，2020，6（2）：30-39.

[10] 余建军，程文琪，吴永忠. 考虑顾客满意度的生鲜外卖路径规划[J/OL]. 工业工程与管理，1-10[2020-10-25].