基于物联网的X公司冷链物流配送路径优化研究

我国是一个农业大国，随着国民经济的不断发展，人们的生活质量日渐改善，对生鲜农产品的需求量也越来越高[1],然后，生鲜农产品具有易腐败变质的特性，因此，其运输和配送环节至关重要。但是由于我国冷链物流发展起步较晚，我国冷链物流运输设施不完善，配送模式相对落后[2]。利用物联网技术优势，能够对冷链物流的配送路径进行科学合理的优化[3,4],提出生鲜农产品的新型配送模式，有利于冷链物流信息化平台的构建，有效解决农产品配送信息不透明、质量难追溯等问题，降低配送成本。

在物联网技术的支持下，研究一个配送中心、多个客户点的闭合式车辆路径问题(VRP),寻求最优的配送路线，实现配送中心的总配送成本最低。本文考虑的成本因素有固定成本、运输成本、制冷成本、货损成本、时间窗惩罚成本以及物联网使用成本，由此构建冷链物流配送路径优化模型。

为了便于对X公司冷链物流配送路径优化问题进行研究，在不改变实际问题本质的前提下，提出如下模型假设。

①客户点的位置、需求量和时间窗都已知，且配送中心的库存量可以满足所有客户需求；

②配送车辆从配送中心出发，服务结束后返回配送中心；

③所有冷链车类型都相同，且冷链车最大载重量已知；

④单个客户需求量不能超过配送车辆的额定载重量；

⑤配送过程中会发生产品变质，产生货损成本，且所有产品的腐坏率都相同；

⑥每个客户仅由一辆冷链车提供一次服务；

⑦忽略配送过程中气候不适、道路拥堵等极端情况；

⑧单个客户的需求不能进行多次配送；

⑨顾客对配送服务有时间窗要求，本文考虑的是软时间窗；

⑩支持物联网技术的应用，考虑配送过程中物联网技术的使用成本。

本文目标函数为所考虑的六部分成本，即固定成本、运输成本、制冷成本、惩罚成本、货损成本、物联网使用成本之和，构建模型如下。

目标函数：

minC=f1∑k=1kΖk+f2∑i=0n∑j=0n∑k=1mtijkxijk+χ∑i=0n∑j=0n∑k=1mQj(1-e-λ(tijk+uj))xijk+∑k=1m∑i=0n∑j=0n(f3xijkt∧ijk+f4yjkxi)+∑k=1m∑i=0n(f5max{ej-tjk,0}+f6max{tjk-li,0})+β(fw+fb∑k=1mΝk)qi         (1)" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">minC=f1∑k=1kZk+f2∑i=0n∑j=0n∑k=1mtkijxkij+χ∑i=0n∑j=0n∑k=1mQj(1−e−λ(tkij+uj))xkij+∑k=1m∑i=0n∑j=0n(f3xkijt∧kij+f4ykjxi)+∑k=1m∑i=0n(f5max{ej−tkj,0}+f6max{tkj−li,0})+β(fw+fb∑k=1mNk)qi         (1)$????=?{}_1{\displaystyle \sum _{?=1}^{?}?}{}_{?}+?{}_2{\displaystyle \sum _{?=0}^{?}{\displaystyle \sum _{?=0}^{?}{\displaystyle \sum _{?=1}^{?}?}}}{}_{??}^{?}?{}_{??}^{?}+?{\displaystyle \sum _{?=0}^{?}{\displaystyle \sum _{?=0}^{?}{\displaystyle \sum _{?=1}^{?}?}}}{}_{?}\left(1-?{}^{-?\left(?{}_{??}^{?}+?{}_{?}\right)}\right)?{}_{??}^{?}+{\displaystyle \sum _{?=1}^{?}{\displaystyle \sum _{?=0}^{?}{\displaystyle \sum _{?=0}^{?}\left(?{}_3?{}_{??}^{?}\stackrel{\wedge }{{\displaystyle ?}}{}_{??}^{?}+?{}_4?{}_{?}^{?}?{}_{?}\right)}}}+{\displaystyle \sum _{?=1}^{?}{\displaystyle \sum _{?=0}^{?}\left(?{}_5???\left\{?{}_{?}-?{}_{?}^{?},0\right\}+?{}_6???\left\{?{}_{?}^{?}-?{}_{?},0\right\}\right)}}+?\left(?{}_{?}+?{}_{?}{\displaystyle \sum _{?=1}^{?}?}{}_{?}\right)?{}_{?}(1)$

