贪心免疫优化算法求解带时间窗的冷链物流选址路径问题

宁雅敬 张惠珍

摘 要：文章针对冷链物流选址路径问题，提出了一种贪心免疫优化算法。首先，建立了考虑物流时间窗约束的选址路径模型，以最小化选址成本、车辆启用成本和运输成本為目标。其次，设计了贪心免疫优化算法来解决该问题。该算法使用六层抗体编码方法，有效提高了抗体突变控制精度和抗体解码效率。通过对初始抗体群体进行贪心预优化，在不压缩丢失抗体突变空间的前提下，提高了初始抗体的适应性。通过对抗体突变方向权值的自适应迭代，提高了算法的优化效率。数值分析结果表明，提出的算法在有时间窗的定位路径问题中具有较好的优化能力，构建的模型可以有效降低定位路径问题的总成本。

关键词：选址路径；时间窗；贪心免疫优化

中图分类号：F252；U116文献标志码：ADOI：10.13714/j.cnki.1002-3100.2024.08.036

Abstract： This paper proposes a greedy immune optimization algorithm for cold chain logistics location and routing problems. Firstly， the paper establishes a location path model that considers logistics time window constraints， with the goal of minimizing location costs， vehicle activation costs， and transportation costs. Secondly， the paper designs a greedy immune optimization algorithm to solve this problem. This algorithm uses a six layer antibody encoding method， effectively improving the accuracy of antibody mutation control and antibody decoding efficiency. By performing greedy pre optimization on the initial antibody population， the adaptability of the initial antibody is improved without compressing the loss of antibody mutation space. The optimization efficiency of the algorithm has been improved through adaptive iteration of antibody mutation direction weights. The numerical analysis results indicate that the proposed algorithm has good optimization ability in location path problems with time windows， and the constructed model can effectively reduce the total cost of location path problems.

Key words： site selection path; time window; greedy immune optimization

0    引    言

近年来，随着物流业的发展和人们对食品安全的关注度不断提高，冷链物流逐渐成为物流行业中的重要领域[1]。冷链物流在运作过程中需要严格控制时间窗口、温度、湿度等因素，因而其选址路径成为十分关键的问题，直接影响着物流成本、效率和服务质量。因此，如何有效地求解带时间窗的冷链物流选址路径问题已经成为学术界和工程界研究的重点之一。

传统的LRPTW优化求解方法包括暴力搜索[1-3]、贪心算法[4]、遗传算法[5]、模拟退火算法[6]等。随着物流路径的复杂程度和配送中心、客户数量的逐步提升，LRPTW问题的求解空间呈现现出非线性增长趋势，传统算法的寻优效率和求解精度较难满足复杂场景下的计算需求。免疫优化算法（Immune Optimization Algorithm，IOA）作为一种新兴的启发式算法，通过模拟免疫学功能、原理和模型来解决复杂的自适应系统，在计算机安全、路径优化、数据挖掘等领域具有很好的应用潜力和可拓展性[7]。姚翠平[8]提出一种基于免疫算法的船舶运输路径优化方法，通过综合评估提出优化运输路径的最优方案。王永成等[9]利用免疫算法解决多无人机任务最优规划问题。然而，传统免疫优化算法在解决带时间窗的冷链物流选址路径问题时显现出了搜索速度较慢、精度有限、收敛性差等缺点。王杰等[10]提出一种基于改进免疫遗传算法和Holt-Winters模型的电能计量器具配送网络优化策略。

本文对传统免疫算法进行改进，在其基础上引入贪心优化策略，重新设计抗体编码和自适应抗体变异权重，提升了算法在带时间窗的冷链物流选址路径问题中的寻优效率和能力。重点在于重新设计了六层结构的抗体编码方式，增强了变异控制和解码效率；采用贪心优化策略对初始抗体群进行了预优化，提高了初始抗体的适应性；通过自适应迭代抗体变异方向权重，加速了算法的寻优过程。案例分析表明，GIOA有效克服了原算法的局部最优和收敛速度慢等问题，在解决复杂VRPTW问题上具有理论和实际应用意义。

1    带时间窗的选址路径问题

1.1    问题描述

