考虑冲突规避的自动化集装箱码头AGV优化调度方法

丁一; 袁浩; 方怀瑾; 田宇

doi:10.3963/j.jssn.1674-4861.2022.03.010

考虑冲突规避的自动化集装箱码头AGV优化调度方法

doi: 10.3963/j.jssn.1674-4861.2022.03.010

丁一^1, ,,
袁浩¹,
方怀瑾²,
田宇²

1.
上海海事大学物流工程与科学研究院上海 201306
2.
上海国际港务（集团）股份有限公司上海 201306

基金项目:

国家重点研发计划项目 2019YFB1704400

国家重点研发计划项目 2019YFB1704405

详细信息

通讯作者:
丁一（1980—），博士，副教授. 研究方向：港航运作优化. E-mail：yiding@shmtu.edu.cn

中图分类号: U693
计量
- 文章访问数: 1439
- HTML全文浏览量: 561
- PDF下载量: 108
- 被引次数: 0
出版历程
- 收稿日期: 2022-01-21
- 网络出版日期: 2022-07-25

An Optimal Scheduling Method of AGVs at Automated Container Terminal Considering Conflict Avoidance

DING Yi^{1
, ,},
YUAN Hao¹,
FANG Huaijin²,
TIAN Yu²

1.
Institute of Logistics Science and Engineering, Shanghai Maritime University Shanghai 201306, China
2.
Shanghai International Port (Group) Co., Ltd., Shanghai 201306, China

摘要

摘要: 合理调度自动化导引车（AGV）对于降低自动化集装箱码头的作业成本具有重要意义。针对AGV调度中的任务分配和路径规划问题，考虑AGV电量和多载等因素，结合自动化码头布局特点，以AGV作业总时间最小和多AGV作业路径无冲突分别为第一阶段和第二阶段的优化目标建立两阶段模型。设计改进模拟退火算法求解第一阶段模型，为了加速算法收敛并保证解的质量，解的改进优先考虑任务的时间成本和AGV数量；设计基于时空网络的路径规划算法求解第二阶段模型，将作业区域离散成网格网络后添加时间信息构建可更新的时空网络，在时空网络上运用最短路径算法规划路径并规避冲突。对于任务分配不均衡导致的路径规划无可行解的拥堵情况，在冲突规避基础上重新计算AGV执行任务的成本并再次进行任务分配，不断迭代直到生成多AGV间路径无冲突的调度方案。以洋山四期自动化集装箱码头为例进行仿真实验与对比分析，结果表明：与使用传统路径规划和避障策略的AGV调度方法对比，所提方法下的总作业时间平均降低了7.31%，AGV冲突数量降低为0，任务总延期时间最大降低2 895 s，最大降低路网拥堵度10.79%，验证了提出方法解决冲突规避和拥堵问题的有效性。
- 交通规划 /
- AGV调度 /
- 冲突规避 /
- 时空网络模型 /
- 模拟退火 /
- 耦合模型
Abstract: Scheduling of automated guided vehicles (AGVs) is crucial for improving the operational efficiency of automated container terminals. In this paper, a two-stage optimization model is proposed for task allocation and path planning of AGVs with the consideration of the following factors: the remaining power supply of the AGV, multiple loads, and the characteristics of automated port layout. During the first stage of the optimization, a task allocation model is used to minimize the total operation time of AGVs, while a path planning model is used to optimize the operation paths of AGVs in the second stage, which will prevent the conflicts between AGVs. A new simulated annealing algorithm is developed to solve the proposed task allocation model. To guarantee an acceptable running time of the algorithm and the quality of the solution, the time cost of the task and the number of AGVs are prioritized in the process of improving the solution algorithm. A path planning algorithm based on time-space network is designed to solve the path planning problem, which discretizes the work area into a grid network and adds revised time information to develop an updated time-space network. It searches for the shortest path based on the network, while detecting conflicts and adjusting routes to avoid collisions and congestion of paths. Under the congestion scenarios, where there is no feasible solution for path planning due to unbalanced task assignment, the cost of AGV tasks will be recalculated based on conflict avoidance and their tasks will be reassigned again. Simulation experiment and comparative analysis are carried out for the case study automated container terminal (Phase Ⅳ) of the Yangshan Port. The proposed method for scheduling of AGVs is compared with a traditional path planning and obstacle avoidance model. study results show that the total operation time is reduced by 7.31% on average. The conflicts between AGVs are totally removed. The total task delay is reduced by 2 895 s, and the network congestion is reduced by 10.79%.
- traffic planning /
- scheduling of AGV /
- conflict avoidance /
- spatiotemporal network model /
- simulated annealing /
- coupled model