其中，t∧ijk=tijk+max{ej-tjk,0}" role="presentation" style="padding: 0px; margin: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">t∧kij=tkij+max{ej−tkj,0}$\stackrel{\wedge }{{\displaystyle ?}}{}_{??}^{?}=?{}_{??}^{?}+???\left\{?{}_{?}-?{}_{?}^{?},0\right\}$。

约束条件：

∑i=1nqiyik≤Qmax,k=1,2,3,⋯,k" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">∑i=1nqiyki≤Qmax,k=1,2,3,?,k${\displaystyle \sum _{?=1}^{?}?}{}_{?}?{}_{?}^{?}\le ?{}_{???},?=1,2,3,?,?$ (2)

∑k=1myik=1,i=1,2,3,⋯,n" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">∑k=1myki=1,i=1,2,3,?,n${\displaystyle \sum _{?=1}^{?}?}{}_{?}^{?}=1,?=1,2,3,?,?$ (3)

∑k=1my0k≤k" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">∑k=1myk0≤k${\displaystyle \sum _{?=1}^{?}?}{}_0^{?}\le ?$ (4)

∑i=1n∑k=1myik=n" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">∑i=1n∑k=1myki=n${\displaystyle \sum _{?=1}^{?}{\displaystyle \sum _{?=1}^{?}?}}{}_{?}^{?}=?$ (5)

∑j=1nx0jk=∑i=1nxi0k≤1,k=1,2,3,⋯,m" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">∑j=1nxk0j=∑i=1nxki0≤1,k=1,2,3,?,m${\displaystyle \sum _{?=1}^{?}?}{}_{0?}^{?}={\displaystyle \sum _{?=1}^{?}?}{}_{?0}^{?}\le 1,?=1,2,3,?,?$ (6)

xijk(max{tik,ei}+pi+tijk-tik)≤0" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">xkij(max{tki,ei}+pi+tkij−tki)≤0$?{}_{??}^{?}\left(\max \left\{?{}_{?}^{?},?{}_{?}\right\}+?{}_{?}+?{}_{??}^{?}-?{}_{?}^{?}\right)\le 0$ (7)

tik" role="presentation" style="padding: 0px; margin: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">ki${}_{?}^{?}$≤li,k=1,2,3,…,m; i=1,2,3,…,n (8)

遗传算法是计算数学中用于解决最优化的搜索算法[5,6],借鉴了自然界中“优胜劣汰，适者生存”的法则，是进化算法的一种。进化算法又包括遗传、突变、自然选择以及杂交等。鉴于遗传算法具有灵活性、可扩展性、群体搜索等特点，本文选择使用遗传算法对X公司冷链物流配送中心最优配送路径模型进行求解。

本文以配送中心和需求点的信息来进行编码。为避免车辆路径模型规划求解时出现无效解，本文在传统遗传算法的基础上采用整数编码的方式，整数编码可以有效的展现出路径优化所得出的车辆配送路线[7,8]。具体编码过程见表2。

种群数量的多少都会影响最优解的结果，若种群数量较多则运算时间较长，局部最优解难以得到。若种群数量较少，可能会导致染色体片段丢失，且最优解存在一定的偶然性。考虑以上因素，本文设定有100个初始种群。

遗传算法中个体遗传机会的大小取决于根据个体适应度的大小评定的各个个体的优劣程度。本文使用该函数来选取适应性高的个体作为新的群体并淘汰适应性低的群体。一般而言，适应度大所代表的个体在解决问题时表现更佳。对于个体i, 对应适应度f(i),适应度是zi,对应第i条染色体所求得目标值的倒数。则其被选中的概率Pi为：

Ρi=fi∑i=1nfi" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">Pi=fi∑ni=1fi$?{}_{?}=\frac{?{}_{?}}{{\displaystyle {\sum }_{?=1}^{?}?}{}_{?}}$

fi=1zii∈{1,2,⋯,popsize}" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">fi=1zii∈{1,2,?,popsize}$?{}_{?}=\frac{1}{?{}_{?}}\begin{array}{cc}& ?\in \left\{1,2,?,???????\right\}\end{array}$