本文所研究的带时间窗的冷链物流选址路径问题涉及选址和路径规划两个方面。选址的目标是确定最少的配送中心并計算总建设成本；路径规划的目标是通过合理分配和运输安排最小化物流总成本，包括配送中心建设成本、运输成本、车辆启用成本和时间窗惩罚成本。

在本文所建立的模型中，供应商若干个，候选配送中心若干，终端网点若干；

供应商、候选配送中心、终端网点的位置己知，在从配送中心到终端网点的配送过程中将时间窗因素考虑在内，设定超出规定时间而产生的惩罚成本与时间有线性函数关系；

终端网点需求量已知，在一定时间内需求不存在波动；

支线运输（从配送中心至终端网点）过程中采用统一标准的车辆，每辆车仅听从一个配送中心的调遣，但是每辆车可以服务多个终端网点，但每个终端网点只能由一辆车进行配送；

运输过程中车辆的终点为配送中心，配送途中车辆的速度己知且固定；

在配送中心等候提供派遣服务的车辆数量足够多，并且每个配送中心的存储量己知；

运输车一直处于恒温状态，其他影响因素忽略不计；

干线运输（从供应商至配送中心）过程中采用统一标准的车辆，每辆车的起点均为供应商，但每辆车仅服务一个配送中心。

1.2    模型符号的定义

对生鲜冷链物流配送中心选址及路径优化模型中的各变量符号定义如下。

R=｛r｜r=1，2，3，…，r｜r≤10｝，表示供应商集合；

J=｛j｜j=1，2，3，…，j｜j≤10｝，表示候选配送中心集合；

N=｛n｜n=1，2，3，…，n｝，表示终端网点集合；

K=｛k｜k=1，2，3，…，k｝，表示从配送中心到终点网点的运输车辆集合；

F表示配送中心的固定建设和运作成本；

Zj表示是否在此处建立配送中心；Zj=

drj表示从供应商到配送中心的欧氏距离；

Crj表示从供应商到配送中心之间的单位运输成本；

djn表示从配送中心（或终端网点）到终端网点的欧氏距离；

Cjn表示从配送中心（或终端网点）到终端网点的单位运输成本；

Bk表示从配送中心到终端网点的配送过程中启动车辆k的固定使用成本；

Mn（tn）表示终端网点的惩罚成本；

tjn表示从配送中心（或终端网点）到终端网点所用的时间；

Yjn表示终端网点是由配送中心出发并进行配送；

C1表示车辆提前到达终端网点发生的单位时间的惩罚成本；

C2表示车辆超出规定时间到达终端网点发生的单位时间的惩罚成本；

Rn表示时间窗是否得到满足，Rn=；

Xjk为0～1变量，表示车辆在行驶过程中的时间窗约束。

超出规定时间带来的总惩罚成本：

1.3    带时间窗选址路径模型

下式表示选址路径模型最小化的物流总成本，其中包括生鲜食品从供应商r到冷链配送中心j的运输成本、配送中心的总建设成本、生鲜食品从被选配送中心j到终端零售门店n的运输成本、车辆启用成本、车辆早到以及迟到的惩罚成本。

约束条件S.T.。

决策变量如下。

式（1）表示至少建一个配送中心；

式（2）表示配送中心总配送量能够满足终端网点的总需求量；

式（3）表示每个终端网点都由一个选中的配送中心有且仅为其提供一次配送服务；

式（4）表示每辆车最多被启用一次；

式（5）表示每一辆车不能超过其最大载重量；

式（6）表示从配送中心到终端网点的进出车辆相同；

式（7）表示限制了从配送中心到终端网点的过程中各个配送中心之间不允许存在路径；

式（8）表示配送车辆的最大行驶距离限制；

式（9）表示消除子路径；

式（10）和（11）表示X kjn和Zj这两个决策变量之间的关系；

式（12）表示每个终端网点都指定一个被选中的配送中心为其提供配送服务；

式（13）表示如果配送车辆在经过j点后到达n点，则车辆k到达节点n的时间是车辆k到达上一节点j的时间加上在n点的服务时间再加上jn间行驶消耗的时间，否则该约束松弛；

