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

doi:10.3976/j.issn.1002-4026.2023.03.010

Abstract

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

CLC Number:

U121

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

Figures/Tables 12

Fig.1

Table 1

Notations"

符号	含义	符号	含义
$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$ 的服务时间

Table 1

Fig.2

Fig.3

Fig.4

Fig.5

Table 2

Experimental results of maximum iterations"

最大迭代次数	$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

Table 2

Table 3

Experimental results of each coefficient"

参数	参数取值	$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

Table 3

Table 4

Comparison of results obtained by the VNS algorithm and CPLEX in small scale instances"

算例	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

Table 4

Table 5

Fig.6

Table 6

Results obtained in large scale instances"

算例	平均车辆数/辆	初始解的值 $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

Table 6

References 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

Electric vehicle pickup and delivery based on link recharging and time windows

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 11

Related Articles 2

Metrics

Comments

Recommended 0

[1]	GU Teng-fei, ZHANG Yong. Research on recharging infrastructure planning for electric vehicles based on battery swapping [J]. SHANDONG SCIENCE, 2018, 31(4): 89-99.
[2]	CHEN Sheng-bo, LIU Yong-ping, HE Shi-wei, LI Hao-dong. Research on integrated optimization of double stack car carriers based vehicle loading and routing problems in vehicle logistics [J]. SHANDONG SCIENCE, 2017, 30(3): 73-81.