李 晶，邵 倩

（大连海事大学 交通运输工程学院，辽宁 大连 116026）

1 引言

随着经济的发展以及对物流服务要求的提高，医药物流业面临利润空间小、时效性差、经营成本高、难以形成集约化发展等诸多问题，现阶段我国医药物流仍然有待提高以满足人们的要求[1-2]。通常医药物流运输批量小、频率高，对于一些特殊医疗物资还需要低温特殊运输，例如疫苗、针剂等。甚至在极其特殊的情况下，比如新型冠状病毒疫情影响下，医疗物资更加需要保证在特定时间段的供应。车辆配送路径优化作为医药物流的重要问题之一，直接影响到物流企业的物流成本、时效性以及客户对物流企业的满意度、依赖性，对提高服务水平具有很高的现实效益。同时，由于全球能源消耗严重、气候变暖形势的加剧，对可以减少能源消耗的低碳物流的要求日益迫切，并且低碳物流的运营模式可以有效降低成本。医药物流车辆配送路径问题可以表达为带时间窗的车辆路径问题（Vehicle Routing Problems with Time Windows，VRPTW），数学上描述为一个NP（Nondeterministic Polynomial，非确定多项式）问题，这类问题很难求得最优解[3]。针对不同的时间窗约束条件，结合车辆路径模型和客户满意度，启发式算法[4]、禁忌搜索算法[5]、自适应遗传算法[6]以及蚁群算法[7]等算法被成功用于求解VRPTW 问题，并解决一些实际的物流车辆路径优化问题。针对多模糊时间窗医药物流车辆路径优化问题，可以使用改进遗传算法和粒子群算法[8]求解。

2 数学模型构建

2.1 问题描述

使医药物流配送车辆从医药物流企业仓库站点出发服务医院、诊所或者个人，完成用户需求后仍返回仓库站点。这里多模糊时间窗表达的含义是当客户有多个不确定的时间段允许物流企业进行医疗物资配送，每个时间段当中有一个最令客户满意的时间段即客户期望被服务的时间段，送达时间越靠近这个时间段，客户越满意，若送达时间在这个时间段内客户满意度最高，越远离这个时间段满意度越低，但送达时间不能超出客户给定的时间范围即客户可以容忍的服务时间段，否则满意度为零。该多模糊时间窗车辆路径问题可以描述为：一个配送中心，共有m辆配送车辆对n个客户进行配送服务，客户i有Wi个不重合的模糊时间窗。已知客户的位置坐标、客户需要的服务时间，车辆从配送中心出发，分别在用户的时间窗内对客户进行配送服务，然后返回配送中心。通过优化路径，在满足客户时间窗的情况下，降低运输成本，减少碳排放，提高客户的满意度。

根据上述问题设定各个符号的意义，见表1。

表1 模型符号及解释

本文采用梯级模糊时间窗，因此客户满意度定义为函数μi(ti)。

2.2 模型构建

考虑碳排放因素的多模糊时间窗的车辆路径问题优化模型可表达为：

式（2）为最小总成本数学模型，包括车辆固定使用成本、燃油消耗成本、二氧化碳排放的环境成本；式（3）为最大客户平均满意度。其中：

2.3 约束条件

约束条件可表达为：

式（6）保证每个客户的满意度不低于σ，σ是依据经验给出；式（7）保证每个客户都只被一辆车服务，服务每个客户的车辆流量平衡；式（8）表示对每个客户的时间窗按时间顺序排序；式（9）和式（10）表示客户在时间窗内被服务；式（11）表示每个客户都有一个时间窗被服务；式（12）表示每辆车的配送总重量不可以超出额定载重量。

3 算法设计

3.1 构造染色体

在此模型中使用自然数编码。使用一组矢量表示染色体。染色体元素为自然序号，代表不同的客户和配送中心，在染色体中自然序号的顺序代表了车辆访问的顺序。在本文模型中有一个配送中心，因此使用0代表配送中心，n代表不同的客户。

例如，总共有3辆车为10个客户进行配送，假设在种群中其中一条染色体为：[0，7，3，4，10，8，0，2，1，5，0，6，9，0]。染色体表示车辆1的行驶路径为：0-7-3-4-10-8-0，即车辆先从配送中心出发，分别为客户7、客户3、客户4、客户10、客户8进行服务，然后返回配送中心。车辆2 的行驶路径为：0-2-1-5-0，代表了车辆2 从配送中心出发，然后分别为客户2、客户1，客户5进行服务，然后返回配送中心。车辆3的行驶路径则为0-6-9-0，即车辆3 从配送中心出发，分别为客户6、客户9进行服务，然后返回配送中心。

3.2 产生初始种群

根据染色体的构造方式，首先对客户序号进行随机排列，在首尾分别插入0，然后在序列中插入m-1 个0 来形成染色体，m为配送车辆数。由于配送车辆有最大载货量，而且希望使得每辆车尽可能装载多的货物。因此在插入0 过程中需要计算当前累计的载货量，当载货量大于车辆最大载货量时，在该客户前插入0，然后重新进行计算，直到插入所有0。通过上述流程可以随机生成多个染色体并组成初始种群。

3.3 适应值函数

