考虑设施规模决策的两级选址-路径优化

doi:10.11772/j.issn.1001-9081.2023101515

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (11): 3513-3520.DOI: 10.11772/j.issn.1001-9081.2023101515

考虑设施规模决策的两级选址-路径优化

冷琴¹^,², 毛政元¹^,²()

^1.福州大学数字中国研究院（福建），福州 350108
^2.空间数据挖掘与信息共享教育部重点实验室（福州大学），福州 350116

收稿日期:2023-11-10 修回日期:2024-01-21 接受日期:2024-01-26 发布日期:2024-11-13 出版日期:2024-11-10
通讯作者: 毛政元
作者简介:冷琴（1997—），女，江西德安人，硕士研究生，主要研究方向：智能算法、路径规划
基金资助:
福建省交通运输科技项目(XY202302)

Two echelon location-routing optimization considering facility sizing decision

Qin LENG¹^,², Zhengyuan MAO¹^,²()

^1.The Academy of Digital China （Fujian），Fuzhou University，Fuzhou Fujian 350108，China
^2.Key Lab of Spatial Data Mining and Information Sharing，Ministry of Education （Fuzhou University），Fuzhou Fujian 350116，China

Received:2023-11-10 Revised:2024-01-21 Accepted:2024-01-26 Online:2024-11-13 Published:2024-11-10
Contact: Zhengyuan MAO
About author:LENG Qin， born in 1997， M. S. candidate. Her research interests include intelligent algorithm， route planning.
Supported by:
Transportation Technology Project of Fujian Province(XY202302)

摘要/Abstract

摘要：

针对目前电商行业基础设施布局和空间利用不合理的问题，提出考虑设施规模决策的两级选址-路径问题（2E-LRP）求解模型。首先，在传统2E-LRP中引入差异性设施规模约束，通过识别客户群设计不同设施规模组合，利用规模弹性变化调整总成本组成，并以最小运营成本为目标建立顾及设施规模弹性变化的2E-LRP模型；其次，提出两阶段混合迭代局部搜索启发式算法求解模型；最后，分析所提模型和优化算法，并以Prodhon等不同数据集为实例进行验证。实验结果表明，所提模型具有针对区域差异和不同数据规模的普适性，且设施规模的弹性变化范围值与总成本呈负相关；与拉格朗日松弛粒度禁忌搜索（LRGTS）等算法的最优成本相比，所提算法对所有算例的最优成本平均值降低了6.67%，可以有效节约运行成本。

关键词: 两级选址-路径问题, 设施规模决策, 偏随机化, 迭代局部搜索, 城市物流

Abstract:

A two Echelon Location-Routing Problem （2E-LRP） solving model considering facility sizing decision was proposed to address the issues of unreasonable infrastructure layout and space utilization in the existing e-commerce industry. Firstly， differential facility sizing constraints were introduced into the traditional 2E-LRP， different combinations of facility sizes were designed by identifying customer base， the total cost composition was adjusted by using changes in size， and a 2E-LRP model considering facility size change with the minimum operating cost as goal was established. Secondly， a two-stage hybrid iterated local search heuristic algorithm was proposed for solving the model. Finally， the performance of the proposed model and optimization algorithm were analyzed and verified with examples in different datasets such as Prodhon. Experimental results show that the proposed model is universal for regional differences and different data sizes， and there is an inverse relationship between the total cost and the change range of facility size. Compared with the optimal costs of algorithms such as Lagrangean Relaxation Granular Tabu Search （LRGTS）， the average value of the optimal cost of the proposed algorithm on all instances is reduced by 6.67%， which can effectively save the operating cost.

Key words: Two Echelon Location-Routing Problem (2E-LRP), facility sizing decision, biased randomization, iterated local search, urban logistics

中图分类号:

TP301.6

冷琴, 毛政元. 考虑设施规模决策的两级选址-路径优化[J]. 计算机应用, 2024, 44(11): 3513-3520.

Qin LENG, Zhengyuan MAO. Two echelon location-routing optimization considering facility sizing decision[J]. Journal of Computer Applications, 2024, 44(11): 3513-3520.

