基于分类垃圾收运时效性的多周期多车舱路径优化研究

doi:10.16381/j.cnki.issn1003-207x.2023.0050

摘要/Abstract

摘要：

随着城市生活垃圾量的急剧增加，分类收运正逐渐成为垃圾分类政策有效实施的关键。本文针对分类垃圾收运的时效性、收运车辆的多舱性等特征，以总成本最小为目标，构建了多周期多车舱垃圾分类收运车辆路径优化模型。根据问题特性，提出了一种基于两阶段的改进自适应大邻域搜索算法。其中，设计了周期相似算子以调整垃圾收运周期，联合收运插入算子以优化周期内多舱车收运路径。最后，通过不同规模算例和实际案例进行对比分析，验证了模型和算法的有效性及高效性。

关键词: 分类垃圾收运, 多周期, 多车舱, 自适应大邻域搜索算法

Abstract:

With the acceleration of urbanization and the enhancement of material living standards， abundant human activities have generated massive urban domestic waste， which has brought severe challenges and threats to sustainable social development and human health. Consequently， many municipal governments in China have successively promulgated policies to promote the implementation of waste sorting. Especially， sorted-waste collection， as an indispensable part of waste sorting， has attracted more attention from the academic community over recent years.In this paper， a novel multi-period sorted-waste collection routing optimization problem for multi-compartment vehicles （MPMCVRP） is proposed， with the objective of minimizing cost. Specially， the MPMCVRP takes into account the advantages of heterogeneous fleets and the difference in storage times between distinct wastes due to their unique properties， thereby making the route planning more realistic. To solve the proposed model， an extended two-stage adaptive large neighborhood search algorithm （EALNS） is developed. In the EALNS， a new period similarity operator is designed to adjust the waste collection period， and a new joint collection insertion operator is presented to optimize the within-period multi-compartment vehicle collection path.To confirm the effectiveness of the EALNS， it is compared with CPLEX on small-scale benchmarks， followed by comparison with the classical heuristic algorithms on medium- and large-scale benchmarks. Furthermore， a series of comparison experiments is implemented to demonstrate the significance of the MPMCVRP from the perspective of employing multi-compartment vehicles and multi-period joint planning. Finally， the proposed MPMCVRP and EALNS are used in a real case to confirm their practicability. In summary， a good foundation for further research is provided.

Key words: sorted-waste collection, multi-period, multi-compartment, adaptive large neighborhood search algorithm

中图分类号:

F252.5

肖建华,张文雪,潘钰雅, 等. 基于分类垃圾收运时效性的多周期多车舱路径优化研究[J]. 中国管理科学, 2025, 33(10): 86-97.

Jianhua Xiao,Wenxue Zhang,Yuya Pan, et al. A Multi-period Multi-compartment Vehicle Routing Problem for Sorted-waste Collection with Timeliness[J]. Chinese Journal of Management Science, 2025, 33(10): 86-97.

图/表 13

图1

图2

表1

表2

垃圾比例系数区间及时效性"

垃圾种类数	垃圾类型	比例系数区间	时效性
2	$P 1$	[3, 9]	1周期
2	$P 2$	[3, 9]	2周期
3	$P 1$	[3, 9]	1周期
	$P 2$	[3, 9]	2周期
	$P 3$	[0, 3]	3周期

表2

表3

表4

小规模算例求解结果"

算例编号	CPLEX		EALNS			Gap（%）
算例编号	$C b e s t C P L E X$	$T C P L E X$	$C b e s t E A L N S$	$C a v g E A L N S$	$T E A L N S$	$G a p b e s t$	$G a p a v g$
4-2-4-1	1027	7	1027	1027	3.5	0	0
4-2-4-2	2046	237	2046	2046	7.4	0	%
4-2-4-3	1733	541	1733	1733	6.6	0	0
4-2-4-4	1896	88	1896	1896	7.6	0	0
4-2-4-5	1156	9	1156	1156	4.3	0	0
5-2-4-1	1801	>7200	1801	1826	5.6	0	-1.4
5-2-4-2	1785	>7200	1785	1785	6.5	0	0
5-2-4-3	1510	>7200	1510	1510	7.6	0	0
5-2-4-4	1484	1086	1484	1484	4.8	0	0
5-2-4-5	1896	>7200	1896	1896	6.7	0	0

表4

表5

中大规模算例求解结果"

