考虑道路负载均衡的码头多AGV无冲突路径规划

doi:10.12141/j.issn.1000-565X.230227

摘要/Abstract

摘要：

随着集装箱运输需求的日益增长以及新型信息技术的广泛应用，集装箱码头作业自动化成为国内外港口发展的主要趋势。集装箱码头作业自动化可有效提高码头的作业效率和安全性，降低码头对人力资源的需求和运营成本。水平运输系统是集装箱码头装卸系统的重要组成部分，同时也是实现集装箱在码头前沿与堆场之间运转的重要纽带，其运行的稳定性和调度的合理性将直接影响码头自动化装卸系统的运行效率。自动导引车（AGV）是自动化集装箱码头常用的水平运输设备，承担着从前沿岸桥到后方堆场的集装箱运输任务。在实际作业过程中，多辆AGV同时运作难免会发生冲突和拥堵。基于此，文中采用基于冲突搜索的双层算法（CBS算法）解决码头多AGV协同作业产生的冲突问题，上层算法搜索AGV间的冲突，下层算法采用A*算法对AGV进行路径规划，并在A*算法中引入负载因子，使得规划路径避开拥堵点，实现码头道路的负载均衡。对于码头多任务点连续作业场景下的多车路径规划，基于CBS算法采用一种滑动时间窗冲突解决方法（STWCR）以提升运算效率。通过仿真实验验证了文中所提算法能够有效解决码头多AGV路径规划的冲突问题，同时均衡路网负载，缓解道路局部拥堵现象，提高道路资源的利用率。研究成果为自动化集装箱码头水平运输系统优化提供了参考。

关键词: 自动化集装箱码头, 路径规划, 冲突规避, 道路负载均衡, A*算法

Abstract:

With the increasing demand for container transportation and the widespread application of new information technologies, the automation of container terminal operations has become the main development trend in domestic and international ports. It can not only effectively improve the efficiency and safety of terminal operations, but also significantly reduce the demand for human resources and the operational costs. The horizontal transportation system is an essential part of the container terminal handling system and an important link enabling the highly efficient container transportation between the quayside and the storage yard, so its operational reliability and the reasonableness of the scheduling directly affect the operational efficiency of the automated container handling system. The mostly used horizontal transportation equipment in container terminals is the automated guided vehicles (AGVs), which is responsible for horizontal transportation from the front quay crane to the rear yard in automated container terminals. In actual operation process, conflicts and congestion is inevitable when multiple AGVs operate simultaneously. On this basis, this paper used conflict-based search (CBS) to solve the conflict problem arising from the cooperative operation of multi-AGVs at the terminal. The upper layer algorithm searched for conflicts among AGVs, while the lower layer algorithm used the A* algorithm for path planning of AGVs. A load factor was introduced into the heuristic function of the A* algorithm in order to avoid congestion in the path planning and achieve load balancing on terminal roads. Further, a sliding time window conflict resolution (STWCR) based on CBS was adopted to improve computational efficiency for multiple AGVs path planning in the continuous operation scenario of multiple task points at the terminal. Simulation experiments verified that the proposed algorithm in this paper can effectively solve the conflict problem of multiple AGVs path planning at the terminal, while balancing the road network load, alleviating local road congestion, and improving the utilization of road resources. The research results of this paper provide a reference for the optimization of the horizontal transportation system in automated container terminals.

Key words: automated container terminal, path planning, conflict avoidance, road load balancing, A* algorithm

中图分类号:

U691

