唐志强，李 锐
辽宁工业大学 电子与信息工程学院，辽宁 锦州 121001
在现代物流配送系统的构建中，如何构建高效、绿色、可靠的配送网络来降低物流成本，减少环境污染和提高安全性对于物流系统可持续发展至关重要。合理的配送中心选址和车辆路径规划对于物流配送系统的有效运作和降低物流成本具有重要作用。由于单独考虑选址问题和车辆路径问题都很难达到全局优化的效果，而集成的选址-路径规划问题（LRP）同时包括战略和战术层面，能够实现整体优化。目前，国内外学者对LRP问题进行了广泛的研究。
近年来，随着环境污染的加剧，一种“低能耗、低排放”的绿色物流受到了广泛的关注。Dukkanci等[1]首次将低碳路径与低碳选址相结合，提出了最小化碳排放的选址-路径问题模型；
Toro等[2]研究了多目标绿色选址-路径问题，建立了最小化燃油消耗及总成本的多目标混合整数线性规划模型；
Wang等[3]研究了绿色、带时间窗的取货和派送两阶段选址-路径问题，并设计一个基于拉格朗日松弛的启发式算法来求解模型；
赵燕伟等[4]提出了一种综合考虑多车型和同时取送货的低碳选址-路径问题，并构建三维指数混合整数规划模型，同时设计一种进化式超启发式算法进行求解；
Zhang等[5]研究了带时间窗的时间依赖绿色选址路径问题，并设计了一种两级超启发式算法进行求解。
在现实世界中，客户的需求可能是模糊的或者不确定。Nadizadeh等[6]于2013年首次提出建立需求不确定的选址-路径问题模型并对其进行求解；
Ghaffari-Nasab等[7]研究了模糊选址路径问题，并设计了一种混合模拟退火算法进行求解；
Nadizadeh等[8]应用蚂蚁算法求解能力受限和模糊需求的选址-路径问题；
Pekel等[9]设计一种结合可变邻域搜索和进化局部搜索的启发式搜索算法，解决了模糊需求的选址-路径问题。
在实际的物流配送过程中，由于供求关系和外部环境因素的影响，客户需求、配送中心和运输路径的可靠性在各个运营周期可能不同，因此考虑多周期选址路径问题更符合现实。Wang等[10]针对两级多周期选址路径问题，建立了一个最小化总成本和车辆数量的多目标LRP模型，并设计了一种两阶段混合算法来求解；
Cheng等[11]在灾后垃圾清理任务中引入了多周期双梯度选址-路径问题，建立了最小化成本和清理时间的LRP模型，并用改进的遗传算法进行求解；
Saffarian等[12]针对灾后救助工作，考虑了一个包含灾害管理周期的多目标LRP模型，同时使用全局性准则方法将其转化为单目标进行求解。
总的来说，目前关于LRP问题的研究已经取得了大量的成果。与现有的研究相比，本文在LRP问题的研究中同时考虑了不确定、可靠性、多周期和绿色四个因素，并基于模糊可信度理论建立了问题模型。此外，本文对基本的遗传算法进行了改进，设计了一种混合遗传算法HGA，实验表明该算法能在有限的时间内提供较优的结果。
物流配送网络如图1所示，包括候选配送中心、运输车辆、客户和运输线路。运输车辆从配送中心出发，按照规划的配送线路依次服务该线路上的所有客户，最后返回对应的配送中心。
图1 物流配送网络Fig.1 Logistics distribution network
模型假设条件如下：
（1）候选配送中心的数量、位置、开设成本、运营成本、能力及其在各个周期的可靠性已知；
（2）车辆的数量、固定运营成本、运输能力、单位距离运输成本和单位距离折旧成本已知，并且每辆车只能从一个配送中心出发，最终回到该配送中心；
（3）客户的数量、位置和需求已知，并考虑需求为模糊变量；
（4）每个客户的需求最多由一辆车服务一次；
（5）任意两点之间的距离及其在各个周期的可靠性已知；
（6）单位燃油成本已知。
考虑模糊需求的多周期可靠性绿色LRP问题是指通过开设配送中心和规划各个周期的车辆运输路径来最小化物流配送成本和燃油消耗成本，同时满足各周期内车辆运输路径的可靠性及模糊需求约束。
1.1 符号说明
模型符号定义如下：I表示候选配送中心集合，J表示客户集合，K表示车辆集合，T表示周期集合。OCi、MCi、Ui和Rti分别表示配送中心i∈I的开设成本、运营成本、能力及其在周期t∈T的可靠性；
Hk、Pk、TCk和DCk分别表示车辆k∈K的固定运营成本、运输能力、单位距离运输成本和单位距离折旧成本；
Dsl和rstl分别表示任意两点s∈M和l∈M之间的距离及其在周期t∈T的可靠性，M=I⋃J；
表示客户j∈J在周期t∈T的 需 求，且为 三 角 模 糊 数Fuel表示单位燃油成本。
决策变量定义如下：xtslk∈{0,1}，如果周期t∈T车辆k∈K从s∈M到l∈M，则xtslk取值为1，否则取值为0；
yitk∈{0,1}，如果周期t∈T车辆k∈K分配给配送中心i∈I，则yitk取1，否则yitk取0；
zi∈{0,1}，如果配送中心i∈I开设，则zi取值为1，否则zi为0。
引入如下辅助变量：f stlk≥0表示在周期t∈T车辆k∈K在点s∈M和点l∈M之间的运输量。
1.2 优化模型
基于以上符号和变量的定义，建立考虑模糊需求的多周期绿色选址-路径问题模型如下：
目标函数（1）为最小化总成本，包括配送中心的开设成本及各个周期内配送中心的运营成本、车辆的固定运营成本、车辆的运输成本、燃油消耗成本；
其中，Fstlk表示周期t车辆k在点i和点j之间的运输油耗，计算详见1.3节；
式（2）为车辆路径的可靠性约束，γ表示要求的可靠性水平；
式（3）表示每个周期内车辆与配送中心的分配关系；
约束（4）表示未开设的配送中心在各个周期内都没有车辆驶出；
约束（5）表示开设的配送中心必须有车辆驶出；
式（6）表示在每个周期内每辆车从一个点驶入，必须要从该点驶出；
式（7）避免客户之间形成子环路；
式（8）保证配送中心之间没有车辆路径；
式（9）表示在每个周期内每辆车辆至多服务于一个配送中心；
式（10）表示在每个周期内每个客户最多只能由一辆车服务；
式（11）表示在每个周期内车辆能力的机会约束，α1表示要求的置信水平；
式（12）表示每个周期内配送中心能力的机会约束，α2表示要求的置信水平；
式（13）和（14）保证客户点两端的流量平衡；
式（15）~（17）为二值变量约束；
式（18）为产品运输量的非负约束。
1.3 油耗计算
车辆在运输过程中，装载量和行驶距离等因素都会影响燃油消耗。本文采用文献[13]的方法来计算油耗，运输车辆的燃油消耗量F可按照式（19）进行计算：
其中，G为道路坡度因子；
D为车辆的行驶距离；
f为载货量；
a和b分别为燃油消耗参数。
基于以上油耗计算方法，周期t内车辆k在点s∈M和点l∈M之间的油耗为：
据此，燃油消耗成本可按如下计算：
当xtslk=1，∀s∈M,∀l∈J,∀k∈K,∀t∈T时，表示周期t内的车辆k经过s和l之间线路，由约束（6）可得，根据文献[14]则有：
对于∀s∈I,∀l∈J,∀k∈K,∀t∈T，当xtslk=1时，根据式（7）可推出，则有：
莫莉在克里斯蒂娜不提防时向她的侧身踢了一脚，克里斯蒂娜后背着地瘫在那里。看到这儿，艾尔突然松开手，把我拉到他身边紧紧地靠着。我咬紧牙不想哭出来。第一天晚上，虽然我对艾尔的哭泣无动于衷，但我还不是铁石心肠的人。此时此刻，看着克里斯蒂娜痛苦地捂着胸肋，我真想冲上去挡在她们中间。
1.4 模糊机会约束的清晰化
由于经典LRP问题是NP-hard问题，而考虑模糊需求的多周期绿色选址-路径问题是经典LRP问题的扩展问题，也属于NP-hard问题，因此设计启发式算法对该问题进行求解。
遗传算法（GA）作为经典的启发式算法，已经在组合优化领域取得了较好的成果。本文采用整数编码，针对本文问题的特点，设计了一种混合进化算法HGA进行求解。在该算法中，优化了交叉算子和设计了两阶段变异操作，提高了算法的搜索能力。
2.1 算法的主要步骤
HGA算法的主要步骤如下：
步骤1按照2.2节中编码方法随机初始化种群；
步骤2对个体进行解码，并计算个体适应值（详见2.2）；
步骤3更新全局最优解；
步骤4判断是否满足终止条件，如果满足，输出最优解并结束运行，否则，继续运行；
步骤5基于轮盘赌选择法进行选择操作；
步骤7个体变异（详见2.4节），然后返回步骤2。
算法的具体流程如图2所示。
图2 算法流程图Fig.2 Algorithm flowchart
2.2 个体的编码与解码
本文采用整数向量对个体进行编码。向量由三个部分组成，第一部分表示客户的服务顺序，第二部分表示客户所属的车辆，第三部分表示车辆所属的配送中心。假设当前有5个客户、3辆车和2个配送中心，则编码如图3所示。
图3 个体编码Fig.3 Individual code
在图3中，根据第二部分可知，客户1和4由车辆1服务，客户2和3由车辆2服务，客户5由车辆3服务。由第三部分知车辆1和2属于配送中心1，车辆3属于配送中心2，再结合第一部分客户的服务顺序即可确定所有每辆车的行驶路径。
对于解码得到的车辆路径，首先检测是否满足本文问题模型中的所有约束条件，如果不满足，则无需通过式（1）计算最终结果，直接设为一个极大值，否则通过式（1）计算最终的成本。
2.3 交叉操作
采用部分映射交叉方法，个体通过与全局最优个体交叉来更新。如图4所示，首先在编码的每个部分都选择两个交叉位置，然后将个体与全局最优解交叉得到新个体。
图4 交叉操作Fig.4 Cross operation
在遗传算法早期阶段，交叉概率较小，可以提高全局搜索能力；
在后期阶段，交叉概率较大，可以提高局部搜索能力，本文采用以下方法优化交叉算子。
其中，Pc表示交叉概率；
Gen和MAXGEN分别表示当前迭代次数和最大迭代次数；
Pcmin和Pcmax分别表示最小交叉概率和最大交叉概率。
2.4 变异操作
变异操作分为两个阶段，低概率的变异操作1用于保持种群的多样性，高频率的变异操作2用于扩展算法的搜索空间。变异方法1采用个体内部两位互换方法。如图5所示，在编码的每个部分都随机选择两个变异位置，然后把这两个变异位置的值互换。
图5 变异操作1Fig.5 Mutation operation 1
变异操作2如图6所示。在编码的第一部分，采用个体内部两位互换的方法，在编码的第二部分随机地选取一个位置，然后在1到最大车辆数量之间随机地获取一个整数来替换该位置的数值，编码的第三部分更新操作与第二部分更新类似。
图6 变异操作2Fig.6 Mutation operation 2
为了验证模型的合理性和HGA算法的有效性，对随机产生的不同规模的算例进行测试。所有算法均采用Matlab编程实现，且实验环境为AMD Core i5 2.4 GHz CPU，内存16 GB RAM，操作系统Windows 10。
3.1 参数设置
表1给出不同算例的规模，包括配送中心的数量、客户数量、车辆数量和周期数量。算例的参数设置如下：配送中心的坐标和客户点的坐标均在[−100，100]之间随机生成；
车辆的运输能力Pk为900，固定运营成本Hk取值为1 200，每公里折旧成本DCk为0.28，单位距离运输成本TCk为1；
配送中心的能力Ui为[2 000，3 000]之间的随机值，开设成本OCi取值范围为[10 000，15 000]、运营成本MCi取值范围为[4 000，6 000]，在各个周期的可靠性Rti为[0.9，1]之间的随机值；
客户的需求，其中p1tj在[100，120]之间随机取值，在[120，140]之间随机取值，p3t j在[140，160]之间随机取值；
任意两点之间线路在各个周期的可靠性ritj为[0.9，1]之间的随机值；
单位燃油成本Fuel取值为7.99；
道路坡度因子G取值为1；
燃油消耗系数和b分别取值为0.006 208和0.212 5[13]。种群数量为20，迭代次数为300。
表1 算例规模Table 1 Case scale
3.2 算法性能分析
为了验证HGA算法的有效性，对算例I1~I5进行求解，并将结果与标准GA算法以及优化DE算法[15]进行比较。对于所有算例，置信水平α1和α2设置为0.5，可靠性水平γ设置为0.3。其中，HGA算法的参数设置为交叉概率最大值0.9、最小值0.1，变异概率为0.05、0.9；
GA算法的参数设置为交叉概率0.9、变异概率0.05；
DE算法的参数设置为参照文献[15]。
对于每个算例，每种算法分别运行10次。表2给出几种算法求解的最优值、最差值、平均值、平均偏差率及平均CPU时间的比较。由表2可见，对于不同规模的算例，HGA算法的最优值、平均值、最差值、平均偏差率和运行时间均优于GA算法和优化DE算法。其中，从平均偏差率来看，HGA算法的变化范围为0.045 4~0.096 1，而GA算法为0.384 4~0.604 5，DE算法为0.2~0.313 0，可见HGA算法的平均偏差率明显优于其他算法。综上可见，HGA算法能够对不同规模问题有效求解。
表2 不同规模算例下HGA与GA、DE结果对比Table 2 Comparison of results of HGA，GA and DE under different scale calculation examples
为了验证置信水平α1和α2以及可靠性水平γ对算法性能和求解结果的影响，对算例I3进行测试。其中，α1和α2在0.1~0.95范围内取值，γ在0.1~0.7范围内取值。对于不同置信和可靠性取值，每种算法分别求解10次。表3给出不同置信水平和可靠性下几种算法性能的比较。由表中数据可知，对于不同可靠性水平和置信水平，HGA算法仍然能保持稳定，并且求解效果优于GA和DE。
表3 不同置信水平和可靠性水平下算法性能比较Table 3 Comparison of algorithm performance under different confidence levels and reliability levels
3.3 模型参数分析
为了研究置信水平α1、α2和γ对总成本的影响，对算例I3进行测试，具体分析不同置信水平和可靠性水平对总成本的影响。其中可靠性水平γ在0.1~0.7范围内取值，α1和α2在0.1~1.0范围内取值。由表4可知，对于一定的α2和α1值，随着γ值的增加，使用车辆的数量和运输距离增加，导致运输费用、车辆固定成本、油耗成本和车辆折旧成本增加，并最终导致总成本的增加；
对于一定的γ值，随着置信水平α2和α1的增加，配送中心的开设成本、车辆的固定成本、运输成本、油耗成本以及车辆折旧成本单调递增。
表4 不同置信水平和可靠性水平下算例I3的详细结果Table 4 Detailed results of example I3 under different confidence levels and reliability levels
本文对基本的选址路径问题进行了拓展，考虑包含模糊需求、多周期、可靠性和绿色的选址-路径问题，并建立了相应的优化模型，同时设计了一个混合的遗传算法对模型进行求解。在该算法中，使用自适应参数替代固定值参数和增加了一个高频率变异操作，在保持种群多样性的同时扩展了算法的搜索空间。最后，将HGA算法、GA算法和DE算法分别应用到求解不同规模算例的仿真实验中，结果表明了HGA算法在不同规模的算例中均优于GA算法和DE算法。本文最后分析了不同置信水平和可靠性水平对总成本的影响，结果表明置信水平和可靠性水平都会对总成本造成较大的影响。
猜你喜欢置信水平算例可靠性产品控制与市场风险之间的相互作用研究经济研究导刊(2020年15期)2020-06-21可靠性管理体系创建与实践上海质量(2019年8期)2019-11-16合理使用及正确测试以提升DC/DC变换器可靠性电子制作(2018年23期)2018-12-26单因子方差分析法在卷烟均匀性检验中的研究与应用山东工业技术(2018年18期)2018-10-315G通信中数据传输的可靠性分析电子制作(2017年2期)2017-05-17用VaR方法分析中国A股市场的风险大经贸(2017年1期)2017-03-17基于振荡能量的低频振荡分析与振荡源定位（二）振荡源定位方法与算例中国学术期刊文摘(2016年2期)2016-02-13互补问题算例分析新乡学院学报(2015年6期)2015-11-06基于可靠性跟踪的薄弱环节辨识方法在省级电网可靠性改善中的应用研究电测与仪表(2015年6期)2015-04-09基于CYMDIST的配电网运行优化技术及算例分析电网与清洁能源(2015年2期)2015-02-28