借鉴了自然界中“优胜劣汰，适者生存”的法则，根据一定的规律或者方法对个体的适应度进行选择，从第t代群体Ρ(t)" role="presentation" style="padding: 0px; margin: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">P(t)$?\left(?\right)$中选择出一些适应度较好的个体遗传到Ρ(t+1)" role="presentation" style="padding: 0px; margin: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">P(t+1)$?\left(?+1\right)$中。本文采用轮盘赌基本思想[9],即适应度越高的解，越应该高概率地进行复制，且复制分数应该越多。

对群体P(t)内的个体进行随机搭配成对，以某一交叉概率交换每一对个体之间的部分染色体，依此产生新的染色体。本文采用匹配交叉的方式，传统遗传算法中Pc一般采用固定值，往往用之计算出的结果不具有实际意义，本文对Pc进行调整，公式如下：

pc=pmin+(pmax-pmin)×(G-g)G" role="presentation" style="padding: 0px; display: inline; line-height: normal; text-indent: 0px; text-align: left; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative; margin: 0px 30px !important;">pc=pmin+(pmax−pmin)×(G−g)G$?{}_{?}=?{}_{???}+\frac{\left(?{}_{???}-?{}_{???}\right)\times \left(?-?\right)}{?}$

Pmax——最大交叉概率，取值0.9;

Pmin——最小交叉概率，取值0.4;

G——最大迭代次；

g——前迭代次。

以某一变异概率将群体P(t)中个体的一个或部分基因值改变为其他的等位基因。本文为使得结果更加准确科学，将设定随机选择适应度低的后N/4个个体进行变异。

在遗传算法中，种群数量的取值范围为[10,500],交叉概率的取值范围为[0.4,0.9]。本文设定的算法终止条件为迭代次数达到最大迭代次数时即自行终止操作。具体参数设置如表3。

X公司冷链物流配送中心位于江苏省徐州市，主要提供生鲜农产品的配送业务。随着科技的发展以及人们生活质量的提高，该配送中心逐渐暴露出了配送路径规划不合理、应变措施不完善等问题，为了降低配送成本，提高顾客满意度，增强企业的市场竞争力，X公司决定对原有的配送路径进行优化。本文研究在物联网技术的支持下，X公司冷链物流配送中心的配送路径优化问题。

根据实地调研收集的数据，选取X公司某一天内需要提供配送服务的20个客户的数据进行分析，具体信息如表4所示，其中0代表配送中心。

为了便于位置信息在MATLAB软件中的表达，利用高德地图的坐标拾取功能，以配送中心为坐标原点建立平面直角坐标系，将配送中心及20个需求点的地理位置在MATLAB中用坐标表示，如图1所示。

通过实际调研，收集X公司冷链物流配送中心配送过程中的相关数据，对模型中涉及的参数进行取值，如表5所示。

通过查阅相关文献并结合本文模型算法中的参数信息[10],对遗传算法中涉及的相关参数进行分析取值，如表6所示。

本文选择使用MATLAB对车辆运输模型和遗传算法进行求解。将参数和所涉及到的数据代入MATLAB软件中运行，得到遗传算法迭代曲线如图2(b)所示，图2(a)是使用传统遗传算法得到的迭代曲线，对比发现，经过本文对遗传算法的改进，最优解出现在的迭代次数从原来的125次左右降低到86次左右。改进后配送方案路线如图3所示。

在满足车辆载额、配送中心、客户要求、时间限度等约束条件的基础上，可以得出配送该配送中心的配送成本如表7所示。

表8是将本文计算所得出的配送路线与传统遗传算法得出的配送路线成本进行对比。通过表8可以得出总成本减少了75.76元，相比原始方案优化了5.3%,车辆行驶距离少了12.84km, 相比原始方案优化了15.1%。即证明本文的VRP模型与遗传算法具有一定的参考意义。

本文针对生鲜农产品冷链物流配送路径优化问题，结合物联网技术，构建了冷链物流VRP模型，并对遗传算法进行研究与设计，利用改进的遗传算法对配送路径优化问题进行研究。以徐州市X公司冷链物流配送中心为例，选取该公司某天内需要提供配送服务的20个客户进行分析，利用MATLAB软件进行模型求解，对比传统遗传算法的求解结果与改进遗传算法的求解结果，得出改进后的遗传算法求解的配送路径距离更短、总成本更低，说明改进的算法具有可行性。对生鲜农产品冷链物流配送路径优化研究有一定的借鉴意义。