基于混合蚁群算法的冷链电动汽车车辆路径问题

doi:10.11772/j.issn.1001-9081.2021091572

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (10): 3244-3251.DOI: 10.11772/j.issn.1001-9081.2021091572

• 前沿与综合应用 • 上一篇

基于混合蚁群算法的冷链电动汽车车辆路径问题

刘志硕, 刘若思, 陈哲

北京交通大学交通运输学院，北京 100044

收稿日期:2021-09-06 修回日期:2022-04-12 接受日期:2022-04-14 发布日期:2022-10-14 出版日期:2022-10-10
通讯作者: 刘志硕
作者简介:第一联系人：刘志硕（1977—），男，湖南安仁人，副教授，博士，主要研究方向：智慧物流与敏捷供应链、车联网、物联网; zhsliu@bjtu.edu.cn
刘若思（1998—），男，黑龙江大兴安岭人，硕士研究生，主要研究方向：交通与物流规划、车辆路径规划
陈哲（1993—），男，湖北黄冈人，硕士，主要研究方向：电动汽车充电策略设计与路径规划。
基金资助:
国家自然科学基金资助项目(72171019)

Cold chain electric vehicle routing problem based on hybrid ant colony optimization

Zhishuo LIU, Ruosi LIU, Zhe CHEN

School of Traffic and Transportation，Beijing Jiaotong University，Beijing 100044，China

Received:2021-09-06 Revised:2022-04-12 Accepted:2022-04-14 Online:2022-10-14 Published:2022-10-10
Contact: Zhishuo LIU
About author:LIU Zhishuo， born in 1977， Ph. D. ， associate professor. His research interests include intelligent logistics and agile supply chain，internet of vehicles， internet of things.
LIU Ruosi， born in 1998， M. S. candidate. His research interests include transportation and logistics planning， vehicle route planning.
CHEN Zhe, born in 1993， M. S. His research interests include charging strategy design and route planning for electric vehicles.
Supported by:
National Natural Science Foundation of China(72171019)

摘要/Abstract

摘要：

用电动汽车进行冷链物流配送符合绿色物流的发展趋势。针对电动汽车冷链配送需消耗更多能源以维持低温环境，而电动汽车续驶里程短、充电时间长，致使运营成本高的现象，思考了电动汽车配送中的冷链车辆路径问题（REVRP）。考虑电动汽车能耗特点和社会充电站的充电需求，构建了以总配送成本最小为优化目标的线性规划模型，而目标函数由固定成本和可变成本构成，其中可变成本包含运输成本和制冷成本。模型考虑容量约束和电量约束，并设计混合蚁群（HACO）算法对其进行求解，其中重点设计了适合社会充电站的转移规则以及4种局部优化算子。在改进Solomon基准算例的基础上，形成了小规模和大规模两个算例集，并通过实验比较了蚁群（ACO）算法和局部优化算子的性能。实验结果表明，在小规模算例集中，传统ACO算法与CPLEX求解器均能找到精确解，而ACO算法在运算时间方面可节省99.6%；而在大规模算例集中，与ACO算法相比，结合4种局部优化算子的HACO算法的平均优化效率提升了4.45%。所提算法能够在有限时间内得出电动汽车REVRP的可行解。

关键词: 冷链物流, 物流配送, 电动汽车, 车辆路径问题, 蚁群算法

Abstract:

The trend of green logistics pushes the use of electric vehicles into cold chain logistics. Concerning the problem that maintaining a low temperature environment requires a lot of energy in electric vehicle cold chain distribution， as well as the phenomena that the limited driving range and long charging time of electric vehicles make high operation cost， the Refrigerated Electric Vehicle Routing Problem （REVRP） in electric vehicle distribution was thought deeply. Considering the characteristics of electric vehicle energy consumption and the charging requirements of social recharging stations， a linear programming model was developed with the objective of minizing total distribution cost， and the objective function was composed of fixed cost and variable cost， in the variable cost， transportation cost and cooling cost were included. The capacity constraints and power constraints were considered in the model， and a Hybrid Ant Colony Optimization （HACO） algorithm was designed to solve this model. Especially， more attention was paid to designing transfer rules suitable for social recharging stations and four local optimization operators. Based on improving the Solomon benchmark examples， the small-scale and large-scale example sets were formed， and the performance of ACO algorithm and the optimization operators were through experiments. The experiment results show that ACO algorithm and CPLEX （WebSphere ILOG CPLEX） solver can find the exact solution in the small-scale example set， and ACO algorithm can save the operation time by 99.6% . In the large-scale example set， compared with ACO algorithm， HACO algorithm combing the four optimization operators has the average optimization efficiency increased by 4.45%. The proposed algorithm can obtain a feasible solution for REVRP in a limited time.

