基于改进NSGA-Ⅱ的考虑自动引导车充电策略的集成调度

doi:10.11772/j.issn.1001-9081.2022121923

摘要/Abstract

摘要：

针对自动引导车（AGV）在自动化集装箱码头（ACT）执行任务过程中的电量问题，提出基于改进的非支配排序遗传算法-Ⅱ（NSGA-Ⅱ）的考虑AGV充电策略的集成调度。首先，在岸桥、场桥和AGV集成调度模式下，考虑AGV在不同作业状态下的耗电量，并建立以最小化作业完工时间和总耗电量为目标的多目标混合规划模型；其次，为提高传统NSGA-Ⅱ的性能，设计自适应NSGA-Ⅱ，并将所提算法与CPLEX求解器、NSGA-Ⅱ和多目标粒子群优化（MOPSO）算法进行性能对比；最后，设计AGV不同充电策略并对设备数量配比进行实验研究。算法对比实验结果表明：相较于传统NSGA-Ⅱ算法，自适应NSGA-Ⅱ对双目标的优化分别提升了2.8%和2.63%。利用自适应NSGA-Ⅱ进行的充电策略和设备数量配比实验的结果表明：增加AGV充电次数能够减少AGV的充电时间，且调整设备数量配比至3∶3∶9和3∶7∶3时，场桥和AGV的时间利用率分别达到最高。可见，AGV充电策略及设备数量配比对码头多设备集成调度有一定影响。

关键词: 自动化集装箱码头, 自动引导车, 充电策略, 码头集成调度, 自适应非支配排序遗传算法-Ⅱ, 耗电量

Abstract:

Aiming at the power problem of Automated Guided Vehicle （AGV） in the process of performing tasks in Automated Container Terminal （ACT）， an integrated scheduling considering AGV charging strategy based on improved Non-dominated Sorting Genetic Algorithm-Ⅱ （NSGA-Ⅱ） was proposed. Firstly， considering the power consumption of AGV under different operating statuses in the integrated scheduling mode of quay crane， yard crane and AGV， a multi-objective mixed programming model with the goal of minimizing the completion time and total power consumption was established. Secondly， to improve the performance of the traditional NSGA-Ⅱ， an adaptive NSGA-Ⅱ was designed and compared with CPLEX solver and Multi-Objective Partical Swarm Optimization （MOPSO） algorithm on performance. Finally， different charging strategies and equipment number ratios of AGV were designed for experimental research. The experimental results of algorithm comparison show that the solution results of the adaptive NSGA-Ⅱ are improved by 2. 80% and 2. 63% respectively on the two objectives proposed compared with NSGA-Ⅱ. The experimental results of applying the adaptive NSGA-Ⅱ to study the ratio of charging strategies and equipment number ratios show that increasing AGV charging number can reduce AGV charging time， and adjusting the ratio of the equipment number to 3：3：9 and 3：7：3 lead to the highest time utilization of yard crane and AGV respectively. It can be seen that the AGV charging strategy and equipment number ratio can influence the terminal integrated scheduling with multiple equipment.

Key words: Automated Container Terminal (ACT), Automated Guided Vehicle (AGV), charging strategy, terminal integrated scheduling, adaptive Non-dominated Sorting Genetic Algorithm-Ⅱ (NSGA-Ⅱ), power consumption

中图分类号:

TP301.6

薛海蓉, 韩晓龙. 基于改进NSGA-Ⅱ的考虑自动引导车充电策略的集成调度[J]. 计算机应用, 2023, 43(12): 3848-3855.

Hairong XUE, Xiaolong HAN. Integrated scheduling considering automated guided vehicle charging strategy based on improved NSGA-Ⅱ[J]. Journal of Computer Applications, 2023, 43(12): 3848-3855.

图/表 18

图1 ACT的实际布局

Fig.1 ACT actual layout

表1 参数说明

Tab.1 Parameters description

