近年来，随着各界对易耗损产品质量重视程度的提升，我国冷链物流迅速发展. 在冷链物流市场中，生鲜食品是冷链物流的主体. 以果蔬、肉禽和水产为主的生鲜产品接近冷链物流商品总量的60%，是冷链物流运输中的绝对主体^[1]. 其中果蔬的刚性消费属性使得对果蔬的研究更具现实意义. 从家庭需要的频率和需求量来说，水果的需求量更多，研究发展冷链水果运输的必要性更强. 从水果生命周期来说，水果的生命周期略短于肉禽以及水产，这是由于随着时间的推动，水果的鲜活度逐渐下降，造成水果口感变差，而在顾客决策购买过程中，口感是购买水果的关键指标. 最后，水果品类繁多，配送地区地形各异，不同时节下对恒温冷藏要求较高，同时水果外部易破损. 据2018年数据显示，我国肉类、水产品和果蔬类农产品冷链腐损率分别为8%、10% 和15%^[2]. 基于水果易腐损的特性，冷链水果运输可以选择保温箱运输方式，减轻因碰撞和温度不恒定造成的腐损. 目前，我国冷链水果运输的发展水平不高，导致冷链水果运输成本消耗巨大. 与传统物流相比，冷链水果运输不仅要降低运输成本，而且对水果的品质要求更高. 由于消费者消费选择增多，顾客黏性降低，如何提高顾客满意度成为企业物流配送考虑的问题之一^[3]. 针对冷链运输中极易耗损的水果，如何在降低冷链水果运输成本的基础上增加顾客满意度，是冷链水果运输亟待解决的问题.

在构建顾客满意度模型方面，Yang等^[4-6]解决了硬时间窗下满意度问题. 对早到或迟到间隔施加惩罚系数，通过最小化惩罚成本提高顾客满意度. 韩亚娟等^[7]在前人基础上针对不同的间隔时间段，分别设置不同的惩罚系数. Zhang等^[8-10]引入模糊梯形函数表征软时间窗下顾客满意度：在顾客期望时间窗内到达，顾客满意度为最大；在期望时间点与最大容忍时间点内到达，顾客满意度随偏离期待时间窗的时间间隔呈线性递减函数. 梁承姬等^[11]在模糊梯度函数基础上，将顾客需求大小作为优先级构建满意度模型. 王娇^[12]改变现存论文中满意度与时间呈线性的假设，通过引入个体时间敏感性系数，构造体现个体满意度差异的非线性模型. 然而，现有求解软时间窗下顾客满意度的研究仍然较少，部分文献假设满意度与早到、迟到时间间隔呈线性递减关系；部分提出个体化差异的非线性满意度模型，不过体现个人差异的敏感性系数均为主观设定. 在实际情况下，顾客满意行为更加复杂，满意度感知可能在一定早到/迟到时间间隔下保持不变. 现有论文中基于模糊理论的线性求解满意度感知模型无法正确拟合现实情况，且无法估计早到、迟到对满意度的影响权值. 因此，本研究引入灰度白化权函数构建改进满意度模型. 通过调研获取顾客对于早到、迟到、耗损程度评价指标满意度等级感知节点；建立不同满意度等级的满意度分段函数；输出不同评价指标对满意度影响权值，旨在建立更加准确的顾客满意度模型.

路径规划问题是典型的组合优化问题，设计启发式算法可以在较短时间内获得优质解. 邓爱民等^[13]综合考虑软时间窗、车辆的固定成本、满载系数等条件，建立集配货一体化车辆路径问题数学模型. 采用模拟退火算法，结合线路内和线路间交换机制，并且增加算法记忆功能，最后依据双终止准则终止求解. 林清国^[14]系统性地比较了遗传算法和模拟退火算法的算法性能，根据2种算法设计过程中存在的弊端，提出糅合全局探索与局部优化的遗传模拟退火算法. 高志波等^[15]针对多车型、多目标带软时间窗路径优化问题，建立双层目标规划模型，上层求解车辆范围，下层利用自适应遗传模拟退火算法实现路径优化，通过与标准遗传算法的对比，验证了改进算法的有效性. Rabbani等^[16]以Pollution Routing Problem (PRP)为背景，以多车厢车辆为运输载体，满足顾客多种产品需求，探索不同速度、不同载重下，碳排放与燃油费用的变化幅度，分别采用标准遗传算法、模拟退火算法和混合遗传模拟退火算法进行算例分析，通过成本与计算时间综合评估算法性能. 以上遗传模拟退火算法以相等概率选择2个父代进行交叉运算，并根据模拟退火Metropolis准则决定子代构成. 现有论文中对父代的选择缺乏针对性，易造成随机交叉，破坏优秀基因，增加算法求解时间. 针对现有遗传模拟退火算法的不足，本研究提出改进遗传算法进行模型求解：定期针对“超级个体”进行局部模拟退火操作，以提高算法求解速率与求解质量；结合不同邻域搜索操作加强优秀基因搜索深度和跳出局优解的能力.