Key words: cold chain logistics, logistics distribution, electric vehicle, Vehicle Routing Problem (VRP), ant colony optimization

中图分类号:

O223

刘志硕, 刘若思, 陈哲. 基于混合蚁群算法的冷链电动汽车车辆路径问题[J]. 计算机应用, 2022, 42(10): 3244-3251.

Zhishuo LIU, Ruosi LIU, Zhe CHEN. Cold chain electric vehicle routing problem based on hybrid ant colony optimization[J]. Journal of Computer Applications, 2022, 42(10): 3244-3251.

图/表 11

表1 集合和参数设置

Tab. 1 Setting of sets and parameters

符号	描述	单位
0，N+1	配送中心	―
V	客户集合	―
K	配送车辆集合	―
F	充电站集合	―
I	$F ⋃ 0$	―
$V'$	$V ⋃ F$	―
$V 0'$	$V' ⋃ 0$	―
$V N + 1'$	$V' ⋃ N + 1$	―
$V 0, N + 1'$	$V' ⋃ 0 ⋃ N + 1$	―
C	配送车辆载重量	kg
Q	电池最大容量	kW⋅h
$v 1$	车辆行驶速度	km/h
g	充电速度	kW⋅h/h
$v 2$	卸货速度	kg/h
$d i j$	节点i、j之间的距离	km
$t i j$	车辆从i到j的行驶时间， $t i j = d i j / v 1$	h
$q i$	客户i的需求量	kg
$s i$	客户i的服务时间， $s i = q i / v 2$	h
a	每辆车的固定成本	元/辆
b	单位耗电量成本	元/（kW⋅h）
h	提供车辆动力单位里程消耗的电能	kW⋅h/km
l	单位时间制冷消耗的电能	kW⋅h/h

表1 集合和参数设置

Tab. 1 Setting of sets and parameters

符号	描述	单位
0，N+1	配送中心	―
V	客户集合	―
K	配送车辆集合	―
F	充电站集合	―
I	$F ⋃ 0$	―
$V'$	$V ⋃ F$	―
$V 0'$	$V' ⋃ 0$	―
$V N + 1'$	$V' ⋃ N + 1$	―
$V 0, N + 1'$	$V' ⋃ 0 ⋃ N + 1$	―
C	配送车辆载重量	kg
Q	电池最大容量	kW⋅h
$v 1$	车辆行驶速度	km/h
g	充电速度	kW⋅h/h
$v 2$	卸货速度	kg/h
$d i j$	节点i、j之间的距离	km
$t i j$	车辆从i到j的行驶时间， $t i j = d i j / v 1$	h
$q i$	客户i的需求量	kg
$s i$	客户i的服务时间， $s i = q i / v 2$	h
a	每辆车的固定成本	元/辆
b	单位耗电量成本	元/（kW⋅h）
h	提供车辆动力单位里程消耗的电能	kW⋅h/km
l	单位时间制冷消耗的电能	kW⋅h/h

表2 决策变量设置

Tab. 2 Setting of decision variables

符号	描述	单位
$y i k$	车辆k到达节点i的剩余电量	kW·h
$Q i k$	车辆k在充电站的充电量	kW·h
$s i k$	车辆k在充电站的充电时间， $s i k = Q i k / g$	h
$u i k$	车辆k到达节点i时的装载量	kg
$x i j k$	车辆k是否从节点i行驶到节点j	―

表2 决策变量设置

Tab. 2 Setting of decision variables

符号	描述	单位
$y i k$	车辆k到达节点i的剩余电量	kW·h
$Q i k$	车辆k在充电站的充电量	kW·h
$s i k$	车辆k在充电站的充电时间， $s i k = Q i k / g$	h
$u i k$	车辆k到达节点i时的装载量	kg
$x i j k$	车辆k是否从节点i行驶到节点j	―

图1 ACO算法的基本流程

Fig. 1 Basic flow of ACO algorithm

表3 ACO算法的参数

Tab. 3 ACO algorithm parameters

