1. 引言
枢纽选址问题(hub location problem, HLP)是经典选址问题的延伸,在现实生活中占据极其重要的地位,甚至具有战略意义。基本枢纽选址问题分为P-中位问题、P-中心问题和覆盖选址问题。航空、公共交通网络、快递、供应链管理和电信系统等领域的枢纽选址问题通常基于轴辐式网络理论开展后续研究。
O’Kelly [1] 首次提出二次整数规划的通用枢纽选址模型,将轴辐式网络应用于枢纽设施选址和网络设计模型上,主要解决轴的位置以及辐的分派问题,并指出该问题属于NP-hard问题。Helm [2] 等设计了单分配无容量约束的轴辐式航空网络模型,采用模拟退火算法进行求解,研究表明该模型能够降低航空网络运输成本。Correia I [3] 等对有容量约束的单分配轴辐式物流网络模型进行回顾,并增加了新的约束条件,减少了模型的计算时间。Camargo [4] 等研究无容量限制的多分配轴辐式网络模型,采用Benders分解方法解决交通拥堵严重时交通成本高的问题。赵晋 [5] 等构建允许辐点间直达的快递网络规划决策模型,对比发现复合轴幅式网络比纯轴辐式网络更利于降低快递网络总成本、提高服务时效性。
以上文献多是解决单层级单阶段枢纽选址问题,随着应用过程需求的复杂化,国内外学者建立多层级多阶段轴辐式网络选址模型。Jaemin [6] 等设计了一个具有两级枢纽的轴辐式网络选址模型,最大限度地降低物流网络成本。李永竞 [7] 等提出一个考虑充电站建设成本的三阶段选址模型,通过仿真验证了模型的有效性,为充电站的科学选址分配问题提供了参考。Zhao [8] 等结合城市地铁系统,提出一个两级三阶段轴辐式结构的优化模型,并论证适合上海地铁物流网络的选址布局方案,结果表明多层级多阶段轴辐式网络选址模型,能够提供合理的枢纽选址方案。
随着同城物流市场的快速扩张,合理的快递枢纽布局尤为重要,单层级单阶段轴辐式网络选址模型无法满足需求,考虑多层级多阶段轴辐式网络选址模型有利于问题的求解。同时,由于枢纽节点存在容量限制和拥堵概率,必要时考虑开通辐点间直达链路以缓解枢纽处拥堵情况。为此,针对同城快递枢纽选址问题,结合点对点网络,建立基于复合轴辐式网络的两阶段同城快递枢纽选址优化模型,为同城快递枢纽选址问题提供合理的建议。第一阶段,自“需求点”角度出发,考虑辐点容量限制,以成本最小为优化目标,建立基于集覆盖模型的辐点选址优化模型,并引入Tent混沌、t分布变异算子等更新策略改进黏菌算法(SMA)进行求解,得到辐点选址方案和对应服务点;第二阶段,自“企业”角度出发,考虑轴点容量限制,轴点拥堵情况,以成本最小为优化目标,建立基于复合轴辐式的轴点选址优化模型,采用郊狼算法(COA)进行求解,得到轴点选址方案和对应辐点;最终,以上海市某快递企业同城快递网络为案例,通过仿真实验验证模型和算法的有效性,为同城快递枢纽合理选址提供一定的建议。
2. 模型构建
2.1. 问题描述
同城快递网络可由
表示,其中N为所有节点的集合,节点包括枢纽节点、转运中心和末端需求点;A为所有边的集合。利用现有趋于完善的快递网点,满足研究区域内所有末端需求点,得到合理的同城快递枢纽布局方案。为此,本文将同城快递网络枢纽选址分为辐点选址阶段和轴点选址阶段:第一阶段,考虑辐点容量限制,构建基于集覆盖模型的辐点选址优化模型,得到辐点选址方案和对应需求量;第二阶段,考虑轴点容量限制且存在轴点拥堵情况,允许部分辐点间开通直接连接链路,构建基于复合轴辐式网络的轴点选址优化模型,得到最终轴点选址方案和对应辐点。
2.2. 基于集覆盖模型的辐点选址模型
2.2.1. 模型假设
为保证模型的可行性和有效性,做出以下假设:1) 辐点负责需求点包裹的收派件任务;2) 每个需求点可以分配给已选择的一个辐点;3) 辐点存在固定建设成本、容量限制;4) 需求量根据地区人均快递包裹数和该地区常住人口进行估算;5) 快递员每次只负责一个需求点的包裹取件,各需求点取派件相互独立。
2.2.2. 符号说明
集合:
I为候选辐点集合,索引为i;
L为需求点集合,索引为l;
参数:
为需求点到辐点的距离;
为辐点日均运行固定成本;
为需求点包裹件数;
为需求点到辐点间单位距离运输成本;
为辐点处的同城快递件均分拣成本;
为选择的辐点数量;
为辐点i的最大容量,即最大快递处理能力;
决策变量:
2.2.3. 模型建立
目标函数:
(1)
约束条件:
(2)
(3)
(4)
(5)
(6)
目标函数式(1)表示需求点到辐点的运输成本、辐点处的固定运行成本、辐点处快递包裹分拣成本之和;约束式(2)表示最终选择辐点的数量;约束式(3)保证需求点只能接受已被选为辐点的服务。约束式(4)保证辐点处理包裹数量不会超过其最大包裹处理能力。约束式(5)保证每个需求点只能分配给一个辐点。约束式(6)表示决策变量。
2.3. 基于复合轴辐式网络的轴点选址模型
2.3.1. 模型假设
为保证模型的可行性和有效性,做出以下假设:1) 轴点作为转运节点,不负责快递的派取任务;2) 每个辐点分配给一个轴点;3) 辐点之间允许直接连接;4) 轴点存在固定运行成本、容量限制;5) 辐点间进行同城快递转运最多经历两个轴点;6) 轴点之间为全连通网络。
2.3.2. 符号说明
集合:
I为候选辐点集合,索引为
;
M为候选轴点集合,索引为
;
参数:
为辐点i与辐点j之间包裹件数;
为辐点i与辐点j直接连接单位距离运输成本;
为轴点k与轴点j之间单位距离运输成本;
为辐点i与轴点k之间单位距离运输成本;
为辐点i与辐点j之间运输距离;
为轴点处同城快递件均转运成本;
为轴点处运行固定成本;
为轴点k的最大容量,即最大快递中转能力;
为辐点i到辐点j在轴点k与轴点m之间运输的包裹件数;
为辐点i到辐点j在轴点k处转运的包裹件数;
为辐点i到辐点j直接运输的包裹件数;
为轴点处拥堵系数 [9] ,
:
为拥堵因子,
为轴点拥堵程度。考虑三种不同的拥堵程度,70%、85%和100%。随机生成一个
,表示轴点处中转拥堵概率,
在70%以下,
,
。对于
在70%到85%之间,
,
。对于φ高于85%的情况,
。
为选择的轴点数量;
决策变量:
2.3.3. 模型建立
目标函数:
(7)
约束条件:
(8)
(9)
(10)
(11)
(12)
(13)
目标函数式(7)表示包括从出发辐点i到轴点k运输成本,轴点k和m间运输成本、轴点m到辐点j运输成本,轴点固定运行成本、轴点处转运成本,辐点i到辐点j直达运输成本之和;约束式(8)表示最终选择辐点的数量;约束式(9)确保要么通过直接链路,要么通过轴点进行转运;约束式(10)表示每个辐点最多分配给一个轴点;约束式(11)表示未选为轴点不能向辐点提供服务;约束式(12)保证轴点包裹的数量不会超过其最大处理能力;约束式(13)表示决策变量。
3. 算法
3.1. 黏菌算法
黏菌算法(Slime Mould Algorithm, SMA),于2020年Li等人 [10] 出的一种新型智能算法。SMA算法模拟了黏菌在寻找食物过程中形态和行为的变化,黏菌的行为主要包括三种:接近食物、包裹食物和获取食物。
3.1.1. 接近食物
黏菌算法模拟了多头绒泡菌在觅食阶段寻找、包围食物的过程。黏菌的前端呈扇形,后面是相互连接的静脉网络。当静脉接近食物时,黏菌的生物振荡器会产生扩散波来改变静脉中细胞质的流动,使黏菌向更好的食物移动。黏菌在接近食物阶段的位置更新公式为:
(14)
其中,
表示个体目前发现的最优解位置,
是范围为
的随机数,W是黏菌的权重系数,
和
表示从黏菌中随机选取的两个个体的位置,
是在[−1, 1]内震荡并最终趋于零的参数,r为[0, 1]之间的随机数。
参数p、参数a和权重系数W的更新公式分别为:
(15)
(16)
(17)
(18)
其中,N为种群规模,
,
表示第i个黏菌个体的适应度,
表示当前迭代下黏菌的最佳适应度,t为当前迭代次数,T为最大迭代次数,
为当前迭代的最佳适应度,
为当前迭代的最差适应度,
表示
排名前一半的黏菌个体,
表示对黏菌个体适应度值的排序序列。
3.1.2. 包裹食物
包裹阶段是模拟黏菌静脉结构内的收缩方法,位置根据食物质量进行调整,食物浓度越高,区域权重越大,位置更新公式如下:
(19)
其中,rand是[0, 1]的随机值,
和
表示搜索空间的上界和下届,z是切换概率,其余参数同上。
3.1.3. 获取食物
黏菌主要依靠生物振荡器产生的波调整静脉中的细胞质流动,使其处于食物浓度较高的位置,通过参数
、
、
模拟黏菌的振荡变化。
模拟不同食物浓度下的振荡频率,黏菌根据发现食物浓度的不同从而调整接近食物的速度,当食物浓度较低时,黏菌接近食物的速度较慢,可以提高黏菌选择最佳食物源的效率。
在
内并且随着迭代次数的增加逐渐接近零。
在
之间振荡并且逐渐趋于零。
和
之间的协同作用模拟黏菌的选择行为,使得黏菌搜索食物更具全面性。
3.2. 改进的黏菌算法
黏菌算法作为一种新型智能算法,具有参数少、模型简单、扩展性和寻优能力强于传统智能优化算法的特点,目前已应用于工程优化 [11] 、参数估计 [12] 等领域。依然存在寻优精度低、收敛速度慢及易陷入局部最优的不足。因此尝试引入tent混沌、t分布变异算子等改进策略来改进基础的黏菌算法。
3.2.1. Tent混沌
黏菌进行更新位置的时候,一般选择当前最优位置进行更新,会出现搜索范围小的情况。为提高搜索效率,选择对当前最优位置添加一个扰动,并对位置信息进行贪婪策略判断,判断当前位置是否最优。本文利用混沌运动的随机性、规律性和遍历性,产生丰富多样的种群。当
时,通过Tent混沌映射得到
,Tent混沌映射表达式为:
(20)
其中,
表示映射次数;
表示第
次映射函数值。
采取贪婪策略进行判断是否保留结果,贪婪策略表达式为:
(21)
3.2.2. t分布变异算子
当
时,采用t分布变异算子
进行位置扰动,改进迭代过程中黏菌的搜索位置。
(22)
当
时,加入新的位置更新策略,表达式如下:
(23)
3.3. 郊狼优化算法
郊狼优化算法(coyote optimization algorithm, COA)是由Juliano于2018年提出的一种全局优化算法,通过模拟郊狼出生、成长、死亡和迁徙行为,包括初始化种群、郊狼的成长、郊狼的生死以及驱逐和接纳4个步骤 [13] 。每一个郊狼代表问题的一个候选解,每个解向量由郊狼的社会状态因子构成,用郊狼的社会适应能力来评价每个候选解向量的质量。
3.3.1. 初始化郊狼种群并随机分组
总郊狼数量为N,分成
个组群,每组有
个郊狼。第
组第c个郊狼在第j维的初始位置
并计算每个郊狼的社会适应度值F:
(24)
(25)
其中,
为[0, 1]内均匀分布的随机数;
、
为第
维状态因子的上下界,
;
为初始设置搜索空间维度。
3.3.2. 组内郊狼的成长
寻找组内郊狼文化趋势计算式:
,其中
为
行D列的矩阵,表示组内的
个解向量;
为第
维状态因子;
为取中位数。计算最优郊狼(头狼)
和随机郊狼
的差异
;组内文化趋势
和随机郊狼
差异
。组内郊狼成长与
与
有关:
(26)
(27)
(28)
其中,
是组内第
只头狼成长获得的新解;
和
为[0, 1]内均匀分布的随机数。
每只头狼成长后,对新个体计算社会适应能力,采用迭代贪心算法进行优胜劣汰,保留更优郊狼参与组内其余郊狼成长。
3.3.3. 郊狼的生与死
组内郊狼成长后,产生一只新的幼狼,幼狼的产生受随机选择父母郊狼的遗传和环境因素影响:
(29)
其中,
为幼狼的第
维度;
为
内均匀分布的随机数;
和
是幼狼随机的两个维度;
为第
维决策变量在限制范围内随机产生的变异值;
和
分别为分散概率和关联概率。
(30)
(31)
每出生一只新生郊狼,就会有一只郊狼淘汰。郊狼生死的规则如下:1) 新生郊狼的适应能力最弱,则新生郊狼直接淘汰;2) 组内有一只郊狼比新生郊狼适应度值差,适应度值最差的郊狼淘汰;3) 组内有多只郊狼的适应度值比新生郊狼的适应度值差,淘汰年龄最大的郊狼。
3.3.4. 郊狼的驱逐与接纳
为保证郊狼组之间的信息共享和种群的多样性,郊狼被驱逐出原本所属的组群概率为
。
4. 算例分析
4.1. 数据来源
为验证模型的有效性,选取上海市某快递企业同城快递网络作为仿真对象。根据上海市统计局数据,第七次人口普查上海市常住人口为2487.09万。根据上海市邮政管理局数据,上海市2021年1~12月同城快递业务总量为82632.8万件。
一年按照365天计算,计算出每日人均的同城快递量为0.09件。如图1和图2所示,选取上海市主要城区466 km2作为研究区域,选取区域内共计366个居住点作为需求点集合 [8] ,部分需求点坐标信息及需求量见附录1。根据人口数据与每日人均快递量乘积得到每个需求点的同城快递需求量。
爬取POI数据,获取主城区某公司营业点(店)作为候选辐点集合(编号FD01-FD58),候选辐点坐标信息见附录2;获取主城区转运中心作为候选轴点集合(编号ZD01-ZD39),候选轴点坐标信息见附录3。
注:该图基于自然资源部标准底图服务网站下载的审图号为GS(2022)4312号的标准地图制作,底图无修改。
Figure 1. Schematic diagram of the research area
图1. 研究区域示意图
![](//html.hanspub.org/file/14-2571419x153_hanspub.png?20240314090845429)
Figure 2. Distribution map of demand points
图2. 需求点分布图
4.2. 参数设置
参考文献 [14] [15] [16] 并使用部分折算设置参数:辐点固定运营成本
;需求点至辐点单位距离运输成本
;辐点处单位分拣成本
;辐点处容量限制
;轴点固定运营成本
;轴点间单位距离运输成本为
;辐点至轴点间单位距离运输成本
;辐点间直接连接的单位距离运输成本
。轴点处单位转运成本
;轴点处容量限制
。
采用MATLAB R2016a软件编写,实验环境为Windows 11,处理器为Intel Core i5-12500H CPU @ 2.50 GHz和16GB RAM。SMA算法种群数量为90,迭代次数为500。COA算法种群数量为80,发现者比例为0.7,郊狼组为10,迭代次数为200。
4.3. 仿真结果
第一阶段:首先使用SMA算法求解基于集覆盖的辐点选址模型,在满足辐点包裹服务能力的情况下覆盖全部需求点,选择的辐点数量 [14]
,四舍五入取整数,选择
个辐点服务366个需求点。SMA算法SMA算法对比结果如表1所示,适应度函数的收敛曲线如图3所示:SMA算法约在第250次迭代收敛,平均用时110 s;改进的SMA算法约在第110次迭代收敛,平均用时89 s。改进的SMA算法收敛速度加快且成本降低4%。
![](Images/Table_Tmp.jpg)
Table 1. Comparison of SMA algorithm results
表1. SMA算法结果对比
![](//html.hanspub.org/file/14-2571419x166_hanspub.png?20240314090845429)
Figure 3. Convergence curve of SMA algorithm fitness function
图3. SMA算法适应度函数的收敛曲线
第一阶段最终选择的辐点、对应服务量(包裹量)如表2和图4所示。
![](Images/Table_Tmp.jpg)
Table 2. Selected spokes and corresponding service volume
表2. 选择的辐点以及对应服务量
![](//html.hanspub.org/file/14-2571419x168_hanspub.png?20240314090845429)
Figure 4. Distribution map of spoke location
图4. 辐点选址分布图
第二阶段:根据第一阶段得到的辐点选址方案和对应服务量,生成辐点间同城快递包裹矩阵,作为辐点间日均包裹流量,部分轴点间同城快递包裹矩阵如表3。采用COA算法求解基于复合轴辐式网络的轴点选址模型,在满足轴点容量约束的情况下,选取不同个数的轴点比较成本变化。如表4,对比不同轴点个数下实验结果,随着轴点个数的增加,轴点间规模经济效益增大,运输成本降低,轴点处理成本增加,
时基于复合轴辐式网络的轴点选址成本达到最优,收敛曲线见图5,选择轴点编号为ZD08、ZD11、ZD13、ZD18、ZD23、ZD27、ZD35为最终方案,并且建议开通编号FD44至FD29、FD29至FD54和FD01至FD52三条直达链路,如表5和表6。对应轴点选址方案和直接链路方案分布图如图6:
![](Images/Table_Tmp.jpg)
Table 3. Number of intra-city express packages between spokes
表3. 部分辐点间同城快递包裹数
![](Images/Table_Tmp.jpg)
Table 4. Comparison of results for different number hub
表4. 不同个数的轴点结果对比
![](Images/Table_Tmp.jpg)
Table 5. Hub location scheme when p = 7
表5.
时轴点选址方案
![](Images/Table_Tmp.jpg)
Table 6. Spoke direct connection scheme
表6. 辐点直接连接方案
![](//html.hanspub.org/file/14-2571419x172_hanspub.png?20240314090845429)
Figure 5. Convergence curve of COA algorithm fitness function
图5. COA算法适应度函数的收敛曲线
![](//html.hanspub.org/file/14-2571419x173_hanspub.png?20240314090845429)
Figure 6. Hub location and spoke direct link scheme when
图6.
轴点选址方案和直接链路方案
方案对比:与基于纯轴辐网络的轴点选址方案对比,结果如表7所示:相比纯轴辐网络选址方案,基于复合轴辐式网络的轴点选址方案除了运输成本增加−0.4%,总成本优化了4.4%,轴点固定成本优化了12.5%,轴点中转处理成本优化了6.2%,轴点的平均利用率提高9.3%。相比于直达式物流网络,总成本 = 辐点间平均距离*单位距离运输成本*包裹总数,辐点间平均距离11.88 km,单位距离运输成本参考公路单位运输成本0.45元/件次 公里,包裹总数为65484件,则直通式物流网络运输成本 = 11.88 × 0.45 × 65484 = 350077元,成本优化了52.6%。结果表明:基于复合轴辐式网络的轴点选址模型,在考虑容量限制的同时,减少分拣成本和轴点固定成本,并且提高轴点平均利用率。
![](Images/Table_Tmp.jpg)
Table 7. Different hub location scheme comparison
表7. 不同轴点选址方案对比
5. 结论
电商蓬勃发展,同城物流市场快速扩张,同城快递需求与日俱增,合理的快递枢纽布局尤为重要。同时,由于快递枢纽节点存在容量限制和一定的拥堵概率,必要时考虑开通辐点间直达链路以缓解枢纽处拥堵情况。对此,本文建立了复合轴辐式两阶段同城快递枢纽选择模型,旨在对同城快递枢纽选址提供合理建议。第一阶段,自顾客“需求点”角度出发,考虑辐点容量和固定运行成本,以最小运行成本为优化目标,基于集覆盖问题建立辐点选址模型,加入tent混沌、t分布变异算子等改进策略改进SMA算法并进行求解,得到辐点选址方案和对应需求点。第二阶段,自快递“企业”角度出发,考虑轴点容量和固定运行成本,允许辐点之间直接链路连接,以最小运行成本为优化目标,基于复合轴辐式网络建立轴点选址模型,采用COA算法进行求解,得到轴点选址方案和对应辐点。算例仿真模拟部分,以上海市某快递企业为例,最终优化成本4%,提高轴点平均利用率9.3%,验证了模型和算法的有效性。此外,研究存在一些不足之处。在构建复合轴辐式两阶段同城快递选址模型时,需求点包裹量采用日均同城快递包裹数与常住人口数量进行计算,没有考虑到需求不确定的情况。未来的研究可以针对同城快递包裹数量进行需求预测,或者考虑不确定需求情况下同城快递网络枢纽选址问题。
基金项目
国家自然科学基金(72174121)。
附录1
附录2
附录3