时变路网下城市医药冷链路径优化研究

廖道争?王江?潘宇

摘要：针对医药冷链配送的高成本、严时效及高客户要求等挑战，综合考虑了时变车速、载重、客户时间窗、满意度及成本等关键因素，提出了一种城市医药冷链路径优化策略。以最小化总成本和最大化客户满意度为目标，构建了时变路网下的优化模型，并运用改进的单亲遗传算法求解。通过多类型算例验证，该方法显著降低了配送成本和时间，提升了准时率和时效性。

关键词：配送成本；客户满意度；时效性；时变路网

一、前言

近年来，我国生物制药行业得到突飞猛进的发展。2021年，生物医药行业累计营收为5918亿元，同比增长113.8%[1]，但是医药冷链物流配送成本一直居高不下。

解决医药冷链物流配送问题的关键在于科学规划配送车辆路径。申晓宁[2]等以总成本最小和客户不满意度最低为目标构建路径规划模型，采用多目标烟花算法对问题进行求解。季琳琳[3]等设计了以成本和满意度为目标的运输模型，通过灰度白化权函数确定满意度等级，并运用改进遗传算法求解该模型。

王宁[4]等考虑到不同时段道路的拥堵问题，采用分段函数刻画不同时段的车辆行驶速度，设计不同规模算例进行求解。赵志学[5]等依据时变路网特点，设计路段划分策略来计算行驶时间。

二、问题描述与模型建立

本研究针对城市医药冷链配送，在时变路网下优化配送路径，旨在实现总成本最小化、客户满意度最大化的目标。

（一）符号说明

O、K分别为：配送网络所有结点集合， 配送中心所有车辆集合。

qi、qj、dij分别为：客户点i、j的医药需求量、客户点i与客户点j的距离。

t0k、tika、tikl、tijk分别为：车辆k的出发时刻、到达客户点i的时间、离开客户点i的时间、在道路（i，j）行驶总时间。

e1、e2分别为：早到和晚到的惩罚成本。

车辆k从i点行驶到j点

其他

车辆k负责客户点i的物流配送

其他

（二）相关因素分析

1.时变路网行驶时间计算

参照安聪琢的研究方法[6]，具体步骤如下：

首先，将客户时间窗细分为多个时间段，并利用百度地图大数据平台获取各时间段的平均速度数据。

接着，根据配送中心的发车时间确定其所属时间段的平均速度，并假定在该时间段内车辆以恒定速度行驶。随后，利用这个速度计算客户点的到达时间，并判断行驶过程是否跨越了不同的时间段，如果行驶过程处于同一时间段内，就按照该时间段的恒定速度来计算行驶时间，如果行驶过程中跨越了多个时间段，则会根据每个时间段的平均速度来分段计算行驶时间。

2.客户满意度分析

本研究采用送达时间的模糊隶属度函数来衡量客户满意度，客户点i的满意度函数为：

式（9）表示目标函数，由配送过程中的固定成本、运输成本、制冷成本，以及时间窗惩罚成本构成。式（11）表示配送车辆不得超载。式（12）表示每个客户点只有一辆车配送。式（13）表示配送网络为闭环且每辆车只能使用一次。式（14）表示客户点的时间窗约束。

三、算法设计

本文提出基于贪心策略的改进型单亲遗传算法，通过对比适应度，筛选并保留最优染色体，从而增强局部搜索能力，同时保持全局搜索能力。

（一）种群初始化策略

采用自然数编码随机生成初始种群。首先确定种群规模，生成随机客户点序列，并在随机选取的K个位置插入0表示车辆调度，然后，在序列首尾加0形成闭环，若生成的序列满足约束条件，则保留，否则重复上述步骤，直至达到种群规模。

（二）计算适应度函数策略

其中，Zx为染色体x的目标函数，Hx为染色体x对应的适应度。

（三）变异策略

为了扩大解的搜索空间，提高算法求解效率和求解质量，改进单亲遗传算法增加改变插入点的变异方式，形成基因换位+改变插入点、基因倒位+改变插入点、基因移位+改变插入点三种形式。