图/表 11

图1 2E-LRP解的图形表示

Fig. 1 Graph of solution for 2E-LRP

表1 符号说明

Tab. 1 Symbol description

变量		含义
普通变量	$N 1$	第一梯队节点集合， $N 1 = C ⋃ J$
	$N 2$	第二梯队节点集合， $N 2 = J ⋃ I$
	$K 1$	第一梯队车辆集合
	$K 2$	第二梯队车辆集合
	$S$	第二梯队设施可选大小集合
	$u 1$	第一梯队运输过程中使用单辆车的固定成本
	$u 2$	第二梯队运输过程中使用单辆车的固定成本
	$U 1$	第一梯队配送车辆容量上限
	$U 2$	第二梯队配送车辆容量上限
	$f j 1$	一个中转站开放的固定成本， $j ∈ J$
	$f j s 2$	大小为 $s$ 的中转站 $j$ 可变开放成本， $j ∈ J, s ∈ S$
	$o j s$	大小为 $s$ 的中转站 $j$ 的可用尺寸， $j ∈ J, s ∈ S$
	$q i$	终端i的需求， $i ∈ I$
	$c i j 1$	第一梯队服务两点之间的成本， $i, j ∈ N 1$
	$c i j 2$	第二梯队服务两点之间的成本， $i, j ∈ N 2$
决策变量	$x i j a$	$x i j a = 1$ 表示由中心点 $a ∈ C$ 出发的第一梯队车辆连接点i和点j， $i, j ∈ N 1$ ；否则 $x i j a = 0$
	$y i j b$	$y i j b = 1$ 表示由中转站 $b ∈ J$ 出发的第二梯队车辆连接点i和点j， $i, j ∈ N 2$ ；否则 $y i j b = 0$
	$z j s$	$z j s = 1$ 表示备选中转站 $j ∈ J$ 开放，且可用大小为 $s ∈ S$ ；否则 $z j s = 0$
	$h i j$	$h i j = 1$ 表示需求点 $i ∈ I$ 分配给中转站 $j ∈ J$ ；否则 $h i j = 0$
	$w j k 1$	$w j k 1$ 表示车辆 $k 1 ∈ K 1$ 服务完开放设施 $j ∈ J$ 的累计重量
	$w i k 2$	$w i k 2$ 表示车辆 $k 2 ∈ K 2$ 服务完需求点 $i ∈ I$ 的累计重量

表1 符号说明

Tab. 1 Symbol description

变量		含义
普通变量	$N 1$	第一梯队节点集合， $N 1 = C ⋃ J$
	$N 2$	第二梯队节点集合， $N 2 = J ⋃ I$
	$K 1$	第一梯队车辆集合
	$K 2$	第二梯队车辆集合
	$S$	第二梯队设施可选大小集合
	$u 1$	第一梯队运输过程中使用单辆车的固定成本
	$u 2$	第二梯队运输过程中使用单辆车的固定成本
	$U 1$	第一梯队配送车辆容量上限
	$U 2$	第二梯队配送车辆容量上限
	$f j 1$	一个中转站开放的固定成本， $j ∈ J$
	$f j s 2$	大小为 $s$ 的中转站 $j$ 可变开放成本， $j ∈ J, s ∈ S$
	$o j s$	大小为 $s$ 的中转站 $j$ 的可用尺寸， $j ∈ J, s ∈ S$
	$q i$	终端i的需求， $i ∈ I$
	$c i j 1$	第一梯队服务两点之间的成本， $i, j ∈ N 1$
	$c i j 2$	第二梯队服务两点之间的成本， $i, j ∈ N 2$