HTML全文

图 1 自动化码头布局

Figure 1. The layout of automatic port

下载: 全尺寸图片幻灯片

图 2 AGV作业流程图

Figure 2. AGV operation flowchart

下载: 全尺寸图片幻灯片

图 3 传统码头和自动化码头路网示意图

Figure 3. Schematic diagram of traditional wharf and automated wharf road network

下载: 全尺寸图片幻灯片

图 4 普通A*或Dijkstra路径规划结果

Figure 4. Result of Dijkstra or A* path planning

下载: 全尺寸图片幻灯片

图 5 时空网络模型

Figure 5. Spatiotemporal network model

下载: 全尺寸图片幻灯片

图 6 AGV冲突类型

Figure 6. AGV conflict type

下载: 全尺寸图片幻灯片

图 7 基于时空网络的路径规划

Figure 7. Path planning based on spatiotemporal network

下载: 全尺寸图片幻灯片

图 8 算法流程图

Figure 8. Algorithm flowchart

下载: 全尺寸图片幻灯片

图 9 冲突示意图

Figure 9. Conflict diagram

下载: 全尺寸图片幻灯片

图 10 冲突规避示意图

Figure 10. Conflict Avoidance Diagram

下载: 全尺寸图片幻灯片

表 1 任务分配模型参数表

Table 1. Theparameters ofthe task allocation model

N	所有任务集合，N={1，2, …，2n}
P	提货任务集合, p={1, 2, …，n}
D	交付任务集合，D ={n + 1, n + 2, …, 2n}
K	AGV集合
r	AGV的安全电量
a_i	任务i最早可以执行时间
l_i	任务i的最晚执行时间
t_ijk	AGV k执行任务i后执行任务j的时间成本，i节点到j节点的距离除以AGV的恒定速度
O	AGV充电站(初始节点）
s_i	任务i的执行时间
q	AGV的额定载重量
T_ik	AGV k到达任务节点i的时间
e_ik	表示AGV k访问完任务节点i的电量
q_ik	AGV k到达节点i的载重量
a	行驶单位时间消耗电量

下载: 导出CSV

表 2 路径规划模型参数表

Table 2. The parameters of the path planning model

O	充电站所在位置
K	JGV集合
T	时间段集合，（1, 2, …，n)
V	拓扑图节点集合
V_m	节点m的相邻顶点集
E	拓扑图弧集合，由(m, n) 表示，其中E中不包含m到自身的虚拟边(m, m)
W	任务集合
W_ktm	用负责运输的AGV k，到达时间t，拓扑图中的目标节点位置m来表示

下载: 导出CSV

表 3 不同冲突类型解决方法

Table 3. Different conflict types resolution methods

冲突类型	传统解决方法	新策略等待时长
追赶冲突	AGV速度恒定，一般不做考虑	AGV速度恒定，一般不做考虑
相向冲突	重新规划路径	高优先级AGV离开该车道时间-低优先级进人该车道时间
占位冲突	重新规划路径	高优先级AGV离开节点时间-低优先级AGV进人该节点时间
节点冲突	等待或者重新规划路径	高优先级AGV离开该节点时间-低优先级AGV进人该节点时间

下载: 导出CSV

表 4 小规模算例

Table 4. Small-scale study

任务编号	任务坐标	需求	最早开始时间/s	最迟完成时间/s	服务时间/s	P_i	D_i
0	(0, 0)	0	0	0	0	0	0
1	(1, 1)	20	1	21	1	0	2
2	(2, 1)	-20	2	34	2	1	0
3	(1, 3)	40	5	22	2	0	4
4	(0, 3)	-40	10	20	2	3	0
5	(0, 4)	40	4	19	2	0	6
6	(2, 3)	-40	8	21	2	5	0
7	(2, 0)	40	3	23	2	0	8
8	(1, 2)	-40	7	16	2	7	0
9	(0, 1)	20	4	17	2	0	10
10	(1, 1)	-20	6	21	1	9	0
11	(1, 4)	40	11	23	2	0	12
12	(0, 1)	-40	13	26	1	11	0