算例编号	VNS-1			VNS-2			VNS-3			EALNS			Gap（%）
算例编号	$C b e s t V N S - 1$	$C a v g V N S - 1$	$R S D$ （%）	$C b e s t V N S - 2$	$C a v g V N S - 2$	$R S D$ （%）	$C b e s t V N S - 3$	$C a v g V N S - 3$	$R S D$ （%）	$C b e s t E A L N S$	$C a v g E A L N S$	$R S D$ （%）	$G a p b e s t 1$	$G a p a v g 1$	$G a p b e s t 2$	$G a p a v g 2$	$G a p b e s t 3$	$G a p a v g 3$
15-3-3-1	2747	2814	1.03	2320	2325	0.11	2543	2567	0.60	2240	2299	1.51	22.6	22.4	3.6	1.1	13.54	11.65
15-3-3-2	2472	2532	1.39	2324	2333	0.16	2325	2325	0.00	2324	2328	0.40	6.4	8.8	0.0	0.2	0.04	-0.13
15-3-3-3	2837	2895	1.12	2353	2375	0.46	2420	2420	0.00	2414	2430	0.61	17.5	19.1	-2.5	-2.3	0.25	-0.41
15-3-3-4	2832	2942	1.59	2531	2532	0.12	2815	2815	0.00	2540	2543	0.17	11.5	15.7	-0.4	-0.4	10.82	10.69
15-3-3-5	2489	2519	0.83	2094	2095	0.11	2407	2432	1.41	2144	2144	0.00	16.1	17.5	-2.3	-2.3	12.26	13.44
20-3-3-1	2877	2933	0.80	2892	2907	0.33	2932	2961	0.64	2786	2861	1.61	3.3	2.5	3.8	1.6	5.26	3.51
20-3-3-2	2646	2767	1.53	2657	2725	2.67	2825	2915	1.08	2628	2635	0.50	0.7	5.0	1.1	3.4	7.51	10.64
20-3-3-3	2928	2999	0.89	3005	3097	1.60	2987	2994	0.13	2915	2925	0.81	0.4	2.5	3.1	5.9	2.47	2.37
20-3-3-4	2689	2798	1.26	2750	2758	0.41	2788	2788	0.01	2684	2684	0.00	0.2	4.2	2.5	2.0	3.87	3.89
20-3-3-5	2890	3017	1.55	2958	3047	1.57	2905	2905	0.00	2889	2900	0.94	0.0	4.0	2.4	5.1	0.55	0.17
20-3-5-1	7489	7900	1.99	7636	7719	0.62	7547	7655	1.41	6406	6563	1.46	16.9	20.4	19.2	17.6	17.82	16.64
20-3-5-2	7360	7466	0.88	7089	7128	0.39	7053	7086	0.49	6173	6313	1.56	19.2	18.3	14.8	12.9	14.26	12.25
20-3-5-3	7571	7744	0.98	7808	7903	0.83	7953	7953	0.00	6561	6712	1.61	15.4	15.4	19.0	17.7	21.21	18.49
20-3-5-4	7050	7169	0.61	7630	7633	0.02	7153	7301	1.93	5851	6077	1.88	20.5	18.0	30.4	25.6	22.24	20.15
20-3-5-5	6604	6773	0.94	6610	6645	0.47	6572	6644	1.00	5877	5976	0.94	12.4	13.3	12.5	11.2	11.82	11.17
30-3-3-1	4650	4822	2.15	3699	4544	6.28	4294	4325	0.89	3502	3552	1.01	32.8	35.8	5.6	27.9	22.62	21.76
30-3-3-2	5675	5867	2.45	4764	5061	6.27	5496	5506	0.14	4531	4625	2.40	25.2	26.9	5.1	9.4	21.29	19.04
30-3-3-3	4196	4454	3.04	3587	4078	4.05	4116	4147	1.20	3257	3280	0.86	28.8	35.8	10.1	24.3	26.36	26.42
30-3-3-4	4489	4768	2.44	3703	4293	6.69	4666	4677	0.32	3489	3581	2.39	28.7	33.1	6.1	19.9	33.74	30.62
30-3-3-5	4614	4955	2.69	4531	4547	0.39	4473	4515	1.19	3756	3865	2.71	22.8	28.2	20.6	17.6	19.10	16.82
30-3-5-1	7745	7830	2.72	9212	9163	0.37	8621	8674	0.84	7741	8034	2.36	0.1	-2.5	19.0	14.1	11.37	7.97
30-3-5-2	11036	11409	1.57	10576	10650	0.56	10831	10858	0.32	8949	9340	2.87	23.3	22.2	18.2	14.0	21.03	16.25
30-3-5-3	10603	10958	1.81	9502	9578	0.37	9096	9306	1.49	8420	8712	1.68	25.9	25.8	12.9	9.9	8.03	6.82
30-3-5-4	11116	11367	1.57	10575	10693	0.89	10606	10626	0.10	8987	9195	2.02	23.7	23.6	17.7	16.3	18.02	15.56
30-3-5-5	9532	10063	2.87	9613	9842	1.02	9630	9663	0.19	8118	8346	1.71	17.4	20.6	18.4	17.9	18.63	15.78
50-2-3-1	5647	5706	2.36	6764	6932	2.02	7154	7168	0.25	5596	5701	2.02	0.9	0.1	20.9	21.6	27.85	25.74
50-2-3-2	5567	5634	2.24	6368	6492	0.81	6451	6481	0.67	5405	5559	1.60	3.0	1.3	17.8	16.8	19.36	16.58
50-2-3-3	5678	5790	2.35	6373	6463	0.62	6599	6608	0.04	5177	5474	2.82	9.7	5.8	23.1	18.1	27.47	20.71
50-2-3-4	5890	5987	2.10	6727	6732	0.06	6476	6487	0.27	5685	5834	1.44	3.6	2.6	18.3	15.4	13.92	11.20
50-2-3-5	5002	5104	2.58	5841	5971	0.78	5923	5923	0.00	4967	5113	2.79	0.7	-0.2	17.6	16.8	19.24	15.84