种群染色体随机生成，其中很多染色体并不满足设定的约束条件。约束条件的处理方法是根据约束条件生成染色体，但是该处理方法复杂而且效率不高，本文采用惩罚函数的方法处理。惩罚函数方法是在违反约束条件方案的目标函数中加入惩罚项。本文需要对配送车辆的载重量通过惩罚项进行处理。考虑到遗传算法初期种群多样性大，此时如果惩罚大的话，染色体的多样性会大幅减少，导致过早收敛，陷入局部最优。针对这个问题，惩罚压力根据迭代次数增加，随着遗传算法循环的次数增加而加大。可以得到目标函数为：

t为遗传算法迭代次数，M为较大正数，qi为客户i的需求量，Q为配送车辆的额定载重量。由于需要满足约束条件，则当不符合条件时Z值会变大。随着迭代次数变大，约束条件对目标函数的影响会增大。适应值越大越好，因此上述目标函数min Z取倒数，适应函数可表示为：

3.4 遗传过程

3.4.1 选择算子。在选择策略中选取了锦标赛选择算法，锦标赛选择算法具有容易实现、时间复杂度小、不需要对所有适应值进行排序处理的优点。具体步骤如下：

步骤1：根据适应函数计算当前种群所有染色体的适应值。

步骤2：种群中所有染色体被选择的概率相同，选取3个染色体。

步骤3：比较选中的3个染色体的适应值，选择适应值最好的染色体。

对以上步骤重复操作N遍，生成N条父代染色体用于后续的交叉和变异，生成下一代的染色体。

3.4.2 交叉算子。通过对2 个父代染色体进行交叉重组生成子代染色体。普通的交叉算子一般适用于旅行者问题，并不太适应多辆车的路径优化问题。在交叉算子的选择上，希望能够保留父代优秀路径的信息，并且即使两父代信息相同也能生成不同的子代，避免过早陷入局部最优的情况。

步骤1：分别在两个父代染色体中选择一段子路径。

染色体A：

步骤2：把A选择的子路径加入B的前段，将B选择的子路径加入到A的前段。

染色体A：

步骤3：将A 中与子路径2 重复的数字和后面的0删除，对B进行同样的操作。

染色体A：

步骤4：针对染色体B，在路径2 后4 个位置中插入0，可生成4个路径方案，计算4个路径方案的适应值，将适应值最大的作为子代染色体1。通过相同的操作可以得到子代染色体2。

3.4.3 变异算子。设定变异概率为a%，在区间（0，1)生成随机数b，当随机数b ＞a时，对交叉生成的子代染色体进行变异操作。在子代染色体随机选取2个位置进行交换生成变异后的子代染色体1，再随机选取2个位置进行交换生成变异后的子代染色体2。比较染色体1 和染色体2 的适应值，适应值高的保留，进入子代种群。

3.5 终止条件

遗传算法的终止条件对于确定遗传算法循环结束很重要。开始时算法会进行很快，每次迭代会产生更好的方案，后期会收敛，改进非常小。通过合理设定终止条件，以便解决方案在运行结束时接近最优。通常可以通过预设目标，达到目标后终止程序，或者在最优方案没有提升时结束程序。本文采用预先设定遗传循环次数作为终止的规则。

4 算例分析

4.1 算例介绍

配送中心拥有3 辆型号相同的货车，为25 个客户进行配送服务。每个客户对货物需求量不同，并且具有多个不同的时间窗。货车的额定重量为50，假设电动车出发时间为0，行驶速度恒定为40，货车单位行驶成本为5。单位油耗为5，燃油转换系数为0.4，单位排放二氧化碳成本为1。表2第一列数据表示客户和配送中心的序号。0 代表配送中心，1，2，…，25分别代表客户。第二、三列代表了配送中心和客户的X坐标和Y坐标；第四列代表客户的货物需求量；第五列和第六列代表客户最大容忍的时间窗，第七列和第八列代表客户期待服务的时间窗；最后一列代表客户所需要服务的时间。

表2 算例数据

图1为配送中心和客户的位置分布，其中圆圈代表客户，三角代表配送中心。

图1 配送中心和客户位置分布图

4.2 算例结果

本文使用C++11 实现上述算法程序，并使用该程序对本文的算例进行求解。算法的参数：种群大小为500，迭代次数为2 000，交叉概率为0.95，变异概率为0.3。

运输路径见表3和图2。

表3 运输路径

图2 运输路径

最终计算出运输成本为6 943，碳排放成本为2 777，总成本为10 170，客户平均满意度为0.726。

改变算法对超重方案的惩罚压力为固定值，并且根据迭代次数逐渐增加惩罚压力作对比，对比结果见表4。

表4 算法对比

5 结论

本文针对医疗物流，通过综合考虑各种信息进行动态的路径规划，降低物流成本并且保证货物能按照客户需求送达。使用遗传算法进行求解，由于医疗物流的时效性，加入模糊时间窗口和惩罚项来保证送达时间，在实际应用中有一定的参考意义。在遗传算法实现过程中，通过初期减少惩罚项的权重能保证前期种群的多样性，避免过早收敛，能够有效提高算法效果；通过稳重的交叉算子能较好保留优秀路径的同时产生不同子代；加大变异概率对迭代后期起到较好作用。下一步研究可以考虑不确定影响因素对路径规划的影响，例如实际交通状况和货物体积。