综合考虑软时间窗约束下，具有运输距离和运输载重限制的多目标冷链路径优化问题（vehicle routing problem with soft time window, VRPSTW）. 具体问题描述如下：冷链水果配送公司在前一天收集到所有零售商的需求信息、地理位置信息、时间窗信息、关于早到时间、迟到时间、货损程度的满意度分级信息等相关信息，规划第2天配送路径. 第2天运输车辆同时从配送中心出发，对多个零售商进行单一易损耗水果配送服务，配送方式采取泡沫保温箱方式，车辆完成配送任务后返回配送中心. 冷链水果运输决策过程大致如下：输入零售商相关信息，决策过程分别计算冷链水果运输各项成本以及零售商满意度评分函数，设置权值因子构造联合多目标优化模型，最后利用改进遗传算法提升算法求解性能，输出最优配送路径.

针对所探讨的问题作出如下假设：1）单一配送中心，配送中心的总水果量不小于所有零售商的需求量；2）配送中心的车辆数量是足够多的，且具有相同的性能及载货容量，每个零售商仅由一辆车经过，并且接受此车服务一次，所有零售商均能得到服务；3）运输线路上零售商的总需求量不超过单车的容量；4）每条配送路径长度不超过配送车辆一次配送的最大行驶距离；5）在冷链水果运输过程中能保持固定的运送温度，且配送时水果的腐败仅与运送时间有关；6）配送过程仅处理静止需求，不接受即时订单需求的补订.