表5

表6

图3

图4

图5

表7

垃圾收运计划"

周期	车型	车辆路线	收运垃圾种类
$T 1$	多舱车	0, 10, 3, 18, 16, 9, 17, 23, 2, 11, 20, 26, 15, 1, 19, 14, 4, 8, 12, 0	$P 3$ 、 $P 4$
	多舱车	0, 22, 21, 5, 7, 6, 13, 25, 27, 28, 24, 29, 30, 0	$P 1$ 、 $P 3$
	多舱车	0, 1, 15, 26, 20, 11, 2, 23, 17, 18, 16, 21, 22, 0	$P 1$ 、 $P 2$ 、 $P 4$
	多舱车	0, 30, 29, 24, 28, 27, 25, 3, 10, 13, 6, 7, 5, 12, 8, 4, 14, 19, 0	$P 2$ 、 $P 4$
	单舱车	0, 30, 24, 3, 10, 13, 7, 18, 23, 17, 9, 19, 14, 4, 8, 12, 21, 0	$P 1$
$T 2$	单舱车	0, 22, 21, 6, 13, 10, 3, 7, 5, 16, 18, 17, 23, 2, 9, 26, 20, 11, 15, 1, 19, 14, 4, 8, 12, 0	$P 1$
$T 2$	单舱车	0, 30, 29, 24, 28, 27, 25, 0	$P 1$
	多舱车	0, 16, 18, 17, 2, 0	$P 3$ 、 $P 4$
$T 3$	多舱车	0, 19, 14, 4, 12, 5, 7, 10, 3, 27, 28, 24, 30, 0	$P 1$ 、 $P 2$
	多舱车	0, 22, 21, 6, 16, 18, 17, 23, 2, 9, 26, 1, 0	$P 1$ 、 $P 2$
	多舱车	0, 30, 29, 24, 28, 27, 25, 3, 10, 13, 7, 6, 21, 12, 8, 9, 26, 20, 11, 15, 1, 0	$P 1$ 、 $P 3$
	单舱车	0, 4, 14, 19, 1, 15, 20, 11, 23, 9, 26, 8, 12, 0	$P 4$
	单舱车	0, 22, 21, 5, 7, 6, 13, 10, 3, 30, 29, 24, 28, 27, 25, 0	$P 4$
	多舱车	0, 19, 14, 4, 12, 5, 7, 10, 3, 27, 28, 24, 30, 0	$P 1$ 、 $P 2$
$T 4$	多舱车	0, 19, 14, 4, 8, 12, 5, 6, 13, 10, 25, 24, 29, 0	$P 1$ 、 $P 2$ 、 $P 3$ 、 $P 4$
	多舱车	0, 22, 21, 16, 18, 17, 23, 2, 9, 11, 20, 15, 4, 0	$P 2$ 、 $P 3$
	多舱车	0, 6, 13, 10, 7, 18, 16, 9, 26, 20, 11, 15, 1, 0	$P 1$ 、 $P 4$
	多舱车	0, 22, 21, 17, 2, 23, 3, 27, 28, 30, 0	$P 2$ 、 $P 4$
	多舱车	0, 19, 9, 16, 18, 6, 10, 13, 0	$P 1$ 、 $P 2$