（四）基于贪心思想的选择策略

引入贪心算法，进行局部调整操作，通过此种方法的局部寻优，找到局部最优。具体操作如下：

1.分别计算各染色体的适应度，并按适应度值的大小进行降序排列。

2.将适应度值大的个体与上一代最优个体进行比较，如果该个体适应度大于上一代，则将变异后个体代替变异前个体，否则仍旧保留原最优个体，最后将结果采用最佳个体保留策略进行保存。

3.每个染色体通过各自的适应度值以及种群适应度之和来计算各自被选择的概率，计算方法如下：

（13）

4.计算染色体累计概率 qx=∑x∈Npx。

5.生成一个[0，1]之间的随机数ω，若ω≤q1，则将第一条染色体加入下一代种群中。若qx-1≤ω≤qx，则将第x条染色体加入下一代种群中，循环操作直到将本代个体选择完。

6.将步骤2保存的个体和步骤5选择的个体组合生成新一代種群。

四、算例实验与结果分析

（一）实验设置

1.本研究选取Solomon算例库[7]中C102、R202、RC202三个标准算例作为实验数据，

配送路径如图1所示。

2.与静态网络的实验对比

以RC202算例为例，静态速度选取时变速度的平均值为：45km/h，对比静态网络与时变网络下的结果如表1所示。

表1显示，与静态路网相比，时变路网在配送路径的行驶路程和总成本上分别降低了5.89%和7.79%。尽管行驶时间增加了35分钟，但考虑到实际路况对车速的影响及车辆难以持续匀速行驶的情况，这一时间增加是可接受的。因此，本研究的时变路网VRP模型较传统静态模型更符合实际，且在成本和行驶距离上有明显优势。

3.不同优化算法的结果分析

为了验证改进单亲遗传算法的有效性，在使用RC202算例的情况下，采用标准遗传算法、单亲遗传算法、改进单亲遗传算法作对比实验，结果如表2所示。

表2显示，改进单亲遗传算法在程序运行时间上较单亲遗传算法和遗传算法分别缩短了13.77秒和856.57 秒，显著提升了求解速度。尽管在配送总成本和距离上略有增加，分别增长了2.33%、1.08%和8.62%、8.05%，但在配送时间上却大幅降低了12.82%和21.77%。这表明改进单亲遗传算法以较小的成本和距离代价，实现了更高效的配送，充分展现了其优越性。

五、结语

为应对医药冷链配送的高成本和时效性挑战，本文构建了时变路网下的配送路径优化模型。通过考虑交通、天气及客户时间窗等因素，采用车速预测函数和路段划分策略计算行驶时间。利用基于贪心思想的改进单亲遗传算法求解模型，实验显示该方法能有效规划配送路线，降低成本，提升时效性，验证了设计方案的有效性。

参考文献

[1]国家发展改革委举行新闻发布会介绍“十四五”生物经济发展规划有关情况[J].中国产经，2022（10）：16-23.

[2]申晓宁，游璇，陈庆洲，等.采用双档案协同进化离散多目标烟花算法的低碳疫苗冷链优化配送[J].计算机工程与科学，2022，44（12）：2255-2265.

[3]季琳琳，王清威，周豪，等.考虑顾客满意度的冷链水果路径优化[J].浙江大学学报（工学），2021，55（02）：307-317.

[4]王宁，胡大伟，徐杰，等.基于客户价值和满意度的城市冷链物流时变路径问题[J].中国公路学报，2021，34（09）：297-308.

[5]赵志学，李夏苗.时变交通下生鲜配送电动车辆路径优化方法[J].交通运输系统工程与信息，2020，20（05）：218-225+239.

[6]安聪琢.时变路网下医药冷链物流配送路径优化研究[D].秦皇岛：燕山大学，2022.

[7]孙靖璐.基于改进自适应大邻域搜索算法的带时间窗车辆路径问题研究[D].北京：北京交通大学，2022.

责任编辑：王颖振、周航