式（14）（15）（16）（17）（18）表示条件的满足状态。

2    贪心免疫优化算法

2.1    抗体种群贪心初始化（见图1）

在本文GIOA中，首先使用贪心优化算法对初始种群进行优化，将种群划分为若干个簇（Cluster）。然后，在每个簇内部应用贪心优化算法，以寻找更好的局部解。同时，引入一些新种群，以维持种群的多样性和避免早熟现象。

2.2    抗体编码方式（见图2）

为解决J选址和J2N路径编码问题，设计如下抗体变量，其中第一层是N编码，编码范围是1—N；第二层是J编码，编码范围是1—J；第三层是路径选择编码，范围是0—1。（见图3）

为了确保该抗体可以转译出合理的路径和J选址，规定该抗体编码第一层为1—N的排列数，第二层为1—J的随机数，第三层为0—1的随机数据。

运输路径的解码规则为，每一列上层N与下层J是一一对应关系，当有多个N对应同一J时，有第三层编码决定是否有同一班次K运送。

抗体4—6层是R的编码，当该列非0时，该列的J由R配送。（见图4）

2.3    免疫操作（见图5）

本文设计的免疫操作包含抗体变异、邻域搜索、自适应权重三个步骤。

2.3.1    变异操作

在完成每次免疫个体之间的克隆操作后，引入变异操作。变异操作旨在扩大搜索范围，增加多样性，从而防止算法过早收敛。

针对本文设计的抗体编码结构，抗体交叉变异分为四种类型：

第一层变异，随机生成范围1—N的两个位置数，交换该位置里的数据；

第二层变异，随机生成范围1—N的1个位置数和范围1—J的数据数用于替换该位置内的数据；

第三层变异，随机生成范围1—N的1个位置数和范围0—1的数据数用于替换该位置内的数据；

第四到六层变异，随机生成范围1—N的1个列位置数、范围3—6的1个行位置数，用范围0—R的数据数来替换该位置的数据。

2.3.2    邻域搜索

当迭代到指定的停止条件时，在每个最优解周围添加一个邻域，通过邻域搜寻最优解。邻域搜索的具体过程如下：首先选定一个邻域半径，如4个变异层的距离；然后通过随机搜索来计算该变异层的适应度值，不断改变变异层并筛选出最优解作为当前搜索的最优解。

2.3.3    自适应变异权重

记录每次抗体变异的方向及其适应度，建立抗体变异权重向量，当某个方向的变异使得抗体适应度增加时，则增加相应方向的变异权重。

2.4    算法步骤（见图6）

改进的免疫优化算法主要包括以下几个步骤。

初始化参数：确定算法的基本参数，包括种群数量size-pop、记忆库容量over-best、期望繁殖概率的多样性评价参数p-s、交叉概率p-cross、变异概率p-mutation抗体的长度length、初始抗体的数目number、迭代次数iteration、抗体间相似度的阈值r；

生成初始免疫个体：随机生成一组初始解作为免疫个体，并计算其适应度函数值；

克隆操作：按照适应度函数值选择并克隆免疫个体，生成新的解，这些新解会受到一定程度的“突变”影响，以增加种群的多样性；

交叉操作：在完成每个免疫个体之间的克隆操作后，引入交叉操作。选择两个免疫个体，并利用交叉方法生成另外两个新的免疫个体；

选择操作：选择经过克隆和交叉后的所有新解中k个最优解作为下一次搜索的初始点；

邻域搜索：当迭代到指定的停止条件时，在每个最优解周围添加一个邻域，并通过邻域搜索寻找更优的解；

重复操作：在新选择的k个解作为免疫个体的基础上，重新进行克隆、交叉、选择和邻域搜索操作，直到达到预设的进化次数。

3    算例分析

为了验证模型的可行性和有效性，以及评估改进的免疫优化算法求解带时间窗的选址路径问题的性能，使用MatlabR2018b实现该算法，并在Windows7系統下，在一台配备2.7GHz主频处理器和4GB内存的PC机上进行大量的数值试验。

3.1    算例原始参数