符号	描述	取值	符号	描述	取值
m_Antnum	蚂蚁数量	50	$β$	转移概率系数	2
m_Maxiter	迭代次数	200	$γ$	转移概率系数	3
$θ 1$ ， $θ 2$ ， $θ 3$	因子得分增量	20	$δ$	转移概率系数	3
$ρ$	信息素耗散率	0.05	$r p$	轮盘赌参数	0.1
$α$	转移概率系数	3

表3 ACO算法的参数

Tab. 3 ACO algorithm parameters

符号	描述	取值	符号	描述	取值
m_Antnum	蚂蚁数量	50	$β$	转移概率系数	2
m_Maxiter	迭代次数	200	$γ$	转移概率系数	3
$θ 1$ ， $θ 2$ ， $θ 3$	因子得分增量	20	$δ$	转移概率系数	3
$ρ$	信息素耗散率	0.05	$r p$	轮盘赌参数	0.1
$α$	转移概率系数	3

表2 电动汽车的性能参数

Tab. 2 Electric vehicle performance parameters

符号	描述	取值	符号	描述	取值
T	初始温度	100	b	单位耗电成本	0.5
H	冷却率	0.999	a	单位固定成本	200
$v 1$	车辆速度	60	h	单位里程行驶耗电量	1
$v 2$	卸货速度	100	l	单位时间制冷耗量	5

表2 电动汽车的性能参数

Tab. 2 Electric vehicle performance parameters

符号	描述	取值	符号	描述	取值
T	初始温度	100	b	单位耗电成本	0.5
H	冷却率	0.999	a	单位固定成本	200
$v 1$	车辆速度	60	h	单位里程行驶耗电量	1
$v 2$	卸货速度	100	l	单位时间制冷耗量	5

表4 小规模算例实验结果

Tab. 4 Experimental results of small-scale examples

算例	CPLEX		ACO算法
算例	Z/元	t/s	Z/元	t/s
平均值		94.70		0.36
C101-5	719.14	2.31	719.14	0.19
C206-5	535.05	0.87	535.05	0.32
R104-5	485.18	1.45	485.18	0.26
R202-5	481.95	0.92	481.95	0.31
RC105-5	528.75	2.68	528.75	0.37
RC204-5	505.65	0.36	505.65	0.24
C101-10	786.21	12.42	786.21	0.25
C202-10	747.82	9.62	747.82	0.32
R102-10	948.46	3.75	948.46	0.25
R201-10	519.27	3.36	519.27	0.36
RC102-10	1 029.88	7.51	1 029.88	0.40
RC201-10	774.00	9.43	774.00	0.38
C103-15	775.35	166.83	775.35	0.38
C202-15	1 035.89	15.77	1 035.89	0.44
R102-15	993.78	85.90	993.78	0.40
R202-15	1 232.72	725.03	1 232.72	0.47
RC103-15	1 032.95	649.11	1 032.95	0.40
RC202-15	1 030.90	8.57	1 030.90	0.78

表5 大规模算例实验结果

Tab. 5 Experimental results of large-scale examples

算例	ACO			HACO-I				HACO-II
算例	best/元	Ave./元	t/s	best/元	ΔZ/%	Ave./元	t/s	best/元	ΔZ/%	Ave./元	t/s
C101	2 586.4	2 607.0	16.9	2 574.6	-0.46	2 575.1	65.0	2 580.5	-0.23	2 581.0	57.5
C201	1 502.4	1 568.9	18.4	1 494.6	-0.52	1 512.5	57.4	1 496.6	-0.39	1 521.3	81.7
R101	3 625.8	3 778.5	18.9	3 603.3	-0.62	3 702.6	77.2	3 613.4	-0.34	3 728.2	88.7
R201	1 109.1	1 118.2	22.6	1 099.6	-0.86	1 102.3	42.2	1 092.2	-1.52	1 108.9	33.3
RC101	3 376.7	3 420.1	23.0	3 360.6	-0.48	3 373.8	107.2	3 242.3	-3.98	3 358.4	123.5
RC201	1 284.7	1 307.7	30.1	1 276.7	-0.62	1 250.0	79.7	1 267.9	-1.31	1 278.7	87.4

图2 节点分布形式对路径求解的影响

Fig. 2 Influence of node distribution format on path solving

图3 电池容量对目标值的影响

Fig. 3 Influence of battery capacity on target value

图4 不同策略对目标的优化效率

Fig. 4 Improvement efficiencies of different strategies to goal

图5 不同策略在不同节点分布形式下的改进效果对比

Fig. 5 Improvement effect comparison of different strategies under different node distribution formats

参考文献 33

