上海交通大学学报 ›› 2023, Vol. 57 ›› Issue (1): 93-102.doi: 10.16183/j.cnki.jsjtu.2021.223
所属专题: 《上海交通大学学报》2023年“机械与动力工程”专题
收稿日期:
2021-06-05
修回日期:
2021-08-03
出版日期:
2023-01-28
发布日期:
2023-01-13
通讯作者:
陈璐
E-mail:chenlu@sjtu.edu.cn.
作者简介:
裘柯钧(1999-),本科生,从事飞机总装生产物流配送相关研究.
基金资助:
QIU Kejun, BAO Zhongkai, CHEN Lu()
Received:
2021-06-05
Revised:
2021-08-03
Online:
2023-01-28
Published:
2023-01-13
Contact:
CHEN Lu
E-mail:chenlu@sjtu.edu.cn.
摘要:
为了实现自动引导车(AGV)在某民用客机总装车间的高效运作,提出AGV任务分配与路径规划两阶段求解方法,有效地解决了车间内AGV的多次往返配送调度问题.在任务分配阶段,提出基于行程的AGV任务分配模型,提高任务分配的效率;在路径规划阶段,采用时间窗算法,对AGV占用的地图资源进行时间窗的初始化、更新和排布,并针对由于避障和等待引起的物料送达时间无法满足的情况,设计了料包交换、优先级提前、预留时长放宽共3种递进的调整策略,实现AGV的无冲突路径规划.在数值实验中,两阶段方法应用于50、100、150个料包问题的平均求解时间分别为15.86、41.12、162.29 s,表明两阶段方法有效缓解了多行程AGV调度问题的复杂性,能在合理时间内实现民用客机总装车间AGV的调度优化,以适应民用客机年产量逐年快速递增的生产需求.
中图分类号:
裘柯钧, 鲍中凯, 陈璐. 民用客机总装车间自动引导车任务分配及路径规划[J]. 上海交通大学学报, 2023, 57(1): 93-102.
QIU Kejun, BAO Zhongkai, CHEN Lu. Task Assignment and Path Planning for Automatic Guided Vehicles in Aircraft Assembly Workshop[J]. Journal of Shanghai Jiao Tong University, 2023, 57(1): 93-102.
表2
部分AO料包的物料需求计划
AO编号 | 需求时间/h | 目标工位 | AO编号 | 需求时间/h | 目标工位 |
---|---|---|---|---|---|
150C08RW6040 | 0 | 暂存区3 | 140C08ZF3401 | 8 | 暂存区2 |
150C08RW6030 | 0 | 暂存区3 | 140C08ZF3300 | 8 | 暂存区2 |
140C07BS0080 | 0 | 暂存区2 | 140C08ZF2500 | 8 | 暂存区2 |
140C05DA0030 | 0 | 暂存区2 | 140C08ZF2400 | 8 | 暂存区2 |
130C06KS0010 | 0 | 暂存区1 | 140C08ZF2100 | 8 | 暂存区2 |
130C01PJ0050 | 0 | 暂存区1 | 130C01RS0010 | 8 | 暂存区1 |
150C03RD0260 | 1 | 暂存区3 | 130C01KS0010 | 8 | 暂存区1 |
150C03JD0010 | 1 | 暂存区3 | 150C04SA0010 | 8.25 | 暂存区3 |
150C03DD0210 | 1 | 暂存区3 | 150C04AA0070 | 8.25 | 暂存区3 |
150C03DD0160 | 1 | 暂存区3 | 150C05SA0040 | 9 | 暂存区3 |
表4
料包数为50、100、150的各算例求解时长和调整策略
算例编号 | 料包数 | 求解时长/s | 调整策略 | 算例编号 | 料包数 | 求解时长/s | 调整策略 |
---|---|---|---|---|---|---|---|
1 | 50 | 5.30 | — | 16 | 100 | 79.17 | — |
2 | 50 | 18.01 | — | 17 | 100 | 60.97 | 优先级提前 |
3 | 50 | 23.48 | — | 18 | 100 | 31.20 | — |
4 | 50 | 20.55 | — | 19 | 100 | 23.75 | — |
5 | 50 | 11.29 | — | 20 | 100 | 34.81 | — |
6 | 50 | 23.55 | — | 21 | 150 | 167.17 | 料包交换 |
7 | 50 | 14.72 | — | 22 | 150 | 197.26 | 料包交换 |
8 | 50 | 20.32 | — | 23 | 150 | 215.47 | 料包交换 |
9 | 50 | 14.70 | — | 24 | 150 | 122.01 | 料包交换 |
10 | 50 | 6.71 | — | 25 | 150 | 115.22 | 料包交换 |
11 | 100 | 24.29 | — | 26 | 150 | 163.90 | — |
12 | 100 | 57.54 | — | 27 | 150 | 113.82 | 料包交换 |
13 | 100 | 23.01 | — | 28 | 150 | 193.61 | — |
14 | 100 | 34.48 | — | 29 | 150 | 95.58 | — |
15 | 100 | 42.00 | — | 30 | 150 | 238.81 | 料包交换 |
表5
算例17的最优任务分配方案
行程 编号 | AGV编号 | ||||
---|---|---|---|---|---|
AGV1 | AGV2 | AGV3 | AGV4 | AGV5 | |
行程1 | 16, 37 | 24, 28 | 14, 29 | 30, 34 | 20, 23 |
行程2 | 52, 64 | 45, 61 | 15, 26 | 9, 18 | 66, 73 |
行程3 | 42, 47 | 41, 43 | 53, 59 | 31, 36 | 19, 90 |
行程4 | 55, 93 | 48, 57 | 50, 58 | 51, 62 | 21, 67 |
行程5 | 32, 35 | 46, 56 | 25, 79 | 54, 63 | 22, 68 |
行程6 | 11, 12 | 6, 39 | 13, 38 | 7, 17 | 1, 2 |
行程7 | 49, 65 | 8, 33 | 75, 76 | 27, 69 | 100, 74 |
行程8 | 77, 82 | 98, 99 | 10, 40 | 89, 96 | 4, 5 |
行程9 | 78, 88 | 70, 72 | 94, 95 | 91, 92 | 3, 84 |
行程10 | 85, 86 | 71, 83 | 80, 97 | 81, 87 | 44, 60 |
[1] |
HU H T, CHEN X Z, WANG T S, et al. A three-stage decomposition method for the joint vehicle dispatching and storage allocation problem in automated container terminals[J]. Computers & Industrial Engineering, 2019, 129: 90-101.
doi: 10.1016/j.cie.2019.01.023 URL |
[2] |
ZOU W Q, PAN Q K, MENG T, et al. An effective discrete artificial bee colony algorithm for multi-AGVs dispatching problem in a matrix manufacturing workshop[J]. Expert Systems with Applications, 2020, 161: 113675.
doi: 10.1016/j.eswa.2020.113675 URL |
[3] | 夏扬坤, 符卓, 谢九勇. 依订单拆分的多自动导引车物料配送路径规划[J]. 计算机集成制造系统, 2017, 23(7): 1520-1528. |
XIA Yangkun, FU Zhuo, XIE Jiuyong. Material distribution route planning for multiple automated guided vehicles with split deliveries by order[J]. Computer Integrated Manufacturing Systems, 2017, 23(7): 1520-1528. | |
[4] |
ZOU W Q, PAN Q K, WANG L. An effective multi-objective evolutionary algorithm for solving the AGV scheduling problem with pickup and delivery[J]. Knowledge-Based Systems, 2021, 218(3): 106881.
doi: 10.1016/j.knosys.2021.106881 URL |
[5] | 汤红杰, 王鼎, 皇攀凌, 等. 优化Dijkstra算法在工厂内物流AGV路径规划的研究[J]. 机械设计与制造, 2018(1): 117-120. |
TANG Hongjie, WANG Ding, HUANG Panling, et al. AGV path planning based on optimized Dijkstra algorithm in logistics factory[J]. Machinery Design & Manufacture, 2018(1): 117-120. | |
[6] | RADHIA Z, KHALED M, SIMON C D, et al. A hybrid method for assigning containers to AGVs in container terminal[J]. IFAC-PapersOnLine, 2016, 49(3): 96-103. |
[7] | WANG C B, WANG L, Qin J, et al. Path planning of automated guided vehicles based on improved A-star algorithm[C]//2015 IEEE International Conference on Information and Automation. Lijiang, China: IEEE, 2019: 2071-2076. |
[8] | FRANTISEK D, ANDREJ B, MARTIN K, et al. Path planning with modified A star algorithm for a mobile robot[J]. Procedia Engineering, 2014(96): 59-69. |
[9] | 赵大兴, 余明进, 许万. 基于高适应度值遗传算法的AGV最优路径规划[J]. 计算机工程与设计, 2017, 38(6): 1635-1641. |
ZHAO Daxing, YU Mingjin, XU Wan. AGV optimal path planning based on genetic algorithms of large fitness value[J]. Computer Engineering and Design, 2017, 38(6): 1635-1641. | |
[10] |
ZHONG M S, YANG Y S, YASSER D, et al. Multi-AGV scheduling for conflict-free path planning in automated container terminals[J]. Computers & Industrial Engineering, 2020, 142: 106371
doi: 10.1016/j.cie.2020.106371 URL |
[11] | 罗强, 王海宝, 崔小劲, 等. 改进人工势场法自主移动机器人路径规划[J]. 控制工程, 2019, 26(6): 1091-1098. |
LUO Qiang, WANG Haibao, CUI Xiaojing, et al. Autonomous mobile robot path planning based on improved artificial potential method[J]. Control Engineering of China, 2019, 26(6): 1091-1098. | |
[12] |
程志, 张志安, 李金芝, 等. 改进人工势场法的移动机器人路径规划[J]. 计算机工程与应用, 2019, 55(23): 29-34.
doi: 10.3778/j.issn.1002-8331.1904-0472 |
CHENG Zhi, ZHANG Zhi’an, LI Jinzhi, et al. Mobile robots path planning based on improved artificial potential field[J]. Computer Engineering and Applications, 2019, 55(23): 29-34.
doi: 10.3778/j.issn.1002-8331.1904-0472 |
|
[13] |
XING L, LIU Y, LI H, et al. A novel tabu search algorithm for multi-AGV routing problem[J]. Mathematics, 2020, 8(2): 279.
doi: 10.3390/math8020279 URL |
[14] | 曾庆成, 李明泽, 薛广顺. 考虑拥堵因素的自动化码头多AGV无冲突动态路径规划模型[J]. 大连海事大学学报, 2019, 45(4): 35-44. |
ZENG Qingcheng, LI Mingze, XUE Guangshun. Multiple AGV conflict-free dynamic routing model in automated terminals considering congestion factors[J]. Journal of Dalian Maritime University, 2019, 45(4): 35-44. | |
[15] | 刘辉, 肖克, 王京擘. 基于多智能体强化学习的多AGV路径规划方法[J]. 自动化与仪表, 2020, 35(2): 84-89. |
LIU Hui, XIAO Ke, WANG Jingbo. Multi-AGV path planning method based on multi-agent reinforcement learning[J]. Automation & Instrumentation, 2020, 35(2): 84-89. | |
[16] |
MURAKAMI K. Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system[J]. Computers & Industrial Engineering, 2020, 141: 106270.
doi: 10.1016/j.cie.2020.106270 URL |
[17] |
杨雅洁, 苌道方, 余芳. 考虑AGV避碰的自动化码头多资源协同调度[J]. 计算机工程与应用, 2020, 56(6): 246-253.
doi: 10.3778/j.issn.1002-8331.1812-0069 |
YANG Yajie, CHANG Daofang, YU Fang. Multi-resource coordinated scheduling of automated terminals considering AGV collision avoidance[J]. Computer Engineering and Applications, 2020, 56(6): 246-253.
doi: 10.3778/j.issn.1002-8331.1812-0069 |
|
[18] | 泰应鹏, 邢科新, 林叶贵, 等. 多AGV路径规划方法研究[J]. 计算机科学, 2017(Sup.2): 84-87. |
TAI Yingpeng, XING Kexin, LIN Yegui, et al. Research of path planning in multi-AGV system[J]. Computer Science, 2017(Sup.2): 84-87. | |
[19] |
KELEN V, LUIS F R, NADIA J M, et al. Integrated tasks assignment and routing for the estimation of the optimal number of AGVS[J]. The International Journal of Advanced Manufacturing Technology, 2016, 82(1/2/3/4): 719-736.
doi: 10.1007/s00170-015-7343-4 URL |
[20] | HAO J, WANG C, YANG M, et al. Hybrid genetic algorithm based dispatch and conflict-free routing method of AGV systems in unmanned underground parking lots[C]//2020 IEEE International Conference on Real-time Computing and Robotics. Asahikawa, Japan: IEEE, 2020: 475-480. |
[21] | RIAZI S, DIDING T, FALKMAN P, et al. Scheduling and routing of AGVs for large-scale flexible manufacturing systems[C]//2019 IEEE 15th International Conference on Automation Science and Engineering. Vancouver, Canada: IEEE, 2019: 891-896. |
[22] |
余翀, 邱其文. 基于栅格地图的分层式机器人路径规划算法[J]. 中国科学院大学学报, 2013, 30(4): 528-538.
doi: 10.7523/j.issn.2095-6134.2013.04.015 |
YU Chong, QIU Qiwen. Hierarchical robot path planning algorithm based on grid map[J]. Journal of University of Chinese Academy of Sciences, 2013, 30(4): 528-538.
doi: 10.7523/j.issn.2095-6134.2013.04.015 |
|
[23] | 胡彬, 王冰, 王春香, 等. 一种基于时间窗的自动导引车动态路径规划方法[J]. 上海交通大学学报, 2012, 46(6): 967-971. |
HU Bin, WANG Bing, WANG Chunxiang, et al. Dynamic routing of automated guided vehicles based on time window[J]. Journal of Shanghai Jiao Tong University, 2012, 46(6): 967-971. |
[1] | 黄鹤, 高永博, 茹锋, 杨澜, 王会峰. 基于自适应黏菌算法优化的无人机三维路径规划[J]. 上海交通大学学报, 2023, 57(10): 1282-1291. |
[2] | . 基于栅格图特征点提取下的蚁群算法路径规划[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(1): 86-99. |
[3] | 陈禹伊, 陈璐. 车辆路径规划问题的逆向优化方法[J]. 上海交通大学学报, 2022, 56(1): 81-88. |
[4] | 郑书坚, 赵文杰, 钟永建, 贺敏, 赵文龙. 面向多目标拦截问题的协同任务分配方法研究[J]. 空天防御, 2021, 4(3): 55-64. |
[5] | 张贇, 邱忠宇, 蔡云泽. 基于偏好联盟博弈的导弹集群分布式任务分配模型[J]. 空天防御, 2021, 4(3): 24-32. |
[6] | 李昭莹, 欧一鸣, 石若凌. 基于深度Q网络的改进RRT路径规划算法[J]. 空天防御, 2021, 4(3): 17-23. |
[7] | 刘西, 李贤, 陈伟, 从光涛, 李如飞. 基于NSGA-Ⅲ算法的多目标分配方法研究[J]. 空天防御, 2021, 4(1): 109-116. |
[8] | 李征, 陈建伟, 彭博. 基于伪谱法的无人机集群飞行路径规划[J]. 空天防御, 2021, 4(1): 52-59. |
[9] | 倪安宁1,刘晏尘1,崔毓伟1,卢军莉2. 评价公交行程时间可靠性价值的Mixed Logit模型[J]. 上海交通大学学报(自然版), 2019, 53(2): 146-152. |
[10] | 刘洋,陈璐. 养护车辆路径规划的鲁棒性优化方法[J]. 上海交通大学学报(自然版), 2018, 52(4): 388-394. |
[11] | 乐健,张华,叶艳辉,范宇. 基于旋转电弧传感机器人立焊焊缝的跟踪[J]. 上海交通大学学报(自然版), 2015, 49(03): 348-352. |
[12] | 杨乘东,钟继勇,陈玉喜,陈善本. 基于视觉识别的多层多道路径规划修正[J]. 上海交通大学学报(自然版), 2015, 49(03): 297-300. |
[13] | 许波,闵华清,肖芳雄. 蚁群算法求解离散最小约束去除问题[J]. 上海交通大学学报(自然版), 2015, 49(03): 383-386. |
[14] | 陈侠,魏晓明,徐光延. 多无人机模糊态势的分布式协同空战决策[J]. 上海交通大学学报(自然版), 2014, 48(07): 907-913. |
[15] | 张铁,欧阳帆. 双机器人协调跟随运动的运动学分析与路径规划[J]. 上海交通大学学报(自然版), 2013, 47(08): 1251-1256. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||