温惠英, 元昱青, 林译峰. 考虑道路负载均衡的码头多AGV无冲突路径规划[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 1-10.

WEN Huiying, YUAN Yuqing, LIN Yifeng. Conflict-Free Path Planning For Multi-AGVs in Automated Terminals Considering Road Load Balancing[J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(10): 1-10.

图/表 17

图1

图2

图3

图4

图5

图6

图7

表1

表2

图8

图9

表3

表4

图10

表5

图11

图12

参考文献 26

1	XIE S T， HU J Y， BHOWMICK P，et al ．Distributed motion planning for safe autonomous vehicle overtaking via artificial potential field［J］．IEEE Transactions on Intelligent Transportation Systems，2022，23（11）：21531-21547.
2	HUANG Y， DING H， ZHANG Y，et al ．A motion planning and tracking framework for autonomous vehicles based on artificial potential field elaborated resistance network approach［J］．IEEE Transactions on Industrial Electronics，2019，67（2）：1376-1386.
3	AZZABI A， NOURI K ．An advanced potential field method proposed for mobile robot path planning［J］．Transactions of the Institute of Measurement and Control，2019，41（11）：3132-3144.
4	LIYUN X， NING W， XUFENG L ．Study on conflict-free AGVs path planning strategy for workshop material distribution systems［J］．Procedia CIRP，2021，104：1071-1076.
5	ZHONG M， YANG Y， DESSOUKY Y，et al ．Multi-AGV scheduling for conflict-free path planning in automated container terminals［J］．Computers & Industrial Engineering，2020，142：106371.
6	ZHOU Y， HUANG N ．Airport AGV path optimization model based on ant colony algorithm to optimize Dijkstra algorithm in urban systems［J］．Sustainable Computing：Informatics and Systems，2022，35：100716.
7	许伦辉，曹宇超，林培群．基于多影响因素RDMA~*算法的无人驾驶动态路径规划［J］．交通信息与安全，2020，38（2）：24-36.
	XU Lunhui， CAO Yuchao， LIN Peiqun. Dynamic path planning for unmanned driving based on multi-influencing factors RDMA* algorithm［J］．Journal of Transport Information and Safety，2020，38（2）：24-36.
8	WU M P， GAO J， LI L，et al ．Control optimisation of automated guided vehicles in container terminal based on Petri network and dynamic path planning［J］．Computers & Electrical Engineering，2022，104：108471.
9	YUE L， FAN H ．Dynamic scheduling and path planning of automated guided vehicles in automatic container terminal［J］．IEEE/CAA Journal of Automatica Sinica，2022，9（11）：2005-2019.
10	左秀峰，沈万杰．基于Floyd算法的多重最短路问题的改进算法［J］．计算机科学，2017，44（5）：232-234，267.
	ZUO Xiufeng， SHEN Wanjie ．Improved algorithm about muti-shortest path problem based on floyd algorithm［J］．Computer Science，2017，44（5）：232-234，267.
11	SINGGIH I K， HONG S， KIM K H ．Flow path design for automated transport systems in container terminals considering traffic congestion ［J］．Industrial Engineering & Management Systems，2016，15（1）：19-31.
12	MARTIN J， CASQUERO O， FORTES B，et al ．A generic multi-layer architecture based on ROS-JADE integration for autonomous transport vehicles［J］．Sensors，2018，19（1）：69.
13	高一鹭，胡志华．基于时空网络的自动化集装箱码头自动化导引车路径规划［J］．计算机应用，2020，40（7）：2155-2163.
	GAO Yilu， HU Zhihua ．Path planning for automated guided vehicles based on tempo-spatial network at automated container terminal［J］．Journal of Computer Applications，2020，40（7）：2155-2163.
14	LI Q， POGROMSKY A， ADRIAANSEN T，et al ．A control of collision and deadlock avoidance for automated guided vehicles with a fault-tolerance capability［J］．International Journal of Advanced Robotic Systems，2016，13（2）：64.
15	张素云，杨勇生，梁承姬，等．自动化码头多AGV路径冲突的优化控制研究［J］．交通运输系统工程与信息，2017，17（2）：83-89.
	ZHANG Suyun， YANG Yongsheng， LIANG Chengji，et al ．Optimal control of multiple AGV path conflict in automated terminals［J］．Journal of Transportation Systems Engineering and Information Technology，2017，17（2）：83-89.
16	张中伟，张博晖，代争争，等．基于动态优先级策略的多AGV无冲突路径规划［J］．计算机应用研究，2021，38（7）：2108-2111.
	ZHANG Zhongwei， ZHANG Bohui， DAI Zhengzheng， et al. RMulti-AGV conflict-free path planning based on dynamic priority strategy ［J］. Application Research of Computers，2021，38（7）：2108-2111.
17	LIANG C， ZHANG Y， DONG L. A three stage optimal scheduling algorithm for AGV route planning considering collision avoidance under speed control strategy［J］．Mathematics，2022，11（1）：138.
18	SMOLIC-ROCAK N， BOGDAN S， KOVACIC Z，et al ．Time windows based dynamic routing in multi-AGV systems［J］．IEEE Transactions on Automation Science and Engineering，2010，7（1）：151-155.
19	万千．基于CBS算法的物流分拣多AGV路径规划的研究［D］．哈尔滨：哈尔滨工业大学，2018.
20	GUO K， ZHU J， SHEN L ．An improved acceleration method based on multi-agent system for AGVs conflict-free path planning in automated terminals［J］．IEEE Access，2020，9：3326-3338
21	李静．基于在线学习的自动化码头AGV调度方法研究［D］．大连：大连理工大学，2018.
22	SHARON G， STERN R， GOLDENBERG M，et al ．The increasing cost tree search for optimal multi-agent pathfinding［J］．Artificial Intelligence，2013，195：470-495.
23	SHARON G， STERN R， FELNER A，et al ．Conflict-based search for optimal multi-agent pathfinding［J］．Artificial Intelligence，2015，219：40-66.
24	MA H， LI J Y， KUMAR T K S，et al ．Lifelong multi-agent path finding for online pickup and delivery tasks ［C］∥Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems （AAMAS）．Sao Paulo：ACM，2017：837-845
25	HU Y， YANG H， HUANG Y ．Conflict-free scheduling of large-scale multi-load AGVs in material transportation network［J］．Transportation Research Part E：Logistics and Transportation Review，2022，158：102623.
26	刘恒麟．多AGV路径规划算法的研究与实现［D］．南京：东南大学，2020.

作业点	Y₁	Y₂	Y₃	Y₄	Y₅
坐标	（14，6）	（14，6）	（14，16）	（14，26）	（14，26）
作业点	Y₆	Y₇	Y₈	Y₉
坐标	（14，36）	（14，46）	（14，51）	（14，56）

车辆数	C/时间步		冲突数/个		C偏差/%
车辆数	CBS	IPF	CBS	IPF	C偏差/%
9	293	292	0	2	0.34
10	335	334	0	3	0.30
11	361	359	0	2	0.56
12	390	388	0	4	0.52
13	406	405	0	3	0.25
14	439	436	0	5	0.69
15	473	471	0	4	0.42
16	496	493	0	6	0.61
17	598	594	0	8	0.67
18	613	608	0	10	0.82

车辆数	C/时间步		C偏差/%
车辆数	算法1	算法2	C偏差/%
9	1 458	1 450	0.55
10	1 677	1 669	0.48
11	1 854	1 851	0.16
12	2 046	2 045	0.05
13	2 149	2 151	0.09
14	2 350	2 349	0.04
15	2 564	2 563	0.04
16	2 688	2 679	0.33
17	2 917	2 917	0.00
18	3 074	3 070	0.13

车辆数	C/时间步		C偏差/%
车辆数	实验1	实验2	C偏差/%
9	1 454	1 454	0.00
10	1 669	1 671	0.12
11	1 851	1 851	0.00
12	2 045	2 046	0.05
13	2 145	2 151	0.28
14	2 349	2 354	0.21
15	2 562	2 563	0.04
16	2 679	2 682	0.11
17	2 917	2 923	0.21
18	3 070	3 073	0.10

[1]	庄陵, 刘宇航. 密集城市群中基于智能反射面的传输方案[J]. 华南理工大学学报(自然科学版), 2024, 52(3): 112-118.
[2]	姚道金, 殷雄, 罗真, 等. 复杂环境下AGVS路径规划算法[J]. 华南理工大学学报(自然科学版), 2023, 51(11): 56-62.
[3]	陈朋, 江勇奇, 俞天纬, 等. 基于局部软约束优化的无人机航迹规划方法[J]. 华南理工大学学报(自然科学版), 2022, 50(6): 27-36.
[4]	魏武, 韩进, 李艳杰, 等. 基于双树 Quick-RRT* 算法的移动机器人路径规划[J]. 华南理工大学学报（自然科学版）, 2021, 49(7): 51-58.
[5]	温惠英, 林译峰, 吴昊书, 等. 基于城市道路交通环境演变的 ECEA 路径规划算法[J]. 华南理工大学学报（自然科学版）, 2021, 49(10): 1-10.
[6]	张家旭, 杨雄, 施正堂, 等. 汽车紧急换道避障的路径规划与跟踪控制[J]. 华南理工大学学报（自然科学版）, 2020, 48(9): 86-93,106.
[7]	赵星吉康林灏徐鹏. 基于多目标路径规划的应急资源配置模型[J]. 华南理工大学学报(自然科学版), 2019, 47(4): 76-82.
[8]	洪晓斌魏新勇黄烨笙刘艳霞肖国权. 融合图像识别和 VFH + 的无人艇局部路径规划方法 [J]. 华南理工大学学报(自然科学版), 2019, 47(10): 24-33.
[9]	潘晓芳周顺平杨林万波. OD 约束的出租车经验模型与路径规划[J]. 华南理工大学学报（自然科学版）, 2017, 45(8): 57-64,83.
[10]	张好剑苏婷婷吴少泓郑军王云宽. 基于改进遗传算法的并联机器人分拣路径优化[J]. 华南理工大学学报（自然科学版）, 2017, 45(10): 93-99.
[11]	吴玉香王超. 一种改进的移动机器人三维路径规划方法[J]. 华南理工大学学报（自然科学版）, 2016, 44(9): 53-60.
[12]	周熙阳杨兆升张伟邴其春商强. 考虑信号交叉口转向类型的最优路径规划算法[J]. 华南理工大学学报（自然科学版）, 2016, 44(4): 101-108.
[13]	章权温惠英孙博. 适于配送车辆导航路径规划的遍历模型的改进型粒子群优化算法[J]. 华南理工大学学报（自然科学版）, 2011, 39(8): 109-112,117.
[14]	王福元徐家文. 整体叶轮分步法数控电解加工工艺与关键技术[J]. 华南理工大学学报（自然科学版）, 2010, 38(8): 72-77.
[15]	崔建勋安实崔娜, . 基于时间扩展网络的区域疏散公交路径规划[J]. 华南理工大学学报（自然科学版）, 2010, 38(3): 64-69.