1	方凯. 我国农产品冷链物流的发展问题研究——基于绿色供应链的农产品冷链物流效率的实证分析［D］. 武汉：华中农业大学， 2013：39-55.
	FANG K. The study on the development of agricultural products cold chain logistics—empirical analysis of agricultural products cold chain logistics efficiency based on green supply chain［D］. Wuhan： Huazhong Agricultural University， 2013：39-55.
2	刘全明. 新旧能源物流汽车替代过程中的博弈和效益优化仿真研究［D］. 北京：北京交通大学， 2020：29-54.
	LIU Q M. The game and benefit optimization simulation in replacement process of new and old energy logistics vehicles［D］. Beijing： Beijing Jiaotong University， 2020： 29-54.
3	DANTZIG G B， RAMSER J H. The truck dispatching problem［J］. Management Science， 1959， 6（1）：80-91. 10.1287/mnsc.6.1.80
4	DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating agents［J］. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 1996， 26（1）：29-41. 10.1109/3477.484436
5	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. 10.1016/j.asoc.2013.10.017
6	LI Y B， SOLEIMANI H， ZOHAL M. An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives［J］. Journal of Cleaner Production， 2019， 227：1161-1172. 10.1016/j.jclepro.2019.03.185
7	GUO N， QIAN B， HU R， et al. A hybrid ant colony optimization algorithm for multi-compartment vehicle routing problem［J］. Complexity， 2020， 2020： No.8839526. 10.1155/2020/8839526
8	MUTAR M L， BURHANUDDIN M A， HAMEED A S， et al. An efficient improvement of ant colony system algorithm for handling capacity vehicle routing problem［J］. International Journal of Industrial Engineering Computations， 2020， 11（4）：549-564.
9	OSVALD A， STIRN L Z. A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food［J］. Journal of Food Engineering， 2008， 85（2）：285-295. 10.1016/j.jfoodeng.2007.07.008
10	AMORIM P， PARRAGH S N， SPERANDIO F， et al. A rich vehicle routing problem dealing with perishable food： a case study［J］. TOP， 2014， 22（2）：489-508. 10.1007/s11750-012-0266-4
11	ABDI A， ABDI A， AKBARPOUR N， et al. Innovative approaches to design and address green supply chain network with simultaneous pick-up and split delivery［J］. Journal of Cleaner Production， 2020， 250： No.119437. 10.1016/j.jclepro.2019.119437
12	ZULVIA F E， KUO R J， NUGROHO D Y. A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products［J］. Journal of Cleaner Production， 2020， 242： No.118428. 10.1016/j.jclepro.2019.118428
13	LI D L， CAO Q， ZUO M， et al. Optimization of green fresh food logistics with heterogeneous fleet vehicle route problem by improved genetic algorithm［J］. Sustainability， 2020， 12（5）： No.1946. 10.3390/su12051946
14	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. 10.1287/trsc.2013.0490
15	GOEKE D， SCHNEIDER M. Routing a mixed fleet of electric and conventional vehicles［J］. European Journal of Operational Research， 2015， 245（1）：81-99. 10.1016/j.ejor.2015.01.049
16	揭婉晨，杨珺，杨超. 多车型电动汽车车辆路径问题的分支定价算法研究［J］. 系统工程理论与实践， 2016， 36（7）：1795-1805. 10.12011/1000-6788(2016)07-1795-11
	JIE W C， YANG J， YANG C. Branch-and-price algorithm for heterogeneous electric vehicle routing problem［J］. Systems Engineering—Theory & Practice， 2016， 36（7）：1795-1805. 10.12011/1000-6788(2016)07-1795-11