决策变量	$x i j a$	$x i j a = 1$ 表示由中心点 $a ∈ C$ 出发的第一梯队车辆连接点i和点j， $i, j ∈ N 1$ ；否则 $x i j a = 0$
	$y i j b$	$y i j b = 1$ 表示由中转站 $b ∈ J$ 出发的第二梯队车辆连接点i和点j， $i, j ∈ N 2$ ；否则 $y i j b = 0$
	$z j s$	$z j s = 1$ 表示备选中转站 $j ∈ J$ 开放，且可用大小为 $s ∈ S$ ；否则 $z j s = 0$
	$h i j$	$h i j = 1$ 表示需求点 $i ∈ I$ 分配给中转站 $j ∈ J$ ；否则 $h i j = 0$
	$w j k 1$	$w j k 1$ 表示车辆 $k 1 ∈ K 1$ 服务完开放设施 $j ∈ J$ 的累计重量
	$w i k 2$	$w i k 2$ 表示车辆 $k 2 ∈ K 2$ 服务完需求点 $i ∈ I$ 的累计重量

图2 混合启发式算法流程

Fig. 2 Flow of hybrid heuristic algorithm

表2 算法参数说明

Tab. 2 Algorithm parameter description

参数	取值
设施组合数量	40
偏概率β	［0.05，0.8］
冷却因子 $K$	0.994
初始温度 $T 0$	100
第一阶段迭代次数	2 000
第二阶段迭代次数	300

表2 算法参数说明

Tab. 2 Algorithm parameter description

参数	取值
设施组合数量	40
偏概率β	［0.05，0.8］
冷却因子 $K$	0.994
初始温度 $T 0$	100
第一阶段迭代次数	2 000
第二阶段迭代次数	300

表3 P20-5-1上的3种模型结果对比

Tab. 3 Result comparison of three models on P20-5-1

模型	选址成本	路径成本	总成本
模型A	25 549	52 089	92 638
模型B	21 158	53 087	89 245
模型C	15 786	51 600	82 386
Gap_BA/%	-17.19	1.92	-3.66
Gap_CA/%	-38.21	-0.94	-11.07

图3 P20-5-1上3种模型的优化结果

Fig. 3 Optimization results of three models on P20-5-1

表 4 Prodhon实例上的结果比较

Tab. 4 Result comparisons on Prodhon instances

实例	最优解	r=0				r=0.25				CPU 时间/s
实例	最优解	最优收敛解	Gap_best/%	平均收敛解	Gap_avg/%	最优收敛解	Gap_best/%	平均收敛解	Gap_avg/%	CPU 时间/s
平均值			0.35		1.07		-6.67		-5.89	603.62
20-5-1	91 062	89 245	-2.04	90 399	-0.73	82 386	-9.53	82 988	-8.87	11.15
20-5-1b	63 094	63 487	0.62	63 548	0.72	50 425	-20.08	50 498	-19.96	10.85
20-5-2	86 118	86 866	0.87	87 150	1.20	76 426	-11.25	76 594	-11.06	12.21
20-5-2b	60 838	60 838	0.00	61 328	0.81	49 162	-19.19	49 905	-17.97	13.40
50-5-1	134 904	134 227	-0.50	134 530	-0.28	127 548	-5.45	128 741	-4.57	71.35
50-5-1b	102 286	102 155	-0.13	102 971	0.67	100 705	-1.55	102 146	-0.14	89.77
50-5-2	132 364	136 228	2.92	136 228	2.92	125 019	-5.55	127 644	-3.57	99.74
50-5-2b	110 630	117 352	6.08	117 766	6.45	104 428	-5.61	105 879	-4.29	71.79
50-5-2BIS	122 725	123 198	0.39	124 104	1.12	116 705	-4.91	117 357	-4.37	114.39
50-5-2bBIS	105 776	108 327	2.41	110 043	4.03	85 404	-19.26	85 809	-18.88	50.95
50-5-3	128 379	129 677	1.01	130 479	1.64	128 927	0.43	129 109	0.57	42.42
50-5-3b	104 006	105 862	1.78	106 837	2.72	106 723	2.61	107 050	2.93	97.07
100-5-1	321 255	319 687	-0.49	323 225	0.61	294 085	-8.46	297 411	-7.42	671.15
100-5-1b	258 205	258 612	0.16	258 612	0.16	225 276	-12.75	228 214	-11.62	599.09
100-5-2	234 179	235 211	0.44	235 215	0.44	236 484	0.98	236 886	1.16	336.37
100-5-2b	195 426	197 322	0.97	197 440	1.03	197 142	0.88	197 656	1.14	382.25
100-5-3	245 944	246 535	0.24	250 204	1.73	245 535	-0.17	245 535	-0.17	282.91
100-5-3b	195 254	197 277	1.04	197 277	1.04	196 480	0.63	196 480	0.63	353.47
100-10-1	358 939	346 980	-3.33	351 131	-2.18	339 604	-5.39	344 485	-4.03	176.56
100-10-1b	302 584	292 685	-3.27	295 019	-2.50	272 532	-9.93	274 800	-9.18	181.14
100-10-2	308 884	293 585	-4.95	298 702	-3.30	271 142	-12.22	273 932	-11.32	220.04
100-10-2b	264 984	277 001	4.53	278 148	4.97	230 742	-12.92	233 276	-11.97	200.94
100-10-3	318 209	303 002	-4.78	308 162	-3.16	285 744	-10.20	289 154	-9.13	237.24
100-10-3b	267 019	261 728	-1.98	265 880	-0.43	233 935	-12.39	236 911	-11.28	285.44
200-10-1	554 598	566 114	2.08	568 057	2.43	540 977	-2.46	545 551	-1.63	1 251.14
200-10-1b	453 286	461 081	1.72	466 129	2.83	431 642	-4.77	441 582	-2.58	1 961.36
200-10-2	502 173	512 867	2.13	512 867	2.13	501 458	-0.14	501 909	-0.05	2 301.93
200-10-2b	426 171	437 270	2.60	443 633	4.10	416 859	-2.19	420 059	-1.43	3 044.64
200-10-3	538 821	537 208	-0.30	538 714	-0.02	511 414	-5.09	513 664	-4.67	2 745.62
200-10-3b	418 800	420 099	0.31	423 081	1.02	401 239	-4.19	405 858	-3.09	2 192.23

