考虑路段充电和时间窗的电动车取送货问题

doi:10.3976/j.issn.1002-4026.2023.03.010

摘要/Abstract

摘要：

考虑路段充电和时间窗的电动车取送货问题,以最小化车辆总旅行距离为目标,结合车辆容量约束、时间窗约束和电量约束等限制,决策一组最优的车辆线路。该问题公式化为一个混合整数线性规划模型,提出一种变邻域搜索算法求解该问题。数值算例用于验证模型的性质和算法的性能。结果表明:在小规模算例中,提出的算法只比商业求解器CPLEX差0.08%;但在大规模算例中,算法能求出高质量的可行解而CPLEX在规定时间内无法得到可行解。

关键词: 物流工程, 取送货问题, 变邻域搜索算法, 电动车辆, 充电路段

Abstract:

In this paper, the electric vehicles pickup and delivery problem considering link recharging and time windows was studied. Aims to minimize the total travel distance of vehicles, considering the constraints of vehicle capacity, time windows and battery capacity, etc., to determine a group of optimal vehicle routes. The problem is formulated as a mixed integer linear programming model; a variable neighborhood search algorithm is proposed to solve it. Numerical instances are used to verify the model properties and algorithm performance. The results show that the proposed algorithm is only 0.08% worse than the commercial solver CPLEX in small scale instances; however, in large scale instances, the algorithm can obtain high quality feasible solutions in the specified time, in contrast to the CPLEX.

Key words: logistics engineering, pickup and delivery problems, variable neighborhood search algorithm, electric vehicle, recharging link

中图分类号:

U121

陈清, 徐小明. 考虑路段充电和时间窗的电动车取送货问题[J]. 山东科学, 2023, 36(3): 78-89.

CHEN Qing, XU Xiaoming. Electric vehicle pickup and delivery based on link recharging and time windows[J]. Shandong Science, 2023, 36(3): 78-89.

图/表 12

图1

表1

符号定义"

符号	含义	符号	含义
$e i$	在节点 $i$ 的最早开始服务时刻	$Q$	电池容量
$l i$	在节点 $i$ 的最晚开始服务时刻	$C$	车辆容量
$t i j$	在弧( $i, j$ )上的走行时间	$T$	计划周期
$d i j$	节点 $i$ 到节点 $j$ 的距离	$x i j k$	如果车辆 $k$ 访问弧( $i, j$ )则为1,反之为0
$q i$	节点 $i$ 的需求	$T i k$	第 $k$ 辆车在节点 $i$ 的开始服务时刻
$h$	单位长度的耗电系数	$u i k$	第 $k$ 辆车离开节点 $i$ 的货物量
$γ$	单位长度的充电系数	$B i k$	第 $k$ 辆车到达节点 $i$ 的电量
$s i$	在节点 $i$ 的服务时间

表1

图2

图3

图4

图5

表2

最大迭代次数的实验结果"

最大迭代次数	$f -$	$f m a x - f m i n f m i n$ /%	平均运行时间/s
5 000	3 805.70	11.80	6.49
10 000	3 795.40	7.70	12.23
20 000	3 781.10	9.80	24.69
25 000	3 719.10	7.90	30.66

表2

表3

各系数的实验结果"

参数	参数取值	$f -$	$f m a x - f m i n f m i n$ /%	平均车辆数/辆
	0.4	3 834.70	4.44	12.60
耗电系数	0.6	4 194.90	5.93	14.50
	0.8	3 862.60	4.47	15.50
	1.0	3 773.20	11.57	12.40
充电系数	2.0	3 814.10	7.59	12.40
	3.0	3 843.20	7.81	12.10
	0.90	3 803.50	7.31	12.40
冷却率	0.75	3 787.90	5.56	12.40
	0.50	3 831.50	7.87	12.10
	0.10	3 814.40	17.11	12.50
初始温度系数	0.07	3 824.30	8.34	12.40
	0.04	3 805.30	7.13	12.80

表3

表4

VNS算法与CPLEX在小规模算例中获得的结果比较"