参数	说明
V	AGV集合，v∈V
K	岸桥集合，k∈K
H	场桥集合，h∈H
I	作业任务集合，I=1，2，…，l（l是作业任务）
I_k	岸桥k∈K的任务集合
I_h	场桥h∈H的任务集合
I_c	充电任务集合，I_c=l+1，l+2，…，l+l。如果AGV v在执行任务i∈I后前往充电站充电，那么该充电任务为任务l+i
I^*	所有任务集合，I^= I ∪ I_c， i，j∈ I^
I⁺	装载作业任务集合
I^-	卸载作业任务集合
M	一个足够大的数
G	AGV的最大电池容量，G为常数
β	作业性质，任务i为装载任务时，β_i =1，反之为0
g	AGV的充电阈值，当AGVv的电量小于g时，需要到充电站进行充电
δ₁，δ₂	AGVv分别处于空载行驶状态、负载行驶状态下的单位耗电量
$t i j k, t i j h, t i j v$	岸桥、场桥和AGV从任务i的结束位置移动到任务j的开始位置所需的时间，当j=i时表示岸桥、场桥从任务i的开始位置移动到结束位置所需的时间
μ	单位时间AGV充电速率，单位为A·h/s

表1 参数说明

Tab.1 Parameters description

参数	说明
V	AGV集合，v∈V
K	岸桥集合，k∈K
H	场桥集合，h∈H
I	作业任务集合，I=1，2，…，l（l是作业任务）
I_k	岸桥k∈K的任务集合
I_h	场桥h∈H的任务集合
I_c	充电任务集合，I_c=l+1，l+2，…，l+l。如果AGV v在执行任务i∈I后前往充电站充电，那么该充电任务为任务l+i
I^*	所有任务集合，I^= I ∪ I_c， i，j∈ I^
I⁺	装载作业任务集合
I^-	卸载作业任务集合
M	一个足够大的数
G	AGV的最大电池容量，G为常数
β	作业性质，任务i为装载任务时，β_i =1，反之为0
g	AGV的充电阈值，当AGVv的电量小于g时，需要到充电站进行充电
δ₁，δ₂	AGVv分别处于空载行驶状态、负载行驶状态下的单位耗电量
$t i j k, t i j h, t i j v$	岸桥、场桥和AGV从任务i的结束位置移动到任务j的开始位置所需的时间，当j=i时表示岸桥、场桥从任务i的开始位置移动到结束位置所需的时间
μ	单位时间AGV充电速率，单位为A·h/s

表2 变量说明

Tab.2 Variable description

变量	说明
x_vij	若AGVv在执行完任务i∈I^* 后执行任务j∈I^，则x_vij* =1；否则x_vij =0
y_kij	若岸桥k在执行完任务i∈I_k 后执行任务j∈I_k，则y_kij =1；否则y_kij =0
z_hij	若场桥h在执行完任务i∈I_h 后执行任务j∈I_h，则z_hi_j=1；否则z_hij =0
φ_vi	若AGVv执行任务i∈I，则φ_vi* =1；否则φ_vi =0
a_vi，A_vi	若任务i∈I*是AGVv的开始（结束）任务，则为1；反之为0
b_i，B_i	若任务i∈I是岸桥k的开始（结束）任务，则为1；反之为0
d_i，D_i	若任务i∈I是场桥h的开始（结束）任务，则为1；反之为0
f_i¹	岸桥k执行作业任务 $i ∈ I k$ 的结束时刻
f_i²	场桥h执行作业任务 $i ∈ I h$ 的结束时刻
f_i³	AGVv完成充电任务 $i ∈ I c$ 时的时刻
$u i 1$	岸桥k执行作业任务 $i ∈ I k$ 的开始时刻
$u i 2$	场桥h执行作业任务 $i ∈ I h$ 的开始时刻
r_vi	AGVv到达开始执行任务 $i ∈ I *$ 位置时的剩余电量
q_vi	AGVv执行充电任务 $i ∈ I c$ 时的排队时间
$p v i 1$	AGVv到达执行任务 $i ∈ I k$ 的岸桥k的时刻
$p v i 2$	AGVv到达执行任务 $i ∈ I h$ 的场桥h的时刻
$p v i 3$	AGVv执行充电任务 $i ∈ I c$ 到达充电站的时刻
E_vi	AGVv完成任务 $i ∈ I *$ 时的总耗电量

表2 变量说明

Tab.2 Variable description