表 4 Prodhon实例上的结果比较

Tab. 4 Result comparisons on Prodhon instances

实例	最优解	r=0				r=0.25				CPU 时间/s
实例	最优解	最优收敛解	Gap_best/%	平均收敛解	Gap_avg/%	最优收敛解	Gap_best/%	平均收敛解	Gap_avg/%	CPU 时间/s
平均值			0.35		1.07		-6.67		-5.89	603.62
20-5-1	91 062	89 245	-2.04	90 399	-0.73	82 386	-9.53	82 988	-8.87	11.15
20-5-1b	63 094	63 487	0.62	63 548	0.72	50 425	-20.08	50 498	-19.96	10.85
20-5-2	86 118	86 866	0.87	87 150	1.20	76 426	-11.25	76 594	-11.06	12.21
20-5-2b	60 838	60 838	0.00	61 328	0.81	49 162	-19.19	49 905	-17.97	13.40
50-5-1	134 904	134 227	-0.50	134 530	-0.28	127 548	-5.45	128 741	-4.57	71.35
50-5-1b	102 286	102 155	-0.13	102 971	0.67	100 705	-1.55	102 146	-0.14	89.77
50-5-2	132 364	136 228	2.92	136 228	2.92	125 019	-5.55	127 644	-3.57	99.74
50-5-2b	110 630	117 352	6.08	117 766	6.45	104 428	-5.61	105 879	-4.29	71.79
50-5-2BIS	122 725	123 198	0.39	124 104	1.12	116 705	-4.91	117 357	-4.37	114.39
50-5-2bBIS	105 776	108 327	2.41	110 043	4.03	85 404	-19.26	85 809	-18.88	50.95
50-5-3	128 379	129 677	1.01	130 479	1.64	128 927	0.43	129 109	0.57	42.42
50-5-3b	104 006	105 862	1.78	106 837	2.72	106 723	2.61	107 050	2.93	97.07
100-5-1	321 255	319 687	-0.49	323 225	0.61	294 085	-8.46	297 411	-7.42	671.15
100-5-1b	258 205	258 612	0.16	258 612	0.16	225 276	-12.75	228 214	-11.62	599.09
100-5-2	234 179	235 211	0.44	235 215	0.44	236 484	0.98	236 886	1.16	336.37
100-5-2b	195 426	197 322	0.97	197 440	1.03	197 142	0.88	197 656	1.14	382.25
100-5-3	245 944	246 535	0.24	250 204	1.73	245 535	-0.17	245 535	-0.17	282.91
100-5-3b	195 254	197 277	1.04	197 277	1.04	196 480	0.63	196 480	0.63	353.47
100-10-1	358 939	346 980	-3.33	351 131	-2.18	339 604	-5.39	344 485	-4.03	176.56
100-10-1b	302 584	292 685	-3.27	295 019	-2.50	272 532	-9.93	274 800	-9.18	181.14
100-10-2	308 884	293 585	-4.95	298 702	-3.30	271 142	-12.22	273 932	-11.32	220.04
100-10-2b	264 984	277 001	4.53	278 148	4.97	230 742	-12.92	233 276	-11.97	200.94
100-10-3	318 209	303 002	-4.78	308 162	-3.16	285 744	-10.20	289 154	-9.13	237.24
100-10-3b	267 019	261 728	-1.98	265 880	-0.43	233 935	-12.39	236 911	-11.28	285.44
200-10-1	554 598	566 114	2.08	568 057	2.43	540 977	-2.46	545 551	-1.63	1 251.14
200-10-1b	453 286	461 081	1.72	466 129	2.83	431 642	-4.77	441 582	-2.58	1 961.36
200-10-2	502 173	512 867	2.13	512 867	2.13	501 458	-0.14	501 909	-0.05	2 301.93
200-10-2b	426 171	437 270	2.60	443 633	4.10	416 859	-2.19	420 059	-1.43	3 044.64
200-10-3	538 821	537 208	-0.30	538 714	-0.02	511 414	-5.09	513 664	-4.67	2 745.62
200-10-3b	418 800	420 099	0.31	423 081	1.02	401 239	-4.19	405 858	-3.09	2 192.23

