Path-Based Model for the Heterogeneous-Fleet Electric Vehicle Routing Problem with Partial Linear Recharging

doi:10.16182/j.issn1004731x.joss.21-1082

Abstract

Abstract:

The heterogeneous-fleet electric vehicle routing problem with partial linear recharging is studied for realistic logistics distribution scenarios using multiple electric vehicle fleets with different transport capacities, driving ranges and acquisition costs. A path-based mixed integer linear model is proposed. The model enumerates the paths visited by all vehicle types between any non-charging nodes, eliminates the infeasible paths through capacity constraints and time window constraints, and eliminates the dominated paths by the dominance criterion. Compared with the traditional charging station replica-based model, this model eliminates the need to set the number of charging station replicas. The results show that the model outperforms other models in terms of solution quality and solution speed, and verifies the validity of the model by conducting simulation experiments on the publicbench mark instances at different scales.

Key words: heterogeneous-fleet, partial linear recharging, electric vehicle routing problem, path-based model, dominance rules

CLC Number:

TP391.9

Weiquan Wang, Ding Ding, Linsha Yan. Path-Based Model for the Heterogeneous-Fleet Electric Vehicle Routing Problem with Partial Linear Recharging[J]. Journal of System Simulation, 2022, 34(3): 614-623.

Figures/Tables 8

Table1

Table 2

Mathematical notation of our model

符号	含义
V	车型的集合
C	商户节点的集合
I	所有节点的集合 $I = C ? {0, N + 1}$
$P D P$	直达路径集
$P C R P$	充电路径集
$Ω 0 C$	从起点配送中心出发到商户终止的路径集
$Ω C C$	从商户出发到商户终止的路径集
$Ω C 0$	从商户出发到终点配送中心终止的路径集
$P$	$P = P D P ? P C R P = Ω 0 C ? Ω C C ? Ω C 0$
M	一个充分大的数
$D p$	路径 $p$ 的通过距离
$T p m a x$	路径 $p$ 的最长通过时间
$T p m i n$	路径 $p$ 的最短通过时间
$Q p$	路径 $p$ 的的最大负载
$Y p$	路径 $p$ 的的最大里程
$f p$	路径 $p$ 的车辆固定成本
$s i$	商户 $i$ 的服务时间
$q i$	商户 $i$ 的服务负载
$α i, β i$	节点 $i$ 的服务时间窗
$A, B$	配送中心的服务时间窗
$π$	单位时间内充电的里程
$? L p$	路径 $p i j ∈ P C R P$ 上从 $i$ 到最左充电节点的距离
$? R p$	路径 $p i j ∈ P C R P$ 上从最右充电节点到 $j$ 的距离
$R p$	路径 $p$ 上的充电节点个数
$x p$	如果车辆访问路径 $p$ 则为1，反之，则为0
$λ p$	路径 $p$ 上的充电里程
$a i$	车辆到达商户 $i$ 的时间
$l i$	车辆离开商户 $i$ 的时间
$w i$	车辆离开商户 $i$ 的负载状态
$r i$	车辆离开商户 $i$ 的里程状态

Table 2

Table 3

Comparison with replication-based model

文献	0-1整数变量	连续变量
[3]	$x i j$	$τ i$ , $u i$ , $y i$
[13]	$x i j$	$τ i$ , $u i$ , $y i$ , $Y i$
[7]	$x i j k$	$τ i$ , $u i k$ , $y i k$
本文	$x p$	$a i$ , $l i$ , $r i$ , $w i$ , $λ p$

Table 3

Table 4

Table 5

Table 6

Table 7

Table 8

References 30