变量	说明
x_vij	若AGVv在执行完任务i∈I^* 后执行任务j∈I^，则x_vij* =1；否则x_vij =0
y_kij	若岸桥k在执行完任务i∈I_k 后执行任务j∈I_k，则y_kij =1；否则y_kij =0
z_hij	若场桥h在执行完任务i∈I_h 后执行任务j∈I_h，则z_hi_j=1；否则z_hij =0
φ_vi	若AGVv执行任务i∈I，则φ_vi* =1；否则φ_vi =0
a_vi，A_vi	若任务i∈I*是AGVv的开始（结束）任务，则为1；反之为0
b_i，B_i	若任务i∈I是岸桥k的开始（结束）任务，则为1；反之为0
d_i，D_i	若任务i∈I是场桥h的开始（结束）任务，则为1；反之为0
f_i¹	岸桥k执行作业任务 $i ∈ I k$ 的结束时刻
f_i²	场桥h执行作业任务 $i ∈ I h$ 的结束时刻
f_i³	AGVv完成充电任务 $i ∈ I c$ 时的时刻
$u i 1$	岸桥k执行作业任务 $i ∈ I k$ 的开始时刻
$u i 2$	场桥h执行作业任务 $i ∈ I h$ 的开始时刻
r_vi	AGVv到达开始执行任务 $i ∈ I *$ 位置时的剩余电量
q_vi	AGVv执行充电任务 $i ∈ I c$ 时的排队时间
$p v i 1$	AGVv到达执行任务 $i ∈ I k$ 的岸桥k的时刻
$p v i 2$	AGVv到达执行任务 $i ∈ I h$ 的场桥h的时刻
$p v i 3$	AGVv执行充电任务 $i ∈ I c$ 到达充电站的时刻
E_vi	AGVv完成任务 $i ∈ I *$ 时的总耗电量

图2 染色体编码

Fig.2 Chromosome coding

图3 染色体顺序交叉

Fig.3 Order crossover of chromosome

图4 染色体两点交叉

Fig.4 Two-point crossover of chromosome

图5 染色体变异

Fig.5 Chromosome mutation

图6 自适应NSGA-Ⅱ的流程

Fig.6 Flowchart of adaptive NSGA-Ⅱ

表3 相关参数

Tab.3 Related parameters

类别	参数	数值
算法基本参数	P_c₁	0.8
	P_c₂	0.6
	种群数	40
	P_m₁	0.1
	P_m₂	0.01
	最大迭代次数	500
设备基本参数	速度/（m·s^-1）	2
	安全阈值/%	30
	充电率/（%·s^-1）	0.2
	重载耗电量/（%·s^-1）	0.4
	空载耗电量/（%·s^-1）	0.2
	岸桥操作时间/s	130
	场桥操作时间/s	120

表4 算法求解目标值及运行时间结果

Tab.4 Objective solution results and running time of algorithms

实验序号	任务数	AGV 数	CPLEX			NSGA-Ⅱ			MOPSO			自适应NSGA-Ⅱ
实验序号	任务数	AGV 数	f1/s	f2/Ah	time/s	f1/s	f2/Ah	time/s	f1/s	f2/Ah	time/s	f1/s	f2/Ah	time/s
1	10	3	2 485	1 059	200.0	2 470	922	55.6	3 072	1 020	52.4	2 460	920	53.7
2	10	4	1 925	825	49.9	1 898	780	55.7	2 369	893	53.4	1 805	739	54.2
3	15	4	3 075	1 538	773.8	3 131	1 432	113.7	3 984	1 590	112.3	3 044	1 403	111.5
4	15	6	2 510	1 258	144.3	2 283	1 102	118.6	3 145	1 388	116.7	2 193	1 079	115.7
5	20	4	5 130*	2 475*	3 600.0	4 585	2 231	199.7	5 652	2 412	200.9	4 456	2 180	192.6
6	20	6	3 620*	1 885*	3 600.0	3 417	1 867	216.9	4 492	2 138	220.5	3 351	1 794	216.7

表5 算法求解目标值差距对比

Tab.5 Comparison of difference between algorithm results