定义一个完全对称网络图 ${{G}} = [N,A]$. $N$为所有节点的集合， $N = \{ 0,1,2,\cdots n\}$，0为配送中心， ${N'} = \{ 1,2,\cdots n\}$为零售商集合； $A$为路径集合， $A = \{ (i,j)|i,$ $ j \in N,i \ne j\} $，其他相关参数及说明如表1所示.

以成本最小化和满意度最大化为目标，通过对冷链水果运输进行建模求解.

冷链水果运输优化问题主要包括如下成本：车辆固定费用 ${C_1}$，车辆燃油耗费成本 ${C_2}$，制冷剂使用成本 ${C_3}$. 具体计算关系式如下：

(1) ${C_1} = \sum\limits_{k = 1}^\infty {\sum\limits_{j = 1}^n {{x_{0jk}}} } F,$

(2) $ {C}_{2}={\sum\limits _{k=1}^{\infty }{\sum\limits _{i=0}^{n}{\sum\limits _{j=0}^{n}{c}_{1}}}}{d}_{ij}(1+\rho {H}_{ijk}/{H}_{1})U{x}_{ijk},$

(3) ${C_3} = \sum\limits_{i = 1}^n {\sum\limits_{J = 1}^m {{u_{iJ}}} } {c_2}Q{s_J}{t_{ik}}\Delta \theta {R_1},$

(4) ${u_{iJ}} = \left\{ \begin{array}{l} {\rm{ }}\left\lfloor {{{{q_i}} / {{q^{{V_J}}}}}} \right\rfloor ,\;J{\rm{ = 1}} ;\\ \left\lfloor {{{\left( {{q_i} - \displaystyle\sum\limits_{j = 1}^{J - 1} {{u_{ij}}{q^{{V_J}}}} } \right)} / {{q^{{V_J}}}}}} \right\rfloor,\;J = 2,\cdots,m - 1 ; \\ \left\lceil {{{\left( {{q_i} - \displaystyle\sum\limits_{j = 1}^{J - 1} {{u_{ij}}{q^{{V_J}}}} } \right)} / {{q^{{V_J}}}}}} \right\rceil ,\;J = m .\\ \end{array} \right.$

式中：m为保温箱种类数. 式（1）为车辆总固定使用成本；式（2）中，单位距离燃料消耗量可以表示为依赖货车载货量的线性函数^[17]，以空车单位距离燃料消耗量 $U$为基础，每增加载货重量 ${H_1}$，单位距离燃料消耗率增加 $\;\rho $， ${H_1}$与 $\;\rho $为经验数据；式（3）为不同尺寸泡沫保温箱里制冷剂费用，与运输时间 ${t_{ik}}$、温差 $\Delta \theta $、传导系数 ${R_1}$、泡沫保温箱的表面积 ${s_J}$相关；式（4）计算零售商所需的每种保温箱数量，优先计算所需载重最大的保温箱数量，之后依次计算其他数量.

在冷链水果运输过程中，零售商（ $i \in {{{N}}'}$）满意度由到达时间和货损程度共同影响. 配送中心应用评分体系计算满意度大小.

早到或迟到的满意度评分分值设置如下：1) 当到达时间为 $[t_i^1,t_i^2]$时，零售商在时间维度上满意度最高且为10分；2）当到达时间为 $[{S_{1i}},t_i^1]$或 $[t_i^2,{S_{2i}}]$时，零售商满意度评分为高、中、低三级，其中高满意度评分为 ${{\rm{Le}}_1}$，中满意度评分为 ${{\rm{Le}}_2}$，低满意度评分为 ${{\rm{Le}}_3}$；3）若超出最大接受时间窗 $[{S_{1i}},{S_{2i}}]$，零售商在时间维度满意度评分为0.

同理，设置相同高、中、低三级评分体系 ${\rm{Le}}{_1}$、 ${\rm{Le}}{_2}$、 ${\rm{Le}}{_3}$衡量零售商对水果货损程度的满意度, 货损程度公式^[18]为

(5) ${\rm{Ls}}(i,k) = \int_0^{{t_{ik}} + {q_i}/(60{l_1})} {\alpha {{\rm{e}}^{\theta t}}} {\rm{d}}t;\;\;i \in {N'},k = 1,\cdots,\infty. $

通过白化权函数构造满意度模型. 白化权函数是在已有信息下对灰色朦胧集内部白化规律的数学表达，用来定量描述某指标值属于某灰类的程度^[19]. 由于提高零售商属于高满意度灰类的概率有利于增加零售商复订几率，利用灰度白化权函数分别计算不同早到、迟到时间以及货损程度属于高满意度等级的概率. 基于白化权函数的满意度计算逻辑如图1所示.

对于零售商（ $i \in {{{N}}'}$）， $f_i^1\left( {{x^1}} \right)$、 $f_i^2\left( {{x^2}} \right)$、 $f_i^3\left( {{x^3}} \right)$分别表示早到、迟到和货损程度分别处于各评价指标高满意度的概率，计算参考^[19-20]如下：

(6) $ f_i^z({x^z}) = \left\{ {\begin{array}{*{20}{l}} {1,}&\!\!\!\!\!\!{{x^z} \in (0,{\lambda ^z}(1));}\\ \!\!\!\!{\dfrac{{{\lambda ^z}(2) - {x^z}}}{{{\lambda ^z}(2) - {\lambda ^z}(1)}},}&\!\!\!\!\!\!{{x^z} \in \!\left[ {{\lambda ^z}(1),\!{\lambda ^z}(2)} \right],z\! =\! 1,2,3,i \in N'\!;\!}\\ {0,}&\!\!\!\!\!\!{{x^z} \in ({\lambda ^z}(2),\infty ).} \end{array}} \right.$

式中： ${x^z}$分别为早到、迟到和货损程度； $\{ {\lambda ^z}(1),{\lambda ^z}(2),$ ${\lambda ^z}(3)|z = 1,2,3\} $为阈值，由实地调研获取，表示零售商对于不同评价指标的满意度高、中、低等级感知临界值平均值.

对阈值进行无量纲化处理，避免评价指标量纲不同对满意度造成影响：

(7) ${w^z} = \frac{{{\lambda ^z}(1)}}{{{\lambda ^z}(1) + {\lambda ^z}(2) + {\lambda ^z}(3)}};\;{{ z = 1,2,3}}.$

利用 ${w^z}$构造 ${\vartheta _z} = \dfrac{{{w^z}}}{{{w^1} + {w^2} + {w^3}}}$，代表各个指标对于高满意度的影响权值.

综上所述，当车辆 $k$为零售商运输水果时，零售商 $i$的总满意度得分为

(8) ${\rm{Sa}}(i,k) = \left\{ \begin{array}{l} {\rm{L}}{{\rm{e}}_1}f_i^1\left( {t_i^1 - {t_{ik}} - {t_{0k}}} \right){\vartheta _1}{\rm{ + 10}}{\vartheta _2} + \\ \qquad{\rm{ L}}{{\rm{e}}_1}f_i^3({\rm{Ls}}(i,k)){\vartheta _3}{\rm{, }}\;{S_{1i}} \leqslant {t_{0k}} + {t_{ik}} < t_i^1;\\ 10{\vartheta _1} + {\rm{L}}{{\rm{e}}_1}f_i^2\left( {{t_{ik}} + {t_{0k}} - t_i^2} \right){\vartheta _2} + \\ \qquad{\rm{ L}}{{\rm{e}}_1}f_i^3({\rm{Ls}}(i,k)){\vartheta _3}{\rm{, }}\;t_i^2 < {t_{0k}} + {t_{ik}} \leqslant {S_{2i}};{\rm{ }}\\ 10{\vartheta _1} + 10{\vartheta _2} + \\ \qquad{\rm{ L}}{{\rm{e}}_1}f_i^3({\rm{Ls}}(i,k)){\vartheta _3}{\rm{, }}\;t_i^1 \leqslant {t_{0k}} + {t_{ik}} \leqslant t_i^2;{\rm{ }}\\ {\rm{L}}{{\rm{e}}_1}f_i^3({\rm{Ls}}(i,k)){\vartheta _3}{\rm{, }}\;{S_{1i}} - \psi \leqslant {t_{0k}} + {t_{ik}}{\rm{ < }}{S_{1i}}{\rm{, }}\\ \qquad{S_{2i}} \leqslant {t_{0k}} + {t_{ik}}{\rm{ < }}{S_{2i}}+\psi .{\rm{ }} \end{array} \right.$

式中： $\psi $为可接受不可行解的时间扩大边界. 在前3项结果中，第1部分为早到因素对零售商总满意度贡献值，第2部分为迟到因素贡献值，第3部分为货损程度贡献值. 其中，当零售商对某指标完全满意时，评分取10. 当到达时间超出最大容忍时间窗（ ${S_{1i}} - \psi $， ${S_{2i}} + \psi $）时，设置较大满意度惩罚项，使时间维度对于满意度贡献降为0.

为了降低成本，提高零售商满意度评分，建立混合整数规划模型（ ${\rm{M}}1$）：

(9) $ \min \;{{{Z}}_1} = {C_1} + {C_2} + {C_3}, $

(10) $\max \;{{{Z}}_2} = \sum\limits_{i = 1}^n {\sum\limits_{k = 1}^\infty {{\rm{Sa}}(i,k)} } .$

约束条件如下：

(11) $ \sum\limits_{j = 0}^n {{x_{ijk}}} = {y_{ik}};\;\;\;i \in {N'}, $

(12) $ \sum\limits_{i = 0}^n {{x_{ijk}}} = {y_{jk}};\;\;j \in {N'}, $

(13) $ \sum\limits_{i = 1}^n {{y_{ik}}} {q_i} \leqslant M;\;\;k = 1,\cdots ,\infty , $

(14) $\sum\limits_{k = 1}^\infty {{y_{ik}}} = 1;\;\;i \in {N'},$

(15) ${S_{1i}} \leqslant {t_{ik}} + {t_{0k}} \leqslant {S_{2i}};\;\;i \in {N'},$

(16) $\sum\limits_{j = 1}^n {{x_{0jk}}} = \sum\limits_{i = 1}^n {{x_{i0k}} \leqslant 1} ;\;\;k = 1,\cdots,\infty,$

(17) ${t_i} = {q_i}/(60{l_1});\;\;i \in {N'},$

(18) $\sum\limits_{i = 1}^n {{x_{ijk}}} \left( {{t_{ik}} + {t_i} + \frac{{{d_{ij}}}}{{{v_{ij}}}}} \right) = {t_{jk}};\;\;j \in {N'},k = 1,\cdots, \infty ,$

(19) $\sum\limits_{i = 0}^n {\sum\limits_{j = 0}^n {{x_{ijk}}} } {d_{ij}} \leqslant {M_1};\;k = 1,\cdots,\infty,$

(20) $ {x}_{ijk}=\left\{ \begin{array}{l}1,\;{\text{车辆}}k{\text{依次服务零售商}}i{\text{、}}j;\\ 0,\;{\text{其他}}.\end{array} \right.$

(21) $ {y}_{ik}=\left\{ \begin{array}{l}1,\;{\text{车辆}}k{\text{服务零售商}}i;\\ 0,\;{\text{其他}}.\end{array} \right.$

式（9）最小化运输成本；式（10）最大化零售商满意度评分；式（11）、（12）限制零售商流入和流出；式（13）限制车辆载重；式（14）表示每个零售商只能由一辆车进行服务；式（15）给出最大接受时间窗；式（16）限制配送车辆均从配送中心出发，送货结束后返回配送中心；式（17）计算在零售商 $i$处的服务时间；式（18）表示车辆 $k$到达零售商 $j$所消耗的时间；式（19）限制驾驶员单次行驶距离；式（20）为车辆配送水果的顺序；式（21）表示车辆 $k$服务零售商的集合.

兼顾企业的经济性和服务水平需求，采用权值法整合成本与零售商满意度关系. 结合权值因子 ${\zeta _1}$和 ${\zeta _2}$（ ${\zeta _1} + {\zeta _2} = 1.0,{\zeta _1} \geqslant 0,{\zeta _2} \geqslant 0$），针对不同配送方案，最大化联合决策目标得到如下模型（ ${\rm{M}}2$）：

(22) $\mathop {\max }\limits_{j \in I}\; {Z^j} = {\zeta _1}\left( {\mathop {\min }\limits_{i \in I} \;Z_1^i} \right)/Z_1^j + {\zeta _2}Z_2^j/\left( {\mathop {\max }\limits_{i \in I}\; Z_2^i} \right).$

式中： $I$为不同配送方案集合， $Z_1^j$为不同配送方案成本， $Z_2^j$为不同配送方案的零售商满意度评分. 式（22）将不同维度双目标值（即成本和满意度）转化到0~1.0，并进行加权求和，从而形成同维度单目标问题^[21]. 当方案 $j$的成本越接近所有方案的最小成本时， $\left( {\mathop {\min }\limits_{i \in I} Z_1^i} \right)/Z_1^j$越大并趋近于1.0；当方案 $j$的满意度越接近于所有方案的最大满意度时， $Z_2^j/(\mathop {\max }\limits_{i \in I} Z_2^i)$越大并趋近于1.0.

传统路径规划问题为NP-hard问题^[22]，本研究针对软时间窗下的多目标路径规划问题VRPSTW，求解更为复杂. 目前解决多目标路径规划问题（vehicle routing problem. VRP）最常用的求解方法包括2种：精确算法和启发式算法. 精确算法适用于解决规模较小的线性规划问题，而启发式算法能够在较短时间内获得大规模非线性问题的较优解. 基于模型（M2）非线性的特性，设计改进遗传算法对模型进行求解.

遗传算法是通用搜索算法，是使用受自然种群遗传学启发的原理来发展问题的解决方案^[23]，适用于求解全局优化问题，具有较强的全局寻优能力，但易于陷入局部解；模拟退火算子模仿固体的退火过程，随着温度参数的不断下降，算法中的解趋于稳定. 模拟退火算子会以一定的概率跳出过程中的稳定解，以寻找目标函数的全局最优解.

综合借鉴2种算法的思路，以遗传算法作为主体算法，对“超级个体^[24]”引入模拟退火思想，以一定概率接受劣解，避免种群快速收敛至局部解. 在迭代过程中，充分利用优质解的寻优思想，采用邻域搜索生成邻域解，取高适应度的邻域解取代种群中数量冗余的染色体；为了有效跳出局部解，通过差异化思想搜索异于最优解的其他染色体的邻域解，更新当前收敛解.

算法中染色体采用自然数编码，配送中心用0表示，其他自然数表示零售商，其中相邻2个0之间的部分构成一条行驶线路，多条行驶路线构成一条染色体. 定义同时满足车辆载重和最大路长限制，但超出最大容忍时间窗的路径所在的染色体为不可行解. 借鉴Gendreau等^[25]的思想，构造有限地接受不可行解的机制，以便通过不可行解的过渡，搜索到更好的可行解，从而提升算法的全局寻优能力. 在设计接受不可行解的机制时，对每一个零售商的最大容忍时间上、下限扩大时间段 $\psi $，即种群接受到达时间处于 $[{S_{1i}} - \psi ,{S_{1i}}]$或 $[{S_{2i}},{S_{2i}} + \psi ]$的不可行解. 同时为了降低不可行解质量，使时间维度对满意度的贡献降为0.

采用随机方式生成初始解，即随机生成客户点 1,2,··· ,n的一个排列，在满足车辆载重、最大路长与扩大的时间窗的条件下，按照此排列顺序将客户点依次加入车辆线路中，当不满足任意一个条件时，开启一条新的车辆线路.

采用 $\mathop {{F^j}}\limits_{j \in I} = {{{Z^j}} \left/{ {\displaystyle\sum\limits_{i \in I} {{Z^i}} }}\right.}$构造染色体适应度，其中 ${Z^j} = {\zeta _1}\left( {\mathop {\min }\limits_{i \in I}\; Z_1^i} \right)\left/{Z_1^j + {\zeta _2}Z_2^j}\right.\left/{\left( {\mathop {\max }\limits_{i \in I} \;Z_2^i} \right)}\right.$. 由公式可知，解的成本越低，满意度越高，解的适应度越强. 同时，采用轮盘赌选择方法，其基本思想是群体中个体被选中的概率与其适应度大小成正比，保证种群朝着适应度更高的解空间转移.

在种群迭代过程中，超级个体的出现极易主导种群进化方向，使遗传算法快速陷入局优；同时模拟遗传退火算法随机选择父代进行模拟退火操作，以一定概率接受差解进入新种群，但是随机选择容易造成前期解的质量偏差，需要较长时间过渡到优质解，因此跳出超级个体，寻找更优解的速度变慢. 为了更好地解决超级个体问题，针对“超级个体”引入模拟退火操作. 局部模拟退火交叉具体如下：若本代适应度最高的2种染色体数量均超出 ${N_1}$，则选择此2种染色体为父代，对染色体中非零基因进行交叉操作；若本代适应度最高的2种染色体中任意一个数量超出 ${N_1}$，则选择数量较多的染色体与随机染色体为父代，对染色体中非零基因进行交叉操作. 2种情况下均须考虑限制条件生成新的配送方案，若生成不可行解，重新选择交叉位置进行交叉操作，并按照Metropolis准则决定新种群构成. 当本代适应度最高的2种染色体数量均不超出 ${N_1}$，直接跳出本次退火交叉.

本研究交叉操作分成普通交叉与局部模拟退火交叉，交叉算子采用改进Order Crossover (OX)，在一定程度上避免生成与父代相同的子代. 如图2所示为改进OX交叉算子. 兼顾求解速度需求，每隔L代判定是否对超级个体进行局部模拟退火交叉. 在进行局部模拟退火交叉时，依据Metropolis准则更新超级个体子染色体群，增加种群多样性，加快种群更新概率，减缓整体优质染色体被破环程度，防止超级个体染色体群垄断当前种群的进化方向，较快得到优质解.

变异操作为随机选择父代染色体中任意2个非零基因，将2个基因位及其之间的基因进行倒转，考虑限制条件生成新的配送方案，对于生成的不可行解，重新选择变异位置直至达到接受解，并依据适应度大小更新当前种群.

为了利用全体染色体信息，迭代采用邻域搜索生成邻域解，邻域搜索是一种高效寻优的搜索方法，文章选用2-opt^[26]，or-opt^[27]，1-1 interchange^[28] 3种方式，每次随机选择一种邻域搜索方式进行邻域搜索得到邻域解.

2-opt的操作过程如下：随机选择一条染色体的一条行驶路线，选择路线上任意2点非零基因，翻转2点基因之间的所有基因，并通过限制条件生成新的配送路线；or-opt的操作过程如下：随机选择一条染色体的2条行驶路线，将一条路线的一个非零基因位插入另一条路线中，并考虑限制条件生成新的染色体；1-1 interchange的操作过程如下：随机选择一条染色体的2条行驶路线，将2条路线上的非零基因进行位置互换，并考虑限制条件合并生成新的染色体. 若在邻域搜索过程中生成不可行解，则须重新选择基因点直至生成接受解.

本研究邻域搜索应用在两方面. 1）利用最优染色体信息. 在迭代过程中，防止某染色体数量冗余主导进化方向，同时利用优秀基因信息，须间隔 ${L_1}$代检测相同染色体数量. 当检测到某染色体数量大于一定阈值时，对目前种群最优解进行邻域搜索，记录邻域搜索优质解，根据适应度大小更新当前种群中数量冗余的染色体，避免种群快速收敛. 2）利用非最优染色体信息. 若种群的最优解连续 ${A'}$代不变，判定迭代陷入局部解. 为了增加算法跳出局部解能力，寻找新的解空间，对当前种群中异于最优解的其他染色体进行邻域搜索，根据当前最优解与所有邻域解适应度大小，进而判断能否更新当前最优解.

结合上述算法改进，所设计的改进遗传算法流程如下：1）参数初始化设置. 如种群规模 ${P_{\rm{s}}}$，交叉概率 ${P_{\rm{c}}}$，变异概率 ${P_{\rm{m}}}$，终止代数 ${m_{\rm{g}}}$，初始温度 ${\theta _0}$，温度下降比例 ${T_{\rm{m}}}$，超级个体阈值 ${N_1}$，局部退火间隔代数 $L$，更新种群间隔代数 ${L_1}$，最优解连续阈值A′，时间扩大间隔 $\psi $，当前代数i=0，最优解连续不变代数A=1. 2）生成初始种群并记录当代最优解. 采用自然数编码方式，根据距离约束、载重约束并适当放松时间约束随机生成一组初始解. 3）选择操作. 通过轮盘赌算法选择当代种群. 4）混合交叉算子分为普通交叉、局部模拟退火交叉. 当i为L倍数（即 $i{\text{%}}L = 0$）且超级个体数量大于N₁时，针对超级个体群进行模拟退火交叉，根据Metropolis准则生成新种群，否则对种群进行普通交叉；当i为L₁倍数（即 $i{\text{%}} {L_1} = 0$）时，执行步骤5），否则执行步骤6）. 5）对目前最优解进行随机一种邻域搜索，以邻域空间内优质解更新当代种群. 6）对i代种群进行变异操作，得到i代子代种群. 比较i代和i代子代最优染色体，若i代子代最优染色体不优于i代最优染色体，则将i代最优染色体替换i代子代种群适应度最低的染色体. 7）执行 $i = i + 1$,并且更新温度 $\theta_1 = {\theta _0}T_m^{i + 1}$. 8）i代与 $i - 1$代最优染色体相同，则A=A+1，否则 $A = 1$. 当A>A′时，调用随机邻域算法搜索当代异于最优解的染色体，更新种群以跳出局部优解. 9）重复步骤3）~8）直到设置的循环次数 $i = {m_{\rm{g}}}$，选择m_g代最优染色体作为最优解.

改进算法流程图如图3所示.

为了验证所提出的改进遗传算法有效性和可行性，利用算法解决上海市某批发中心对闵行区35家水果店的水果冷链运输优化问题；同时，针对关键参数的变化设计可行性分析，与传统遗传和遗传模拟退火算法进行结果比对. 为了保证解的稳定性，每一次结果均为各算法运行20次结果的平均值.

通过资料查阅与实地调研，获取零售商位置相对坐标 $(X,Y)$与各路段运行的平均速度. 向闵行区水果零售商发放问卷. 问卷设定高、中、低满意度评分为 ${{\rm{Le}}_1} = 9.5$、 ${{\rm{Le}}_2} = 8.0$、 ${{\rm{Le}}_3} = 6.0$，获取零售商对配送早到、迟到时间以及耗损程度的满意度信息. 商家储藏模式为早到产品可以直接放入冷藏柜，故忽略早到因素对满意度的影响，以*代表不在意早到时间的影响，现有时间窗由 $[t_i^1,t_i^2,{S_{2i}}]$ 表示. 计算迟到时间、耗损程度高、中、低满意度感知平均临界值分别为 $[17,37,63]$ min、 $[0.028,0.120,0.240]$. 配送点的基本零售商信息如表2所示. 运输过程中保温箱种类m=4，参数如表3所示.

改进遗传算法及相关参数设置如下： ${P_{\rm{s}}}$=50， ${m_{\rm{g}}}$=1500， ${P_{\rm{c}}}$=0.75， ${P_{\rm{m}}}$=0.1，θ₀=100 °C， ${T_{\rm{m}}}$=99%，N₁=4，L=3，L₁=30，A′= 50， $M = 1\;200\;{\rm{ kg}}$， $U = 0.056\;{\rm{ L}} / {\rm{km}}$， $V \!= \!3.23 \times 1.96 \times 2.1\;{{\rm{m}}^3}$， ${c_1} \!=\! 6$ 元/ ${{\rm{L}}}$， ${c_2} \!= \! 1.2$ 元/ $ {\rm{kg}}$， $\Delta \theta \!\!=\! 20 $ °C, ${R_1} \!=\! 0.1$， $Q = 0.06$ ${\rm{kg}}/ {({{\rm{m}}^2} \cdot {\rm{h}} \cdot {\text{°C}})}$， ${M_1} = 150\;{\rm{ km}}$， ${t_{0k}} = 8$， ${l_1}\! = \!16\;{\rm{kg}} / {\min }$， $\rho = 0.05$， ${H_1} = 200\;{\rm{ kg}}$， ${\zeta _1} = 0.8$， ${\zeta _2} = 0.2$， $\psi = 0.5\;{\rm{h}}$. 配送中心坐标为（20，20）.

分别运用改进遗传(improved genetic algorithm，IGA)，传统遗传(genetic algorithm，GA)和模拟退火遗传算法(simulated annealing genetic algorithm, GA-SA)，针对上述实例进行求解，求解环境为matlab R2018a. 3种算法求解结果如表4所示. 表中， ${\rm{Im}}1 = (Z_1^{{\rm{GA}} - {\rm{SA}}} - Z_1^{{\rm{IGA}}})/Z_1^{{\rm{IGA}}}$（或 $(Z_1^{{\rm{GA}}}{\rm{ \!- \!}}Z_1^{{\rm{IGA}}})/Z_1^{{\rm{IGA}}}$）， ${\rm{Im}}2 = (Z_2^{{\rm{GA}} - {\rm{SA}}}{\rm{ - }}Z_2^{{\rm{IGA}}})/Z_2^{{\rm{IGA}}}$（或 $(Z_2^{{\rm{GA}}}-{Z_2})/{Z_2}$）分别为本研究提出的算法与其他算法在成本与满意度上的改进程度. 可以看出，本研究所提出的改进算法在双目标上均优于其他算法. 改进遗传算法得到的路径配送关系如图4所示.

为了验证改进遗传算法在不同参数下的适应性以及不同参数对结果的影响，设计参数范围如下：卸货率为10~20 kg/min，N′=0~80. 考虑货物卸载率和零售商人数对生鲜农产品冷链配送路径优化的影响.

选取12组数值算例，命名为Vxy, 其中x为零售商人数，y为货物卸货率. 在3.1节基本案例取值基础上，应用3种算法. 零售商人数为30、35、40、50，货物卸载率为10、14、16 kg/min，进行组合求解. 当零售商人数>35时，零售商需求、零售商位置坐标、零售商时间窗、行驶速度均随机生成，其中 $ {q}_{i}\sim 100+U(\rm{0},\rm{200})$， $X,Y\sim U(0,40)$， $t_i^1\sim {t_{0k}} + U(0,2)$， $t_i^2\sim t_i^1 + U(0.5,4)$， ${S_{2i}}\sim t_i^2 + U(0,2)$， ${v_{ij}}\sim 20 + U(0,20)$. 如表5所示为3种算法收敛结果.

可以看出，改进遗传算法在成本和满意度上均表现最优. 在冷链水果配送中，服务时间的大小影响决策结果，因此须重点考虑卸货率. 随着卸货率l₁变小，服务时间增多，成本趋势变大，满意度趋势变少，总体趋势变差，原因在于服务时间过大，占用正常配送时间，造成部分调度方案超出时间窗的范围. 若时间窗较大，则存在临界卸货率 $l_1'$，当 ${l_1} \geqslant l_1'$时，成本与满意度值优化幅度减缓，根据卸货效率和结果均衡考虑，选择较优卸货率范围. 随着零售商人数增加，改进遗传算法优势更明显，如图5所示. 图中，Ratio为改进比例，是表5中相同人数算例下Im1或Im2的平均值，KK1为模拟退火遗传算法成本减少比例，KK2为模拟退火遗传算法满意度增加比例，KK3为传统遗传算法成本减少比例，KK4为传统遗传算法满意度增加比例. 与其他算法相比，使用改进遗传算法得到的双目标提升比例随着人数增多总体呈现上升趋势.

传统模拟退火遗传算法因其以一定概率接受劣解，随机性较强，算法收敛慢；传统遗传算法极易陷入局优，无法得到优质解. 如表6所示为不同卸货率下，3种算法平均收敛代数O₁及收敛时间O₂，从2个维度综合考虑，证明改进遗传算法能够较快得到更优解.

针对冷链水果运输重点关注的满意度方面，提出灰度白化权函数替代现有论文中满意度线性递减函数. 基于实地问卷调查得到影响满意度指标：晚到时间和耗损程度的高中低满意度等级感知临界值建立灰度白化权函数. 为了高效求解模型，设计改进遗传算法，通过对“超级个体”引入模拟退火的Metropolis准则，随机选择3种邻域搜索之一定期更新染色体群加强算法求解能力. 通过实际案例以及数值实验验证了算法的有效性，且随着服务人数增加，改进遗传算法优势更明显.

在配送过程中，服务时间的大小影响决策结果，随着卸货率l₁变小，服务时间增多，成本趋势变大，满意度趋势变少，总体趋势变差，由于占用正常配送时间. 若时间窗较大，则存在临界卸货率 $l_1' $，当 ${l_1} \geqslant l_1'$时，成本与满意度值优化幅度减缓，可以得到适合的卸货率范围.

总体来说，本研究为冷链水果物流的配送关注品质特性以及配送方案的设计提供了新的思路. 但是依然存在不足，譬如目前冷链配送过程中产生的环境污染问题，以及目前建立模型假设需求静止，不能适应实际配送过程中的动态变化.

针对以上不足，未来研究将分为2个部分：增强企业环保意识，深入研究绿色物流，将环保因素加入模型中；实际运输过程中卸货时间、顾客需求均为变量，须考虑它们的随机性，增强算法求解配送路径优化的动态调节能力.