$T 5$	单舱车	0, 13, 10, 3, 25, 27, 28, 24, 29, 30, 0	$P 1$
$T 5$	单舱车	0, 22, 21, 6, 7, 5, 12, 8, 16, 18, 17, 23, 2, 9, 26, 20, 11, 15, 1, 19, 14, 4, 0	$P 1$
总成本		7418

表7

图6

参考文献 25

[1]	李明月，李俐频，左薇，等. 基于GIS与改进蚁群算法的垃圾收运路径规划［J］. 环境工程学报， 2022， 16（7）： 2388-2396.
	Li M Y， Li L P， Zuo W， et al. Garbage collection and transportation path planning based on GIS and improved ant colony algorithm［J］. Chinese Journal of Environmental Engineering， 2022， 16（7）： 2388-2396.
[2]	牟能冶，程驰尧，蒋尔伟，等. 基于多车型多行程的城市生活垃圾分类运输路径优化［J］. 安全与环境学报， 2022， 22（4）： 2199-2208.
	Mu N Y， Cheng C Y， Jiang E W， et al. Urban solid waste classification and transportation path optimization based on multi-vehicle and multi-journey［J］. Journal of Safety and Environment， 2022， 22（4）： 2199-2208.
[3]	Reed M， Yiannakou A， Evering R. An ant colony algorithm for the multi-compartment vehicle routing problem［J］. Applied Soft Computing， 2014， 15： 169-176.
[4]	Henke T， Speranza M G， Wäscher G. The multi-compartment vehicle routing problem with flexible compartment sizes［J］. European Journal of Operational Research， 2015， 246（3）： 730-743.
[5]	Henke T， Speranza M G， Wäscher G. A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes［J］. Annals of Operations Research， 2019， 275（2）： 321-338.
[6]	Erdem M. Optimisation of sustainable urban recycling waste collection and routing with heterogeneous electric vehicles［J］. Sustainable Cities and Society， 2022， 80： 103785.
[7]	Yang J， Tao F， Zhong Y. Dynamic routing for waste collection and transportation with multi-compartment electric vehicle using smart waste bins［J］. Waste Management & Research， 2022， 40（8）： 1199-1211.
[8]	孙丽君，周雅娴，滕玥，等. 多车舱车辆路径问题的研究现状与发展［J］.系统工程理论与实践，2021，41（6）： 1535-1546.
	Sun L J， Zhou Y X， Teng Y， et al. Multi-compartment vehicle routing problem： Status and perspectives［J］. Systems Engineering-Theory & Practice， 2021， 41（6）： 1535-1546.
[9]	Ostermeier M， Henke T， Hübner A， et al. Multi-compartment vehicle routing problems： State-of-the-art， modeling framework and future directions［J］. European Journal of Operational Research， 2021， 292（3）： 799-817.
[10]	闫芳，张燕红，柴福良. 垃圾分类背景下城市生活垃圾多级转运网络优化［J］. 重庆师范大学学报（自然科学版）， 2022， 39（4）： 1-11.
	Yan F， Zhang Y H， Chai F L. Multi-stage transport network optimization of considering the municipal solid waste classification［J］. Journal of Chongqing Normal University （Natural Science）， 2022， 39（4）： 1-11.
[11]	Aydemir-Karadag A. Bi-objective adaptive large neighborhood search algorithm for the healthcare waste periodic location inventory routing problem［J］. Arabian Journal for Science and Engineering， 2022，47（3）： 3861-3876.
[12]	尚春剑，马良，刘勇. 垃圾分类下带时间窗异构周期性混合车辆路径问题模型及算法［J］. 系统工程， 2021， 39（6）： 131-145.
	Shang C J， Ma L， Liu Y. The model and algorithm of heterogeneous periodic hybrid vehicle routing problem with time window under garbage classification［J］. Systems Engineering， 2021， 39（6）： 131-145.