17	ÇATAY B， KESKIN M. The impact of quick charging stations on the route planning of electric vehicles［C］// Proceedings of the 2017 IEEE Symposium on Computers and Communications. Piscataway： IEEE， 2017：152-157. 10.1109/iscc.2017.8024521
18	ZHANG S， GAJPAL Y， APPADOO S S， et al. Electric vehicle routing problem with recharging stations for minimizing energy consumption［J］. International Journal of Production Economics， 2018， 203：404-413. 10.1016/j.ijpe.2018.07.016
19	MACRINA G， DI PUGLIA PUGLIESE L， GUERRIERO F， et al. The green mixed fleet vehicle routing problem with partial battery recharging and time windows［J］. Computers and Operations Research， 2019， 101：183-199. 10.1016/j.cor.2018.07.012
20	KESKIN M， AKHAVAN-TABATABAEI R， ÇATAY B. Electric vehicle routing problem with time windows and stochastic waiting times at recharging stations［C］// Proceedings of the 2019 Winter Simulation Conference. Piscataway： IEEE， 2019：1649-1659. 10.1109/wsc40007.2019.9004766
21	KARAKATIČ S. Optimizing nonlinear charging times of electric vehicle routing with genetic algorithm［J］. Expert Systems with Applications， 2021， 164： No.114039. 10.1016/j.eswa.2020.114039
22	ELSHAER R， AWAD H. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants［J］. Computers and Industrial Engineering， 2020， 140： No.106242. 10.1016/j.cie.2019.106242
23	BELL J E， McMULLEN P R. Ant colony optimization techniques for the vehicle routing problem［J］. Advanced Engineering Informatics， 2004， 18（1）：41-48. 10.1016/j.aei.2004.07.001
24	MAVROVOUNIOTIS M， ELLINAS G， POLYCARPOU M. Ant colony optimization for the electric vehicle routing problem［C］// Proceedings of the 2018 IEEE Symposium Series on Computational Intelligence. Piscataway： IEEE， 2018：1234-1241. 10.1109/ssci.2018.8628831
25	刘志硕，申金升，柴跃廷. 一种求解车辆路径问题的混合多蚁群算法（英文）［J］. 系统仿真学报， 2007， 17（15）：3513-3520. 10.3969/j.issn.1004-731X.2007.15.037
	LIU Z S， SHEN J S， CHAI Y T. Hybrid multiple ant colonies algorithm for capacitated vehicle routing problem［J］. Journal of System Simulation， 2007， 19（15）：3513-3520. 10.3969/j.issn.1004-731X.2007.15.037
26	YU B， YANG Z Z， YAO B Z. An improved ant colony optimization for vehicle routing problem［J］. European Journal of Operational Research， 2009， 196（1）：171-176. 10.1016/j.ejor.2008.02.028
27	STÜTZLE T， HOOS H H. MAX-MIN ant system［J］. Future Generation Computer Systems， 2000， 16（8）：889-914. 10.1016/s0167-739x(00)00043-1
28	LIN S. Computer solutions of the traveling salesman problem［J］. Bell System Technical Journal， 1965， 44（10）：2245-2269. 10.1002/j.1538-7305.1965.tb04146.x
29	LIN S， KERNIGHAN B W. An effective heuristic algorithm for the TS［J］. Operational Research， 1973， 21（2）：498-516. 10.1287/opre.21.2.498
30	BARBAROSOGLU G， OZGUR D. A tabu search algorithm for the vehicle routing problem［J］. Computers and Operations Research， 1999， 26（3）：255-270. 10.1016/s0305-0548(98)00047-1
31	BALSEIRO S R， LOISEAU I， RAMONET J. An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows［J］. Computers and Operations Research， 2011， 38（6）： 954-966. 10.1016/j.cor.2010.10.011
32	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. 10.1016/j.trc.2016.01.013
33	SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research， 1987， 35（2）：254-265. 10.1287/opre.35.2.254

[1]	肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
[2]	韩舒宁, 徐敏, 董学士, 林青, 沈凡凡. 混合伊藤算法求解多尺度着色旅行商问题[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 695-700.
[3]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[4]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[5]	李二超, 齐款款. B样条曲线融合蚁群算法的机器人路径规划[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3558-3564.
[6]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.
[7]	张庆华, 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法[J]. 计算机应用, 2020, 40(4): 1097-1103.
[8]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[9]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[10]	刘育良, 陈淮莉. 负载影响下纯电动汽车配送路径规划及充电策略[J]. 计算机应用, 2020, 40(10): 2831-2837.
[11]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[12]	王东先, 孟学雷, 乔俊, 汤霖, 焦志臻. 基于改进蚁群算法的铁路乘务交路计划的编制[J]. 计算机应用, 2019, 39(9): 2749-2756.
[13]	张玉州, 徐廷政, 郑军帅, 饶舜. 考虑紧急度的救灾车辆路径问题建模与优化[J]. 计算机应用, 2019, 39(8): 2444-2449.
[14]	郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.
[15]	杨继东, 孙兆琦, 王飞龙. 基于视觉抓取的并联桁架机器人最优路径控制[J]. 计算机应用, 2019, 39(3): 913-917.

基于混合蚁群算法的冷链电动汽车车辆路径问题

Cold chain electric vehicle routing problem based on hybrid ant colony optimization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 33

相关文章 15

编辑推荐

Metrics