在初始种群优化中，设置免疫个体200个，初始种群簇1 000个，种群簇融合概率0.5；设置免疫算法最大迭代次数1 000次，抗体克隆次数20次，单抗体变异3次，变异类型4种，新旧抗体比列1：1；自适应领域搜索中设置搜索次数5 000次，初始变异概率相同。

算例中设置5个供应商，10个候选中转站，20个客户点。

3.2    算例结果与分析

为说明本文改进免疫算法的有效性，将本文GIOA算法、无初始种群优化IA算法和无领域优化IA算法进行对比分析。

算例5-10-20下本文GIOA算法结果如图7所示，相关的指标见表1。

算例5-10-20下无初始种群优化IA算法结果如图8所示，相关的指标见表1。

算例5-10-20下无领域优化IA算法结果如图9所示，相关的指标见表1。

在三种算法对比中，可以发现在小规模算例中，本文所提的GIOA算法的寻址时间较长，这是因为无初始种群优化GIOA算法和无领域优化GIOA算法只能改进免疫优化算法中的局部。改进的免疫算法由于加入了初始解的生成操作和多种不同的交叉变异操作，在使得求解质量更优的同时，耗费了一定的程序时间。但考虑到运输建设成本以及对应的总成本，该算法的求解质量具有较大优势。

3.3    算法性能分析

为进一步验证本文所提出的GIOA算法的有效性，将其与传统免疫算法和遗传算法在5-10-20、5-10-100、5-20-20、5-20-100、10-10-20、10-10-100、10-10-20、10-20-100这8种规模算例中进行对比分析，取5次计算结果，取得的最优成本结果如图10所示，平均成本和时间如表2所示，其中总成本单位为103，时间单位为秒。

通过表2可以看出，与传统免疫算法相比，本文所提出的改进面议算法的运行时间略长，主要是因为改进的免疫算法中加入了初始解的生成操作和多种不同的交叉变异操作。但从总成本角度看，改进免疫算法明显优于另外三种算法。

4    结    语

本文对带时间窗的冷链物流选址路径问题进行了研究，并使用改进的免疫优化算法进行求解。通过引入动态调整机制、粒子初始位置的启发式选择以及避免全局信息丢失等方式，对免疫优化算法进行了改进，有效改善了传统免疫算法过早陷入局部最优解、收敛速度慢、在高维空间内搜索能力差的问题。对比GA和CPLEX，本文所提出的改进免疫算法对于带时间窗的冷链物流选址路径问题有良好的优化性能。

参考文献：

[1] 李震，段力伟．“公转铁”背景下铁路冷链运输发展对策[J]．铁道货运，2020，38（6）：37-41.

[2] 虎翼飞，张惠珍，陈曦．改进野马算法求解低碳开放式送取货选址路径问题[J/OL]．包装工程，2024：1-14.[2024-01-20].

http：//kns.cnki.net/kcms/detail/50.1094.TB.20230818.1308.004.html.

[3] 张戬，刘炜，潘卫国，等．基于改进暴力搜索算法的全双向变流供电系统参数设计[J]．电工技术学报，2021，36（23）：4896-4904.

[4] 徐小小，周启银，娄成龙，等．基于贪心算法的自动路径规划送药小车[J]．中国新技术新产品，2023（8）：21-23.

[5] 李家碧，韩曙光．考虑客户等级和时变路况的无人物流配送路径[J]．浙江大学学报（工学版），2023，57（10）：2018-2027.

[6] 宾厚，张路行，王素杰，等．基于改进多目标遗传算法的农村低碳物流配送路径优化[J]．中国农业大学学报，2023，

28（7）：224-237.

[7] 马元锋，李昂儒，余慧敏，等．基于动态拥挤距离的混合多目标免疫优化算法[J]．计算机科学，2018，45（S1）：63-68.

[8] 姚翠平．结合免疫算法的船舶运输路径优化方法研究[J]．舰船科学技术，2019，41（12）：58-60.

[9] 王永成，蔡晨晓．免疫算法在多无人机任务最优规划中的应用[J]．机械设计与制造，2023（8）：237-241.

[10]  王杰，孙林，郑直，等．基于改进免疫遗传算法和Holt-Winters的电能计量器具配送优化[J]．电力科学与技术学报，2022，

37（2）：156-163.