[13]	Elbek M， Wøhlk S. A variable neighborhood search for the multi-period collection of recyclable materials［J］. European Journal of Operational Research， 2016， 249（2）： 540-550.
[14]	Shaw P. Using constraint programming and local search methods to solve vehicle routing problems［M］//Maher M， Puget J F. Principles and Practice of Constraint Programming— CP98， Berlin， Heidelberg： Springer Berlin Heidelberg， 1998： 417-431.
[15]	Fang Z， Tu W， Li Q， et al. A Voronoi neighborhood-based search heuristic for distance/capacity constrained very large vehicle routing problems［J］. International Journal of Geographical Information Science， 2013， 27（4）： 741-764.
[16]	Hübner A， Ostermeier M. A multi-compartment vehicle routing problem with loading and unloading costs［J］. Transportation Science， 2018， 53（1）： 282-300.
[17]	Ropke S， Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］. Transportation Science， 2006， 40（4）： 455-472.
[18]	Alinaghian M， Shokouhi N. Multi-depot multi-compartment vehicle routing problem， solved by a hybrid adaptive large neighborhood search［J］. Omega， 2018， 76： 85-99.
[19]	Mancini S. A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet： Formulation and adaptive large neighborhood search based matheuristic［J］.Transportation Research Part C： Emerging Technologies， 2016， 70： 100-112.
[20]	Coelho L C， Cordeau J F， Laporte G. The inventory-routing problem with transshipment［J］. Computers & Operations Research， 2012， 39（11）： 2537-2548.
[21]	Gu W， Cattaruzza D， Ogier M， et al. Adaptive large neighborhood search for the commodity constrained split delivery VRP［J］. Computers & Operations Research， 2019， 112： 104761.
[22]	Clarke G， Wright J W. Scheduling of vehicles from a central depot to a number of delivery points［J］. Operations Research， 1964， 12（4）： 568-581.
[23]	Cornillier F， Boctor F F， Laporte G， et al. A heuristic for the multi-period petrol station replenishment problem［J］. European Journal of Operational Research， 2008， 191（2）： 295-305.
[24]	Hemmelmayr V C， Doerner K F， Hartl R F. A variable neighborhood search heuristic for periodic routing problems［J］.European Journal of Operational Research， 2009， 195（3）： 791-802.
[25]	Popović D， Vidović M， Radivojević G. Variable Neighborhood Search heuristic for the Inventory Routing Problem in fuel delivery［J］. Expert Systems with Applications， 2012， 39（18）： 13390-13398.

算例规模	垃圾点数	垃圾种类数	周期数	算例总数
小规模	4, 5	2	4	10
中大规模	15, 20, 30, 50	2, 3	3, 5	30

车容	车辆类型	车舱数量	车舱容量	派车成本	单位路径成本
1650	单舱	1	1650	208	1
1650	双舱	2	825+825	212	1
2750	单舱	1	2750	218	1.1
2750	双舱	2	1375+1375	262	1.1
5400	单舱	1	5400	348	1.3
	双舱	2	2700+2700	417
	三舱	3	1800+1800+1800	500
	四舱	4	1350+1350+1350+1350	590

算例编号	实验类型	总成本	车辆数	派车成本	路径成本	平均收运频次
15-3-3-1	实验组	2680	5	1205	1575	3.3
15-3-3-1	对照组	2240	4	1159	1081	2.3
15-3-3-3	实验组	2884	5	1380	1504	3.2
15-3-3-3	对照组	2414	4	1397	1017	2.1
20-3-3-1	实验组	3390	5	1480	1911	3.4
20-3-3-1	对照组	2786	4	1552	1234	2.1
20-3-3-3	实验组	3462	6	1698	1764	3.4
20-3-3-3	对照组	2915	5	1775	1140	2.2
20-3-5-1	实验组	7584	12	3496	4088	7.3
20-3-5-1	对照组	6406	10	3758	2648	4.4
20-3-5-3	实验组	7633	11	3305	4328	7.7
20-3-5-3	对照组	6561	9	3651	2910	4.8
30-3-3-1	实验组	4284	7	1996	2288	3.2
30-3-3-1	对照组	3502	5	1861	1642	2.1
30-3-3-3	实验组	3832	7	1916	1916	3.1
30-3-3-3	对照组	3257	5	1861	1396	2.1
30-3-5-1	实验组	9040	16	4138	4903	7.4
30-3-5-1	对照组	7741	12	4505	3236	4.7
30-3-5-3	实验组	9755	16	4628	5127	7.3
30-3-5-3	对照组	8420	13	4962	3458	4.3
50-2-3-1	实验组	5960	10	3090	2870	3.1
50-2-3-1	对照组	5596	9	3416	2180	2.1
50-2-3-3	实验组	5564	10	2960	2624	3.1
50-2-3-3	对照组	5177	8	3060	2117	2.3