图4 r值与总成本的关系

Fig. 4 Relationship between total cost and r

图5 部分实例总成本相对于r值的变化

Fig. 5 Total cost varying with r on some instances

图6 福州案例中总成本相对于r值的变化

Fig. 6 Total cost varying with r on Fuzhou instance

表 5 福州案例中r值变化与总成本结果

Tab. 5 Total cost varying with r on Fuzhou instance

r	选址成本	路径成本	总成本
0	473 734	13 833	544 473
0.05	444 982	16 403	536 741
0.1	433 653	15 536	517 367
0.15	406 692	17 719	503 014
0.2	403 974	18 026	492 185
0.25	386 318	15 849	468 642

参考文献 19

1	MARA S T W， KUO R J， ASIH A M S. Location-routing problem： a classification of recent research［J］. International Transactions in Operational Research， 2021， 28（6）：2941-2983.
2	WU Y， QURESHI A G， YAMADA T. Adaptive large neighborhood decomposition search algorithm for multi-allocation hub location routing problem［J］. European Journal of Operational Research， 2022， 302（3）： 1113-1127.
3	DARVISH M， ARCHETTI C， COELHO L C， et al. Flexible two-echelon location routing problem［J］. European Journal of Operational Research， 2019， 277（3）： 1124-1136.
4	陈希琼，胡大伟，王宁. 多目标同时取送货选址-路径问题的多起点变邻域搜索算法［J］. 控制理论与应用， 2022， 39（7）： 1229-1241.
	CHEN X Q， HU D W， WANG N. A multi-start variable neighborhood search for multi-objective location routing problem with simultaneous pickup and delivery［J］. Control Theory and Applications， 2022， 39（7）： 1229-1241.
