Integrated scheduling considering automated guided vehicle charging strategy based on improved NSGA-Ⅱ

doi:10.11772/j.issn.1001-9081.2022121923

Abstract

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

摘要：

针对自动引导车（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充电策略及设备数量配比对码头多设备集成调度有一定影响。

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

CLC Number:

TP301.6

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.

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

Figures/Tables 18

Fig.1 ACT actual layout

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

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

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 *$ 时的总耗电量

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 *$ 时的总耗电量

Fig.2 Chromosome coding

Fig.3 Order crossover of chromosome

Fig.4 Two-point crossover of chromosome

Fig.5 Chromosome mutation

Fig.6 Flowchart of adaptive NSGA-Ⅱ

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

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

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

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

Fig.8 Changes of AGV power consumption

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

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

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

Fig.12 Changes of completion time and AGV power consumption

Fig. 13 Changes of time utilization of equipments

References 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]	Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291.
[2]	LIU Shize, QIN Yanjun, WANG Chenxing, GAO Cunyuan, LUO Haiyong, ZHAO Fang, WANG Baohui. Transportation mode recognition algorithm based on multi-scale feature extraction [J]. Journal of Computer Applications, 2021, 41(6): 1573-1580.
[3]	YANG Wei, LI Ran, ZHANG Kun. Task allocation optimization for automated guided vehicles based on variable neighborhood simulated annealing algorithm [J]. Journal of Computer Applications, 2021, 41(10): 3056-3062.
[4]	LIU Yuliang, CHEN Huaili. Distribution path planning and charging strategy for pure electric vehicles with load constraint [J]. Journal of Computer Applications, 2020, 40(10): 2831-2837.
[5]	ZHANG Jie, YANG Chunyu, JU Fei, XU Xiaolong. Optimization of ordered charging strategy for large scale electric vehicles based on quadratic clustering [J]. Journal of Computer Applications, 2017, 37(10): 2978-2982.
[6]	WEI Pei, JIANG Ping, HE Jingjing, ZHANG Huimeng. Ultra wideband indoor localization based on inner triangle centroid algorithm [J]. Journal of Computer Applications, 2017, 37(1): 289-293.
[7]	SONG Guozhi, WANG Cheng, TU Yao, ZHANG Dakun. Low power mapping based on improved genetic algorithm with Prim initial population selection for 3D network-on-chip [J]. Journal of Computer Applications, 2017, 37(1): 90-96.
[8]	CHEN Pengzhan, LI Jie, LUO Man. Study of human motion tracking system based on wireless sensor network [J]. Journal of Computer Applications, 2015, 35(8): 2316-2320.
[9]	ZUO Cheng, YU Hongfang. Reliability-aware virtual data center embedding algorithm [J]. Journal of Computer Applications, 2015, 35(2): 299-304.
[10]	GUO Binglei, YU Jiong, LIAO Bin, YANG Dexian. Dynamic power consumption profiling and modeling by structured query language [J]. Journal of Computer Applications, 2015, 35(12): 3362-3367.
[11]	XU Jun-yong PAN Yu LING Chen. Power-aware resource scheduling under cloud computing environment [J]. Journal of Computer Applications, 2012, 32(07): 1913-1915.
[12]	LI Ran GUO Bing SHEN Yan WANG Ji-he WU Yuan-sheng LIU Yun-ben. Power-related hardware/software partitioning based on Hopfield neural network and tabu search [J]. Journal of Computer Applications, 2011, 31(03): 822-825.
[13]	. Research and application of synchronization compensation mechanism in wireless sensor networks [J]. Journal of Computer Applications, 2010, 30(4): 892-894.
[14]	. Design and implementation of real-time power measurement system for server's key energy components [J]. Journal of Computer Applications, 2010, 30(10): 2846-2849.
[15]	. Design and implementation of I/O power consumption simulation modules of power consumption simulator HMSim [J]. Journal of Computer Applications, 2010, 30(07): 1987-1990.