算例	CPLEX			VNS
算例	$m$ /辆	$f C P L E X$	t_CPLEX/s	$f * V N S$	t_VNS/s	$σ 0$ /%
R8-0	2	438	1.60	438	1.70	0.00
R8-1	2	434	1.50	434	1.20	0.00
R8-2	2	382	0.80	382	1.70	0.00
R8-3	2	519	0.90	519	0.90	0.00
R8-4	2	396	0.70	401	1.30	1.30
C8-0	1	209	2.40	209	0.80	0.00
C8-1	1	117	0.80	117	0.90	0.00
C8-2	1	196	0.70	196	0.80	0.00
C8-3	1	132	0.60	132	0.70	0.00
C8-4	2	276	1.30	276	1.50	0.00
RC8-0	2	300	1.70	300	0.10	0.00
RC8-1	2	334	0.90	334	0.40	0.00
RC8-2	2	432	2.10	432	0.40	0.00
RC8-3	2	287	0.50	287	0.60	0.00
RC8-4	2	360	0.70	360	0.10	0.00
R10-0	2	409	1.30	409	2.50	0.00
R10-1	2	589	1.40	589	1.50	0.00
R10-2	3	539	1.20	539	1.30	0.00
R10-3	2	551	1.80	551	2.10	0.00
R10-4	2	544	2.30	544	1.50	0.00
C10-0	1	128	1.50	128	1.00	0.00
C10-1	1	156	1.40	156	0.90	0.00
C10-2	1	201	1.30	201	1.00	0.00
C10-3	1	220	2.70	220	1.40	0.00
C10-4	1	243	1.00	243	1.50	0.00
RC10-0	2	396	4.20	396	2.10	0.00
RC10-1	2	395	1.60	395	1.90	0.00
RC10-2	2	347	2.60	347	2.20	0.00
RC10-3	2	429	2.90	429	1.80	0.00
RC10-4	3	484	210.40	484	1.70	0.00
R12-0	2	533	2.70	533	1.00	0.00
R12-1	2	590	2.10	590	1.10	0.00
R12-2	3	748	156.61	748	2.20	0.00
R12-3	2	522	0.60	522	0.80	0.00
R12-4	3	687	133.35	687	1.40	0.00
C12-0	1	229	4.40	229	2.20	0.00
C12-1	2	278	3.50	278	3.00	0.00
C12-2	1	244	1.80	244	4.70	0.00
C12-3	2	194	2.00	198	2.00	2.10
C12-4	2	252	1.50	252	1.10	0.00
RC12-0	2	420	3.30	420	0.70	0.00
RC12-1	3	494	4.90	494	2.30	0.00
RC12-2	2	383	2.40	383	4.80	0.00
RC12-3	3	445	2.30	445	2.10	0.00
RC12-4	2	580	293.40	580	2.80	0.00
平均			19.33		1.50	0.08

表4

表5

图6

表6

大规模算例的结果"

算例	平均车辆数/辆	初始解的值 $f 0$	最优值 $f V N S *$	平均值 $f - V N S$	平均运行时间 $t ¯$ /s	平均值 $f - G A$	$σ 1$ /%	$σ 2$ /%
R100-0	12.30	4 530	3 729	3 879.30	12.34	3 902.75	4.03	-0.60
R100-1	13.90	6 089	4 647	4 793.90	15.38	4 912.48	3.16	-2.47
R100-2	13.50	6 227	4 622	4 788.00	17.59	4 870.11	3.59	-1.71
R100-3	13.00	5 178	4 067	4 168.30	12.68	4 201.60	2.49	-0.80
R100-4	13.00	5 685	4 290	4 436.40	15.38	4 478.95	3.41	-0.96
C100-0	7.70	2 358	1 944	1 999.10	16.12	2 091.11	2.83	-4.60
C100-1	7.60	2 821	1 893	1 932.30	20.79	2 021.67	2.08	-4.63
C100-2	7.80	2 266	1 858	1 916.30	17.11	2 106.00	3.13	-9.90
C100-3	5.90	1 602	1 140	1 190.50	22.41	1 260.89	4.43	-5.91
C100-4	7.00	3 319	2 046	2 106.20	21.55	2 269.67	2.94	-7.76
RC100-0	11.50	6 117	3 893	4 064.80	14.19	4 270.48	4.41	-5.06
RC100-1	12.30	4 170	3 099	3 183.60	14.20	3 268.39	2.73	-2.66
RC100-2	11.10	3 637	2 886	3 025.30	13.01	3 127.36	4.82	-3.37
RC100-3	12.10	4 286	3 166	3 302.90	13.86	3 512.20	4.32	-6.34
RC100-4	11.60	4 815	3 620	3 722.10	15.95	3 799.52	2.82	-4.47
R200-0	26.00	10 735	8 735	9 062.50	24.46	9 557.61	3.75	-5.46
R200-1	23.60	9 921	8 179	8 559.90	22.80	8 936.12	4.66	-4.40
R200-2	24.90	10 671	8 927	9 111.00	28.15	9 620.50	2.06	-5.59
R200-3	24.90	9 434	8 113	8 504.50	23.50	8 954.70	4.83	-5.29
R200-4	25.40	11 345	8 934	9 150.80	26.16	9 756.37	2.43	-6.62
C200-0	13.60	3 837	2 950	3 090.60	35.81	3 211.89	4.77	-3.92
C200-1	11.40	3 745	2 839	2 882.50	37.19	2 924.11	1.53	-1.44
C200-2	13.90	4 041	3 741	3 833.00	30.29	3 993.78	2.46	-4.19
C200-3	13.40	5 527	3 967	4 130.30	33.64	4 164.89	4.12	-0.84
C200-4	12.60	4 376	3 420	3 521.80	41.13	3 559.44	2.98	-1.07
RC200-0	17.40	7 908	5 875	6 018.10	34.49	6 548.36	2.44	-8.81
RC200-1	17.70	7 951	6 103	6 174.30	32.03	6 416.40	1.17	-3.92
RC200-2	18.90	6 220	4 919	5 144.20	33.52	5 436.71	4.58	-5.69
RC200-3	17.90	6 684	4 867	5 025.80	28.99	5 378.58	3.26	-7.02
RC200-4	17.40	6 731	5 537	5 747.90	32.13	5 924.30	3.81	-3.07
R400-0	46.50	18 410	15 558	15 903.50	50.31	16 622.11	2.22	-4.52
R400-1	46.20	19 616	16 852	17128.10	59.95	17 956.30	1.64	-4.84
R400-2	45.90	19 156	16 398	16 608.10	55.91	17 348.56	1.28	-4.46
R400-3	45.10	18 022	15 129	15 634.80	53.99	16 380.47	3.34	-4.77
R400-4	45.80	21 252	16 157	16 732.70	48.02	17 249.35	3.56	-3.09
C400-0	22.50	6 328	5 775	5 925.60	70.89	6 066.00	2.61	-2.37
C400-1	26.70	8 020	7 252	7 494.50	97.42	7 955.89	3.34	-6.16
C400-2	24.80	7 286	6 577	6 730.60	72.33	7 079.56	2.34	-5.18
C400-3	26.00	7 197	6 169	6 315.00	65.99	6 737.67	2.37	-6.69
C400-4	27.30	9 206	7 452	7 803.50	81.41	8 275.89	4.72	-6.05
RC400-0	40.00	12 612	11 271	11 596.90	51.68	12 033.58	2.89	-3.77
RC400-1	41.90	13 830	12 015	12 609.70	52.38	13 481.26	4.95	-6.91
RC400-2	37.90	12 040	11 003	11 366.20	60.62	12 013.59	3.30	-5.70
RC400-3	40.40	12 678	11 723	12 002.60	51.31	12 714.22	2.39	-5.93
RC400-4	40.80	15 410	13 860	14131.70	55.85	14 986.20	1.96	-6.05
平均							3.18	-4.56