5	QUINTERO-ARAUJO C L， GUIMARANS D， JUAN A. A simheuristic algorithm for the capacitated location routing problem with stochastic demands［J］. Journal of Simulation， 2021， 15（3）： 217-234.
6	TORDECILLA R D， PANADERO J， JUAN A A， et al. A simheuristic algorithm for the location routing problem with facility sizing decisions and stochastic demands［C］// Proceedings of the 2020 Winter Simulation Conference. Piscataway： IEEE， 2020： 1265-1275.
7	TORDECILLA R D， MONTOYA-TORRES J R， QUINTERO-ARAUJO C L， et al. The location routing problem with facility sizing decisions［J］. International Transactions in Operational Research， 2023， 30（2）： 915-945.
8	MOHAMED I BEN， KLIBI W， SADYKOV R， et al. The two-echelon stochastic multi-period capacitated location-routing problem［J］. European Journal of Operational Research， 2023， 306（2）： 645-667.
9	AMIRI M， AMIN S H， TAVAKKOLI-MOGHADDAM R. A Lagrangean decomposition approach for a novel two-echelon node-based location-routing problem in an offshore oil and gas supply chain［J］. Transportation Research Part E： Logistics and Transportation Review， 2019， 128： 96-114.
10	DAI Z， AQLAN F， GAO K， et al. A two-phase method for multi-echelon location-routing problems in supply chains［J］. Expert Systems with Applications， 2019， 115： 618-634.
11	CHEN Y， ZHAO Q， WANG W， et al. Mixed multi-echelon location routing problem with differentiated intermediate depots［J］. Computers and Industrial Engineering， 2023， 177： No.109026.
12	杨屹夫，孙冰，马艳芳，等. 服务差异二级选址路径问题及大邻域搜索算法［J］. 计算机工程与应用， 2023， 59（3）： 282-292.
	YANG Y F， SUN B， MA Y F， et al. Adaptive large neighborhood search algorithm for two-echelon location-routing problem with different service modes［J］. Computer Engineering and Applications， 2023， 59（3）： 282-292.
13	JUAN A A， FAULIN J， JORBA J， et al. On the use of Monte Carlo simulation， cache and splitting techniques to improve the Clarke and Wright savings heuristics［J］. Journal of the Operational Research Society， 2011， 62（6）： 1085-1097.
14	JUAN A A， CORLU C G， TORDECILLA R D， et al. On the use of biased-randomized algorithms for solving non-smooth optimization problems［J］. Algorithms， 2020， 13（1）： No.8.
15	GRASAS A， JUAN A A， FAULIN J， et al. Biased randomization of heuristics using skewed probability distributions： a survey and some applications［J］. Computers and Industrial Engineering， 2017， 110： 216-228.
16	ZHOU L， LIN Y， WANG X， et al. Model and algorithm for bilevel multisized terminal location-routing problem for the last mile delivery［J］. International Transactions in Operational Research， 2019， 26（1）： 131-156.
17	HAJGHANI M， FORGHANI M A， HEIDARI A， et al. A two-echelon location routing problem considering sustainability and hybrid open and closed routes under uncertainty［J］. Heliyon， 2023， 9（3）： No.e14258.
18	NGUYEN V P， PRINS C， PRODHON C. Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking［J］. European Journal of Operational Research， 2012， 216（1）： 113-126.
19	PRINS C， PRODHON C， RUIZ A， et al. Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic［J］. Transportation Science， 2007， 41（4）： 431-541.

[1]	刘育良, 陈淮莉. 负载影响下纯电动汽车配送路径规划及充电策略[J]. 计算机应用, 2020, 40(10): 2831-2837.
[2]	宋婷, 陈矛, 吴超, 张龚钊. 基于多类迭代局部搜索的自动化排课算法[J]. 计算机应用, 2019, 39(6): 1760-1765.
[3]	欧阳秋萍, 李杰, 沈林成. 考虑3G/4G网络特性的多无人机环保监测任务调度[J]. 计算机应用, 2016, 36(3): 871-877.

考虑设施规模决策的两级选址-路径优化

Two echelon location-routing optimization considering facility sizing decision

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 19

相关文章 3

编辑推荐

Metrics