基础数据	自适应NSGA-Ⅱ与CPLEX/%		自适应NSGA-Ⅱ与NSGA-Ⅱ/%		自适应NSGA-Ⅱ与MOPSO/%
基础数据	GAP1	GAP2	GAP3	GAP4	GAP5	GAP6
平均值	6.91	10.57	2.80	2.63	24.03	14.46
10/3	1.01	13.13	0.41	0.22	19.92	9.80
10/4	6.23	10.42	4.90	5.26	23.81	17.25
15/4	1.01	8.88	2.78	2.03	23.59	11.76
15/6	12.63	14.23	3.94	2.09	30.27	22.26
20/4	13.14	11.92	2.81	2.29	21.16	9.62
20/6	7.43	4.83	1.93	3.91	25.40	16.09

图7 3种算法运行实验5某次得出的帕累托最优解集

Fig.7 Pareto optimal solution sets obtained from experiment 5 by three algorithms

图8 AGV耗电量变化

Fig.8 Changes of AGV power consumption

图9 Changes of AGV charging time proportion

Fig.9 AGV充电时间占比变化

图10 充电时间和充电次数随g变化的情况

Fig.10 Charging time and number of charges varying with g

图11 充电时间和充电次数随Pu变化的情况

Fig.11 Charging time and number of charges varying with Pu

图12 完工时间和AGV耗电量变化

Fig.12 Changes of completion time and AGV power consumption

图13 设备时间利用率变化

Fig. 13 Changes of time utilization of equipments

参考文献 22

1	LIU D， GE Y-E. Modeling assignment of quay cranes using queueing theory for minimizing CO₂ emission at a container terminal ［J］. Transportation Research Part D： Transport and Environment， 2018， 61（A）： 140-151. 10.1016/j.trd.2017.06.006
2	范厚明，岳丽君，李荡，等.考虑路径冲突的AGV配置与调度优化［J］.运筹与管理，2020，29（5）：43-51
	FAN H M， YUE L J， LI D， et al. Optimization of AGV dispatching and configuration considering path conflict ［J］. Operations Research and Management Science， 2020， 29（5）： 43-51.
3	ZHAO Q R， JI S W， GUO D， et al. Research on cooperative scheduling of automated quayside cranes and automatic guided vehicles in automated container terminal ［J］. Mathematical Problems in Engineering， 2019， 2019： No. 6574582. 10.1155/2019/6574582
4	周玉清，韩晓龙. 双循环策略下岸桥与跨运车的联合调度［J］.计算机应用： 2023，43（2）：645-653. 10.11772/j.issn.1001-9081.2021122042
	ZHOU Y Q， HAN X L. Joint operation of quay crane and straddle carrier under double-cycle strategy ［J］.Journal of Computer Applications，2023，43（2）： 645-653. 10.11772/j.issn.1001-9081.2021122042
5	YANG Y， ZHONG M， DESSOUKY Y， et al. An integrated scheduling method for AGV routing in automated container terminals ［J］. Computers & Industrial Engineering， 2018， 126： 482-493. 10.1016/j.cie.2018.10.007
6	JONKER T， DUINKERKEN M B， YORKE-SMITH N， et al. Coordinated optimization of equipment operations in a container terminal ［J］. Flexible Services and Manufacturing Journal， 2019， 33： 281-311.
7	ZHANG H， QI L， LUAN W， et al. Double-cycling AGV scheduling considering uncertain crane operational time at container terminals［J］. Applied Sciences，2022，12： No.4820. 10.3390/app12104820
8	陈铮荣. 考虑AGV无冲突路径规划的自动化集装箱码头集成调度［D］.北京：北京交通大学， 2020：5-7. 10.1016/j.cie.2020.106371
	CHEN Z R.Integrated scheduling considering AGV conflict-free path planning in automated container terminal ［D］. Beijing： Beijing Jiaotong University， 2020：5-7. 10.1016/j.cie.2020.106371
9	吴洪明，邹梦艳. 考虑电池电量约束的自动化码头AGV调度［J］. 起重运输机械， 2021（3）： 47-52.
	WU H M， ZOU M Y. AGV scheduling of automated terminal considering battery power constraints ［J］. Hoisting and Conveying Machinery， 2021（3）： 47-52.
10	SWEDA T M， DOLINSKAYA I S， KLABJAN D. Optimal recharging policies for electric vehicles ［J］. Transportation Science， 2017， 51（2）： 457-479. 10.1287/trsc.2015.0638
11	周小凡，苌道方，余芳，等. 考虑充电和等待时间的集装箱码头AGV调度［J］. 上海海事大学学报， 2019， 40（3）： 1-5，13.
	ZHOU X F， CHANG D F， YU F， et al. Scheduling of AGV in container terminals considering charging and waiting time ［J］. Journal of Shanghai Maritime University， 2019， 40（3）： 1-5，13.
