线性充电策略下多车型电动车辆路径模型研究

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

系统仿真学报 ›› 2022, Vol. 34 ›› Issue (3): 614-623.doi: 10.16182/j.issn1004731x.joss.21-1082

线性充电策略下多车型电动车辆路径模型研究

王伟权^1,³(), 丁鼎¹(), 颜林莎²

^1.对外经济贸易大学国际经济与贸易学院, 北京 100029
^2.对外经济贸易大学政府管理学院, 北京 100029
^3.对外经济贸易大学信息化管理处, 北京 100029

收稿日期:2021-10-26 修回日期:2021-11-04 出版日期:2022-03-18 发布日期:2022-03-22
通讯作者: 丁鼎 E-mail:wangweiquan@uibe.edu.cn;dingd@uibe.edu.cn
作者简介:王伟权(1991-)，男，博士生，研究方向为电动车辆路径优化。E-mail：wangweiquan@uibe.edu.cn
基金资助:
北京市社会科学基金(17GLB026);对外经济贸易大学中央高校基本科研业务费(16JQ01)

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

Weiquan Wang^1,³(), Ding Ding¹(), Linsha Yan²

^1.School of International Trade and Economics, University of International Business and Economics, Beijing 100029, China
^2.School of Government, University of International Business and Economics, Beijing 100029, China
^3.Department of Information Management, University of International Business and Economics, Beijing 100029, China

Received:2021-10-26 Revised:2021-11-04 Online:2022-03-18 Published:2022-03-22
Contact: Ding Ding E-mail:wangweiquan@uibe.edu.cn;dingd@uibe.edu.cn

摘要/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

中图分类号:

TP391.9

王伟权, 丁鼎, 颜林莎. 线性充电策略下多车型电动车辆路径模型研究[J]. 系统仿真学报, 2022, 34(3): 614-623.

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.

图/表 8

表1

表2

本文模型的符号

符号	含义
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$ 的里程状态

表2

表3

与副本模型的比较

文献	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$

表3

表4

表5

表6

表7

表8

参考文献 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

线性充电策略下多车型电动车辆路径模型研究

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 30

相关文章 1

编辑推荐

Metrics

本文评价

算例	文献[7] FR	本文 PR	Gap/%	Time/s
C101-5	317.75	317.75	0	0.03
C103-5	206.05	205.37	-0.33	0.08
C206-5	361.88	352.10	-2.70	0.08
C208-5	264.34	264.34	0	0.22
R104-5	156.25	156.25	0	0.16
R105-5	175.08	175.08	0	0.05
R202-5	204.18	204.18	0	0.25
R203-5	240.63	240.63	0	0.17
RC105-5	268.96	268.96	0	0.08
RC108-5	283.93	283.93	0	0.13
RC204-5	220.55	220.55	0	0.77
RC208-5	193.89	193.89	0	0.51
C101-10	492.15	486.84	-1.08	0.16
C104-10	362.71	362.71	0	277.16
C202-10	404.32	404.32	0	1.38
C205-10	471.97	471.97	0	1.08
R102-10	287.19	287.19	0	1.05
R103-10	235.07	234.30	-0.33	813.61
R201-10	328.38	320.93	-2.27	1.78
R203-10	322.16	322.16	0	421.74
RC102-10	498.51	498.51	0	0.19
RC108-10	386.12	386.12	0	1.73
RC201-10	384.17	384.17	0	0.69
RC205-10	429.69	426.69	-0.70	1.23
C103-15	481.03	464.43	-3.45	3 081.31
C106-15	415.13	415.13	0	4.33
C202-15	603.35	603.35	0	944.92
C208-15	525.89	525.89	0	305.22
R102-15	465.94	460.69	-1.13	9.77
R105-15	387.89	387.89	0	3.05
R202-15	495.64	495.64	0	7 200
R209-15	403.50	403.50	0	3 150.45
RC103-15	448.67	448.67	0	1 057.94
RC108-15	445.25	445.25	0	7 200
RC202-15	471.61	471.61	0	114.02
RC204-15	360.90	360.90	0	7 200
Average Gap/%			-0.33
Average Opt time/s			308
#Opt/#Num			33/36