1	Erdoğan S, Miller-Hooks E. A Green Vehicle Routing Problem[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2012, 48(1): 100-114.
2	Roberti R, Wen M. The Electric Traveling Salesman Problem with Time Windows[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2016, 89: 32-52.
3	Schneider M, Stenger A, Goeke D. The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations[J]. Transportation Science (S0041-1655), 2014, 48(4): 500-520.
4	Desaulniers G, Errico F, Irnich S, et al. Exact algorithms for Electric Vehicle-Routing Problems with Time Windows[J]. Operations Research, (S0030-364X), 2016, 64(6): 1388-1405.
5	Golden B, Assad A, Levy L, et al. The Fleet Size and Mix Vehicle Routing Problem[J]. Computers & Operations Research, (S0305-0548), 1984, 11(1): 49-66.
6	Goeke D, Schneider M. Routing a Mixed Fleet of Electric and Conventional Vehicles[J]. European Journal of Operational Research, (S0377-2217), 2015, 245(1): 81-99.
7	Hiermann G, Puchinger J, Ropke S, et al. The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations[J]. European Journal of Operational Research (S0377-2217), 2016, 252(3): 995-1018.
8	Hiermann G, Hartl R F, Puchinger J, et al. Routing a Mix of Conventional, Plug-in Hybrid, and Electric Vehicles[J]. European Journal of Operational Research (S0377-2217), 2019, 272(1): 235-248.
9	Macrina G, Laporte G, Guerriero F, et al. An Energy-Efficient Green-Vehicle Routing Problem with Mixed Vehicle Fleet, Partial Battery Recharging and Time Windows[J]. European Journal of Operational Research (S0377-2217), 2019, 276(3): 971-982.
10	揭婉晨, 杨珺, 杨超. 多车型电动汽车车辆路径问题的分支定价算法研究[J]. 系统工程理论与实践, 2016, 36(7): 1795-1805.
	Wanchen Jie, Yang Jun, Yang Chao. Branch-and-Price Algorithm for Heterogeneous Electric Vehicle Routing Problem[J]. Systems Engineering-Theory & Practice, 2016, 36(7): 1795-1805.
11	李得成, 陈彦如, 张宗成. 基于分支定价算法的电动车与燃油车混合车辆路径问题研究[J]. 系统工程理论与实践, 2021, 41(4): 995-1009.
	Li Decheng, Chen Yanru, Zhang Zongcheng. A Branch-and-Price Algorithm for Electric Vehicle Routing Problem with Time Windows and Mixed Fleet[J]. Systems Engineering — Theory & Practice, 2021, 41(4): 995-1009.
12	李英, 张鹏威, 吴一帆. 电动汽车/传统汽车混合车队配置及路径优化模型[J]. 系统管理学报, 2020, 29(3): 522-531.
	Li Ying, Zhang Pengwei, Wu Yifan. Vehicle Routing Problem with Mixed Fleet of Conventional and Electric Vehicles[J]. Journal of Systems & Management, 2020, 29 (3): 971-982.
13	Keskin M, Çatay B. Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows[J]. Transportation Research Part C: Emerging Technologies (S0968-090X), 2016, 65: 111-127.
14	Felipe Á, Ortuño M T, Righini G, et al. A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2014, 71: 111-128.
15	Sweda T M, Dolinskaya I S, Klabjan D. Adaptive Routing and Recharging Policies for Electric Vehicles[J]. Transportation Science (S0041-1655), 2017, 51(4): 1326-1348.
16	Montoya A, Guéret C, Mendoza J E, et al. The Electric Vehicle Routing Problem with Nonlinear Charging Function[J]. Transportation Research Part B: Methodological (S0191-2615), 2017, 103: 87-110.
17	Froger A, Mendoza J E, Jabali O, et al. Improved Formulations and Algorithmic Components for the Electric Vehicle Routing Problem with Nonlinear Charging Functions[J]. Computers & Operations Research (S0305-0548), 2019, 104: 256-294.
18	Schiffer M, Walther G. An Adaptive Large Neighborhood Search for the Location-Routing Problem with Intra-Route Facilities[J]. Transportation Science (S0041-1655), 2018, 52(2): 331-352.
19	赵灿华, 侍洪波. 基于自适应变邻域搜索的大规模电动车辆路径优化[J]. 华东理工大学学报(自然科学版), 2020, 46(5): 694-701.
	Zhao Canhua, Shi Hongbo. Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search[J]. Journal of East China University of Science and Technology(Natural Science Edition), 2020, 46(5): 694-701.
20	Zhao M, Lu Y. A Heuristic Approach for a Real-World Electric Vehicle Routing Problem[J]. Algorithms (S1999-4893), 2019, 12(2): 45.
21	Wen M, Linde E, Ropke S, et al. An Adaptive Large Neighborhood Search Heuristic for the Electric Vehicle Scheduling Problem[J]. Computers & Operations Research (S0305-0548), 2016, 76: 73-83.
22	Cortés-Murcia D L, Prodhon C, Afsar H M. The Electric Vehicle Routing Problem with Time Windows, Partial Recharges and Satellite Customers[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2019, 130: 184-206.
23	Hansen P, Mladenović N. Variable Neighborhood Search: Principles and Applications[J]. European Journal of Operational Research (S0377-2217), 2001, 130(3): 449-467.
24	Vidal T, Crainic T G, Gendreau M, et al. A Hybrid Genetic Algorithm with Adaptive Diversity Management for a Large Class of Vehicle Routing Problems with Time-Windows[J]. Computers & Operations Research (S0305-0548), 2013, 40(1): 475-489.
25	胡蓉, 陈文博, 钱斌, 等. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
	Hu Rong, Chen Wenbo, Qian Bin, et al. Learning Ant Colony Algorithm for Green Multi-Depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
26	宁涛, 郭晨, 陈荣, 等. 一种动态车辆路径问题解决策略仿真研究[J]. 系统仿真学报, 2015, 27(12): 2942-2947.
	Ning Tao, Guo Chen, Chen Rong, et al. Simulation Study on Scheduling Strategy of Dynamic Vehicle Routing Problem[J]. Journal of System Simulation, 2015, 27(12): 2942-2947.
27	范双南, 陈纪铭, 高为民, 等. 基于改进智能水滴算法的动态车辆配送路径优化[J]. 系统仿真学报, 2020, 32(9): 1808-1817.
	Fan Shuangnan, Chen Jiming, Gao Weimin, et al. Dynamic Vehicle Distribution Path Optimization Based on Improved Intelligent Water Drop Algorithm[J]. Journal of System Simulation, 2020, 32(9): 1808-1817.
28	Bruglieri M, Mancini S, Pezzella F, et al. A Path-Based Solution Approach for the Green Vehicle Routing Problem[J]. Computers & Operations Research (S0305-0548), 2019, 103: 109-122.
29	Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research (S0030-364X), 1987, 35(2): 254-265.
30	Schiffer M, Walther G. The Electric Location Routing Problem with Time Windows and Partial Recharging[J]. European Journal of Operational Research (S0377-2217), 2017, 260(3): 995-1013.

文献	问题	多车型	容量	时间窗	线性完全充电	可变充电	模型
[3]	E-VRPTW-FR		√	√	√		Replication-based model
[13]	E-VRPTW-PR		√	√		√
[4]	EVRPTW		√	√	√	√
[7]	E-FSMFTW-FR	√	√	√	√
[10]	E-HVRPTW	√	√	√	√
[2]	E-TSPTW			√	√	√	Path-based model
[17]	E-VRP-NL					√
本文	E-FSMFTW-PR	√	√	√	√	√

模型	文献[3]	本文
#Opt/#Num	25/36	35/36
Ave Opt time/s	405.48	8.21

模型	文献[13]	文献[30]	本文
#Opt/#Num	33/36	31/36	35/36
Ave Opt time/s	74.70	554.92	5.97

算例	文献[7] FR	本文 PR	Gap/%	Time/s
C101-5	857.75	857.75	0	0.06
C103-5	476.05	475.37	-0.14	0.09
C206-5	1 261.88	1 252.10	-0.78	0.09
C208-5	1 164.34	1 164.34	0	0.17
R104-5	327.25	327.25	0	0.17
R105-5	346.08	346.08	0	0.05
R202-5	609.18	609.18	0	0.27
R203-5	645.63	645.63	0	0.17
RC105-5	511.96	511.96	0	0.08
RC108-5	532.04	532.04	0	0.14
RC204-5	496.74	496.74	0	4.19
RC208-5	328.89	328.89	0	0.44
C101-10	1 302.15	1 296.84	-0.41	0.13
C104-10	902.71	902.71	0	7 200
C202-10	1 304.32	1 304.32	0	1.22
C205-10	2 631.97	2 282.61	-13.27	1.11
R102-10	595.34	585.18	-1.71	3.75
R103-10	478.07	478.07	0	6 069
R201-10	1 138.38	773.35	-32.07	3.16
R203-10	952.16	952.16	0	7 200
RC102-10	1 100.27	1 100.27	0	0.19
RC108-10	693.27	693.27	0	6.44
RC201-10	684.63	682.48	-0.31	1.58
RC205-10	1 064.59	1 064.59	0	15.34
C103-15	1 291.03	1 274.43	-1.29	7 200
C106-15	1 253.59	1 250.76	-0.23	1.05
C202-15	2 403.35	2 403.35	0	7 200
C208-15	2 325.89	2 325.89	0	7 200
R102-15	850.58	846.74	-0.45	36.38
R105-15	760.13	760.13	0	13.73
R202-15	1 311.24	1 311.24	0	7 200
R209-15	1 033.50	1 033.50	0	7 200
RC103-15	840.97	840.97	0	7 200
RC108-15	1 013.70	1 013.70	0	7 200
RC202-15	1 101.60	1 101.60	0	487.84
RC204-15	810.90	810.90	0	7 200
Average Gap/%			-1.41
Average Opt Time/s			512
#Opt/#Num			26/36

算例	文献[7] FR	本文 PR	Gap/%	Time/s
C101-5	377.75	377.75	0	0.03
C103-5	236.05	235.37	-0.29	0.08
C206-5	461.88	452.10	-2.12	0.09
C208-5	364.34	364.34	0	0.17
R104-5	175.25	175.25	0	0.16
R105-5	194.08	194.08	0	0.05
R202-5	249.18	249.18	0	0.26
R203-5	285.63	285.63	0	0.17
RC105-5	295.96	295.96	0	0.08
RC108-5	313.93	313.93	0	0.11
RC204-5	255.55	255.55	0	1.09
RC208-5	208.89	208.89	0	0.52
C101-10	582.15	576.84	-0.91	0.13
C104-10	422.71	422.71	0	1 244.39
C202-10	504.32	504.32	0	0.72
C205-10	711.97	682.61	-4.12	1.22
R102-10	325.19	325.19	0	1.23
R103-10	262.07	262.07	0	1 392
R201-10	418.38	404.23	-3.38	1.92
R203-10	392.16	392.16	0	1 494.97
RC102-10	572.27	572.27	0	0.19
RC108-10	422.12	422.12	0	17.19
RC201-10	429.17	429.17	0	0.99
RC205-10	504.59	504.59	0	1.84
C103-15	571.03	554.43	-2.91	7 200
C106-15	533.59	530.76	-0.53	5.36
C202-15	803.35	803.35	0	4 630.06
C208-15	725.89	725.89	0	7 200
R102-15	511.55	506.69	-0.95	11.19
R105-15	436.89	436.89	0	6.22
R202-15	591.24	591.24	0	7 200
R209-15	473.50	473.50	0	7 200
RC103-15	499.67	499.67	0	1 387.36
RC108-15	514.65	514.65	0	7 200
RC202-15	541.61	541.61	0	351.37
RC204-15	410.90	410.90	0	7 200
Average Gap/%			-0.42
Average Opt Time/s			351
#Opt/#Num			30/36