12	张亚琦，杨斌，胡志华，等.自动化码头AGV充电与作业的集成调度研究［J］. 计算机工程与应用， 2017， 53（18）： 257-262，270. 10.3778/j.issn.1002-8331.1605-0003
	ZHANG Y Q， YANG B， HU Z H，et al. Research of AGV charging and job integrated scheduling at automated container terminal ［J］. Computer Engineering and Applications， 2017， 53（18）： 257-262，270. 10.3778/j.issn.1002-8331.1605-0003
13	赵涛，梁承姬，胡筱渊，等. 自动化集装箱码头AGV调度与换电双层模型求解［J］. 大连理工大学学报， 2021， 61（6）： 623-633.
	ZHAO T， LIANG C J， HU X Y，et al. Solution of AGV scheduling and battery exchange two-layer model for automated container terminal ［J］. Journal of Dalian University of Technology， 2021， 61（6）： 623-633.
14	陈珲，韩晓龙. 考虑充电策略的自动化码头AGV调度［J］. 上海海事大学学报， 2021， 42（2）： 20-25，74.
	CHEN H， HAN X L. AGV scheduling of automated terminals considering charging strategy ［J］. Journal of Shanghai Maritime University， 2021， 42（2）： 20-25，74.
15	傅正堂，胡志华，宗康. 集装箱码头AGV电量非饱和状态下的调度优化［J］. 大连海事大学学报， 2017， 43（3）： 58-62.
	FU Z T， HU Z H， ZONG K. Scheduling optimization of container terminal AGV under electricity unsaturation condition ［J］. Journal of Dalian Maritime University， 2017， 43（3）： 58-62.
16	谢旦岚，郭笛，纪媛，等.自动化码头运输设备充电策略优化的仿真研究［J］. 系统仿真学报， 2020， 32（10）： 1927-1935.
	XIE D L， GUO D， JI Y，et al. Simulation research on optimization of AGV charging strategy for automated terminal ［J］. Journal of System Simulation， 2020， 32（10）： 1927-1935.
17	DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA‑Ⅱ ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197. 10.1109/4235.996017
18	SRINIVAS M， PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms ［J］. IEEE Transactions on Systems， Man， and Cybernetics， 1994， 24（4）： 656-667. 10.1109/21.286385
19	ZHAN X， XU L， ZHANG J， et al. Study on AGVs battery charging strategy for improving utilization ［J］. Procedia CIRP， 2019， 81： 558-563. 10.1016/j.procir.2019.03.155
20	COELLO C A C， PULIDO G T， LECHUGA M S. Handling multiple objectives with particle swarm optimization ［J］. IEEE Transactions on Evolutionary Computation， 2004，8（3）： 256-279. 10.1109/tevc.2004.826067
21	CHEN J C， CHEN T-L， TENG Y-C. Meta-model based simulation optimization for automated guided vehicle system under different charging mechanisms ［J］. Simulation Modelling Practice and Theory， 2021， 106： 102208. 10.1016/j.simpat.2020.102208
22	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

[1]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.
[2]	高一鹭, 胡志华. 基于时空网络的自动化集装箱码头自动化导引车路径规划[J]. 计算机应用, 2020, 40(7): 2155-2163.
[3]	刘育良, 陈淮莉. 负载影响下纯电动汽车配送路径规划及充电策略[J]. 计算机应用, 2020, 40(10): 2831-2837.
[4]	魏亚茹, 朱瑾. 自动化码头双场桥调度与集装箱存储选位建模[J]. 计算机应用, 2018, 38(4): 1189-1194.
[5]	张洁, 杨春玉, 鞠非, 徐小龙. 基于二次聚类的大规模电动汽车有序充电调度策略优化[J]. 计算机应用, 2017, 37(10): 2978-2982.
[6]	周静娴, 胡志华. 自动化集装箱码头穿越式双自动堆码起重机调度优化[J]. 计算机应用, 2015, 35(9): 2673-2677.