表6

参考文献 11

[1]	KOC C, KRRAOGLA N I. The green vehicle routing problem: A heuristic based exact solution approach[J]. Applied Soft Computing, 2016, 39: 154-164. DOI: 10.1016/j.asoc.2015.10.064. doi: 10.1016/j.asoc.2015.10.064
[2]	DESAULNIERS G, ERRICO F, IRNICH S, et al. Exact algorithms for electric vehicle-routing problems with time windows[J]. Operations Research, 2016, 64(6): 1388-1405. DOI: 10.1287/opre.2016.1535. doi: 10.1287/opre.2016.1535
[3]	ANDELMIN J, BARTOLINI E. An exact algorithm for the green vehicle routing problem[J]. Transportation Science, 2017, 51(4): 1288-1303. DOI: 10.1287/trsc.2016.0734. doi: 10.1287/trsc.2016.0734
[4]	商丽媛. 有时间窗装卸问题的一类改进遗传算法求解[J]. 太原师范学院学报(自然科学版), 2009, 8(1): 26-30. DOI: 10.3969/j.issn.1672-2027.2009.01.010. doi: 10.3969/j.issn.1672-2027.2009.01.010
[5]	SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520. DOI: 10.1287/trsc.2013.0490. doi: 10.1287/trsc.2013.0490
[6]	KESKIN M, ÇATAY B. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65: 111-127. DOI: 10.1016/j.trc.2016.01.013. doi: 10.1016/j.trc.2016.01.013
[7]	江玉萍. 带时间窗和充电站的纯电动物流车取送货路径优化问题[D]. 南京: 南京大学, 2019.
[8]	GOEKE D. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles[J]. European Journal of Operational Research, 2019, 278(3): 821-836. DOI: 10.1016/j.ejor.2019.05.010. doi: 10.1016/j.ejor.2019.05.010
[9]	CHEN Z B, LIU W, YIN Y F. Deployment of stationary and dynamic charging infrastructure for electric vehicles along traffic corridors[J]. Transportation Research Part C: Emerging Technologies, 2017, 77: 185-206. DOI: 10.1016/j.trc.2017.01.021. doi: 10.1016/j.trc.2017.01.021
[10]	邹云程, 刘昊翔, 龙建成. 考虑出行者异质的多类型充电设施部署优化[J]. 系统工程理论与实践, 2020, 40(11): 2946-2957. DOI: 10.12011/1000-6788-2019-2610-12. doi: 10.12011/1000-6788-2019-2610-12
[11]	NACCACHE S, CÔTÉ J F, COELHO L C. The multi-pickup and delivery problem with time windows[J]. European Journal of Operational Research, 2018, 269(1): 353-362. DOI: 10.1016/j.ejor.2018.01.035. doi: 10.1016/j.ejor.2018.01.035

算例		算例行驶路线	算例总距离
R12-0	车辆1的路线	12—0⁺—5⁺—21—20—0^-—2⁺—5^-—2^-—13	533
	车辆2的路线	12—1⁺—4⁺—1^-—4^-—3⁺—3^-—13