下载: 导出CSV

表 5 第1次迭代结果

Table 5. Results of the first iteration

AGV编号	任务分配	AGV的时空路径
AGV1	0-5-6-11-1 2-10	(0, 0, 0)(0，1，1)((0, 2, 2)(0, 3, 3)(0, 4, 4)(0, 4, 5)(0, 4, 6)(1，4, 7)(2, 4, 8)(2, 3, 9)(2, 3, 10)(2, 3, 11)(2, 2, 12)(2, 1, 13)(1, 1, 14)(1, 2, 15)(1, 3, 16)(1, 4, 17)(1, 4, 18)(1，4，19)(0, 4, 20)(0, 3, 21)(0, 2, 22)(0，1，23)(0，1，24)(0，1，25)(0, 0, 26)
AGV2	0-7-8-0	(0, 0, 0)(1，0，1)(2, 0, 2)(2, 0, 3)(2, 0, 4)(2，1，5)(2, 2, 6)(1，2, 7)(1，2, 8)(1，2, 9)(0, 2，10)(0，1，11)(0, 0，12)
AGV3	0-1-2-3-4-9-10-0	(0, 0, 0)(0, 0，1)(1，0, 2)(1，1，3)(1，1，4)(2, 1, 5)(2, 1, 6)(2, 1, 7)

下载: 导出CSV

表 6 AGV调度结果

Table 6. AGV scheduling results

AGV编号	任务分配	AGV时空路径
AGV1	0-5-6-0	(0, 0, 0)(0，1，1)(0, 2, 2)(0, 3, 3)(0, 4, 4)(0, 4, 5)(0, 4, 6)(0, 3, 7)(1，3, 8)(2, 3, 9)(2, 3，10)(2, 3，11)(2, 2，12)(2，1，13)(2, 0, 14)(1, 0, 15)(0, 0, 16)
AGV2	0-9-10-7-8-0	(0, 0, 0)(0, 0，1)(0，1，2)(0，1，3)(0，1，4)(1，1，5)(1，1，6)(1，1，7)(1，2, 8)(1，3, 9)(1, 4, 10)(1, 3, 11)(1, 4, 12)(1, 4, 13)(1, 4, 14)(1, 3, 15)(1, 2, 16)(1, 1, 17)(1, 0, 18)(2, 0，19)(2, 0, 20)(2, 0, 21)(2，1，22)(2, 2, 23)(1, 2, 24(1, 2, 25)(1, 2, 26)(1, 1, 27)(1, 0, 28)(0, 0, 29)
AGV3	0-1-2-3-4-0	(0, 0, 0)(1，0，1)(1，1，2)(1，1，3)(2，1，4)(2，1，5)(2，1，6)(2, 2, 7)(2, 3, 8)(2, 3, 9)(1，3，10)(1，3，11)(1，3，12)(0, 3，13)(0, 3, 14)(0, 3, 15)(0, 2, 16)(0, 1, 17)(0, 0, 18)

下载: 导出CSV

表 7 路网参数

Table 7. Road network parameters

区域	参数设置
AGV	速度4m/s，电量可供AGV行驶时间为14min
AGV作业区域	作业区域总长取288 m，宽147 m，海侧装卸区7条双向车道，陆侧8条车道，等待区域28条车道
岸桥	12个岸桥，岸桥间距离为24 m
堆场箱区	12个箱区，间隔取24 m

下载: 导出CSV

表 8 不同算法求解速度对比

Table 8. The speed comparison of different algorithms

任务规模/个	求解速度/s
任务规模/个	GUROBI	FSA_TSN	GA_TSN
10	23.34	17.45	17.43
20	89.45	28.56	45.24
30	356.24	35.34	57.62
40	923.65	44.56	73.56
100	3 786.45	87.82	156.57

下载: 导出CSV

表 9 TAP-TSN和TAP-SP冲突数量对比

Table 9. Comparison of the number of conflicts between TAP-TSN and TAP-SP

算例	任务规模/个	冲突数量/次		作业总时间/s
算例	任务规模/个	TAP-TSN	TAP-SP	TAP-SP	TAP-TSN (规避前）	TAP-SP (规避后）
1	20	0	0	1 876	1 876	1 894
2	50	0	22	4 573	4 234	4 745
3	100	0	43	9 158	9 120	10 236
4	200	0	150	19 123	18 126	21 361
5	300	0	183	29 342	28 921	32 498
6	400	0	278	40 076	39 742	42 576
7	500	0	310	51 452	50 672	54 782
8	600	0	421	64 074	62 453	68 294

下载: 导出CSV

表 10 三阶段调度模型与本文模型对比

Table 10. Comparison between three-stage scheduling model and this model

算例	任务规模/个	任务延期时间/s		规避冲突后冲突数量/次		路网拥堵度/%
算例	任务规模/个	TAP-TSN	传统调度	TAP-TSN	传统调度	TAP-TSN	传统调度
1	100	186	924	0	12	2.62	6.23
2	100	164	935	0	24	1.73	7.32
3	100	155	1 042	0	21	1.64	8.57
4	200	526	2 072	0	43	4.83	9.32
5	200	482	1 925	0	26	3.87	8.42
6	200	641	2 145	0	10	3.18	10.28
7	300	956	2 346	0	15	4.34	11.96
8	300	1 648	2 662	0	102	6.26	12.34
9	300	1 351	2 743	0	87	5.84	11.73
10	400	1 482	4 072	0	32	3.42	13.76
11	400	1 194	3 938	0	46	2.37	13.32
12	400	1 287	4 182	0	123	3.26	14.34

下载: 导出CSV

参考文献(22)

[1]	GRUNOW M, GUNTHER H, LEHMANN M. Dispatching multi-load AGVs in highly automated seaport container terminals[J]. OR Spectrum, 2006(26): 211–235.
[2]	霍凯歌, 张亚琦, 胡志华. 自动化集装箱码头多载AGV调度问题研究[J]. 大连理工大学学报, 2016, 56(3): 244–251. https://www.cnki.com.cn/Article/CJFDTOTAL-DLLG201603004.htm HUO K G, ZHANG Y Q, HU Z H. Research on scheduling problem of multi-load AGV at automated container terminal[J]. Journal of Dalian University of Technology, 2016, 56 (3): 244–251(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-DLLG201603004.htm
[3]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056–3062. doi: 10.11772/j.issn.1001-9081.2020121919 YANG W, LI R, ZHANG K. Multi-AGV task allocation optimization based on variable neighborhood simulation annealing algorithm[J]. Journal of Computer Applications, 2021, 41 (10): 3056–3062. (in Chinese). doi: 10.11772/j.issn.1001-9081.2020121919
[4]	LIM J, KIM K, YOSHIMOTO K. et al. A dispatching method for automated guided vehicles by using a bidding concept[J]. OR Spectrum, 2003, 25(1): 25–44. doi: 10.1007/s00291-002-0116-0
[5]	周润, 龙伟, 李炎炎, 等. 面向绿色再制造系统的AGV路径规划研究[J]. 四川大学学报(自然科学版), 2019, 56(5): 883–889. doi: 10.3969/j.issn.0490-6756.2019.05.014 ZHOU R, LONG W, LI Y Y, et al. Research on AGV path planning for green remanufacturing systems[J]. Sichuan University Journal(Natural Science Edition), 2019, 56(5): 883–889. (in Chinese) doi: 10.3969/j.issn.0490-6756.2019.05.014
[6]	QING G, ZHENG Z, YUE X. Path-planning of automated guided vehicle based on improved Dijkstra algorithm[C]. Control Decision Conference, Melbourne, Australia: IEEE, 2017.
[7]	LYU X, SONG Y, HE C, et al. Approach to integrated scheduling problems considering optimal number of automated guided vehicles and conflict-free routing in flexible manufacturing systems[J]. IEEE Access, 2019, 7(1): 74909–74924.
[8]	张中伟, 张博晖, 代争争. 基于动态优先级策略的多AGV无冲突路径规划[J]. 计算机应用, 2021, 38(7): 2108–2111. https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ202107035.htm ZHANG Z W, ZHANG B H, DAI Z Z. Multi-AGV conflict-free path planning based on dynamic priority strategy[J]. Computer Applications, 2021, 38(7): 2108–2111. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ202107035.htm
[9]	KRISHNAMURTHY N, BATTA R, KARWAN M. Developing conflict-free routes for automated guided vehicles[J]. Operations Research, 1993, 41(6): 1077–1090. doi: 10.1287/opre.41.6.1077
[10]	CORREA A I, ANDRE L, LOUIS R. Scheduling and routing of automated guided vehicles: A hybrid approach[J]. Computers & Operations Research, 2007, 34(6): 1688–1707.
[11]	余娜娜, 李铁克, 王柏琳, 等. 自动化分拣仓库中多AGV调度与路径规划算法[J]. 计算机集成制造系统, 2020, 26(1): 171–180. YU N N, LI T K, WANG B L, et al. Multi-AGV scheduling and path planning algorithms in automated sorting warehouses[J]. Computer Integrated Manufacturing Systems, 2020, 26 (1): 171–180. (in Chinese)
[12]	KEISUKE M. Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system[J]. Computers & Industrial Engineering, 2020, 141(1): 1–10.
[13]	HU Y, DONG L, XU L. Multi-AGV dispatching and routing problem based on a three-stage decomposition method[J]. Mathematical Biosciences and Engineering, 2020, 17(5): 5150–5172. doi: 10.3934/mbe.2020279
[14]	李静, 朱小林. 集装箱码头上多自动引导车的调度和路径规划[J/OL]. (2022-01-25)[2022-1-20]. http://kns.cnki.net/kcms/detail/11.5946.TP.20210618.1850.016.html. LI J, ZHU X L. Scheduling and path planning of multi-AVS on container terminals[J/OL]. (2022-01-25)[2022-1-20]. http://kns.cnki.net/kcms/detail/11.5946.TP.20210618.1850.016.html.
[15]	JI S, LUAN D, CHEN Z, et al. Integrated scheduling in automated container terminals considering AGV conflict-free routing[J]. Transportation Letters-the International Journal of Transportation Research, 2020, 13(2): 1–14.
[16]	曾庆成, 李明泽, 薛广顺. 考虑拥堵因素的自动化码头多AGV无冲突动态路径规划模型[J]. 大连海事大学学报, 2019, 45(4): 35–44. ZENG Q C, LI M Z, XUE G S. Multi-AGV conflict-free dynamic path planning model for automated terminals considering congestion factors[J]. Journal of Dalian Maritime University, 2019, 45(4): 35–44. (in Chinese)
[17]	张素云, 杨勇生, 梁承姬, 等. 自动化码头多AGV路径冲突的优化控制研究[J]. 交通运输系统工程与信息, 2017, 17 (2): 83–89. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201702013.htm ZHANG S Y, YANG Y S, LIANG C J, et al. Optimal control of multiple AGV path conflict in automated terminals[J]. Transportation Systems Engineering and Information Technology, 2017, 17(2): 83–89. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201702013.htm
[18]	祁文祥, 陆志强, 孙小明. 带软时间窗的集货与送货多车辆路径问题节约算法[J]. 交通运输工程学报, 2010, 10(2): 99–103. doi: 10.3969/j.issn.1671-1637.2010.02.018 QI W X, LU Z Q, SUN X M. Saving Algorithm for Collecting and Delivery Multi-vehicle Path Problem with Soft Time Window[J]. Journal of Transportation Engineering, 2010, 10 (2): 99–103(in Chinese). doi: 10.3969/j.issn.1671-1637.2010.02.018
[19]	高一鹭, 胡志华. 基于时空网络的自动化集装箱码头自动化导引车路径规划[J]. 计算机应用, 2020, 40(7): 2155–2163. GAO Y L, HU Z H. Path planning for automated guided vehicles based on tempo-spatial network at automated container terminal[J]. Computer Applications, 2020, 40 (7): 2155–2163(in Chinese)
[20]	李文霞, 张春民, 马昌喜. 多目标低碳车辆路径优化模型及求解算法[J]. 交通信息与安全, 2020, 38(1): 118–126. https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS202001018.htm LI W X, ZHANG C M, MA C X. Multi-objective low-carbon vehicle routing optimization model and solution algorithm[J]. Journal of Transport Information and Safety, 2020, 38(1): 118–126(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS202001018.htm
[21]	VU D N, KAP H K. Dispatching method for automated lifting vehicles in automated port container terminals[J]. Computers & Industrial Engineering, 2009, 56(3): 1002–1020.
[22]	KIM K H, JEON S M, RYU K R. Deadlock prevention for auto-mated guided vehicles in automated container terminals[J]. ORSpectrum, 2006, 28(4): 659–679.