Multi-AGVs Scheduling with Vehicle Conflict Consideration in Ship Outfitting Items Warehouse

doi:10.1007/s12204-022-2561-z

Abstract

Abstract: The inbound and outbound tasks for valuable imported ship outfitting items are operated by multiple automated guided vehicles (AGVs) simultaneously in the outfitting warehouse. Given the efficiency mismatch between transportation equipment and the lack of effective scheduling of AGVs, the objective of the studied scheduling problem is to minimize the total travel time cost of vehicles. A multi-AGV task scheduling model based on time window is established considering the loading constraints of AGVs and cooperation time window constraints of stackers. According to the transportation characteristics in the outfitting warehouse, this study proposes a conflict detection method for heavy forklift AGVs, and correspondingly defines a conflict penalty function. Furthermore, to comprehensively optimize travel time cost and conflict penalty, a hybrid genetic neighborhood search algorithm (GA-ANS) is proposed. Five neighborhood structures are designed, and adaptive selection operators are introduced to enhance the ability of global search and local chemotaxis. Numerical experiments show that the proposed GA-ANS algorithm can effectively solve the problem even when the scale of the problem increases and the effectiveness of the vehicle conflict penalty strategy is analyzed.

Key words: ship outfitting items warehouse, multi-AGVs scheduling, time window, hybrid algorithm

摘要： 船舶舾装件立体仓储由多辆自动引导小车（AGV）同时作业，对配托后的管阀件、设备备件等舾装件进行出入库作业，针对堆垛机与AGV作业效率不匹配以及AGV缺乏有效调度的现状，以天为调度周期，以最小化车辆能源消耗为目标，考虑多种类型AGV托盘的承重约束、堆垛机协同作业时间窗约束，建立基于时间窗的多AGV作业任务调度模型。针对舾装件仓储内车辆运输特性，提出一种冲突检测方法并定义了惩罚项函数。此外，综合考虑车辆效率和冲突概率，提出一种遗传邻域搜索混合算法（GA-ANS），并设计五种领域结构，引入自适应选择算子增强和均衡全局搜索与局部趋化能力。数值实验验证表明了算法可以求解较优的调度方案，并对车辆冲突惩罚策略的有效性进行了分析。

关键词: 舾装件立体仓储，多车辆调度，时间窗，混合优化算法

CLC Number:

TP391

CHEN Yini(陈旖旎), JIANG Zuhua^* (蒋祖华). Multi-AGVs Scheduling with Vehicle Conflict Consideration in Ship Outfitting Items Warehouse[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 492-508.

References

[1] QIU L, HSU W J, HUANG S Y, et al. Scheduling and routing algorithms for AGVs: A survey [J]. International Journal of Production Research, 2002, 40(3): 745-760.
[2] SHAN T, CHENG X, CHEN J. A spare parts warehouse management system based on bar code technology and bluetooth technology [J]. Ship Electronic Engineering, 2008, 28(3): 145-147 (in Chinese).
[3] TANG W, PENG W, SU S, et al. Slotting optimization of multi-roadway automated high-rise warehouse for shipping industry [J]. Computer Integrated Manufacturing Systems, 2020, 26(2): 384-392 (in Chinese).
[4] UDHAYAKUMAR P, KUMANAN S. Task scheduling of AGV in FMS using non-traditional optimization techniques [J]. International Journal of Simulation Modelling, 2010, 9(1): 28-39.
[5] NISHI T, HIRANAKA Y, GROSSMANN I E. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles [J]. Computers & Operations Research, 2011, 38(5): 876-888.
[6] WANG Y, PENG Y, PAN F. Scheduling algorithm for vehicles in warehouses based on greedy algorithm and genetic algorithm [J]. Transducer and Microsystem Technologies, 2012, 31(10): 25-128 (in Chinese).
[7] SAIDI-MEHRABAD M, DEHNAVI-ARANI S, EVAZABADIAN F, et al. An Ant Colony Algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs [J]. Computers & Industrial Engineering, 2015, 86: 2-13.
[8] JIANG J Z, LIU G. Research on intelligent scheduling in multi-robot intelligent warehouse system [J]. Mechanical & Electrical Engineering Technology, 2017, 46(9): 82-84 (in Chinese).
[9] YUE X H, XU X J, WANG X B. Research on multiAGV scheduling algorithm based on improved hybrid PSO-GA for FMS [J]. Computer Science, 2018, 45(S2): 167-171 (in Chinese).
[10] KUMAR M V S, JANARDHANA R, RAO C S P. Simultaneous scheduling of machines and vehicles in an FMS environment with alternative routing [J]. The International Journal of Advanced Manufacturing Technology, 2011, 53(1/2/3/4): 339-351.
[11] WANG T C, XU B L. AGV configuration and scheduling analysis based on queuing theory [J]. Machinery Design & Manufacture, 2020(4): 266-269 (in Chinese).
[12] ZHANG Z W, CHEN B, CHEN W D. Dynamic routing of automated guided vehicles with time window [J]. Microcomputer Applications, 2016, 32(11): 46-49 (in Chinese).
[13] ZHU L B, WANG H, WANG J L, et al. Research on path planning of parking system based on dynami time window [J]. Chinese Journal of Engineering Design, 2017, 24(4): 440-448 (in Chinese).
[14] TAI R C, WANG J C, CHEN W D. A prioritized planning algorithm of trajectory coordination based on time windows for multiple AGVs with delay disturbance [J]. Assembly Automation, 2019, 39(5): 753-768.
[15] LIAN Y D, XIE W, ZHANG L W. A probabilistic time-constrained based heuristic path planning algorithm in warehouse multi-AGV systems [J]. IFACPapersOnLine, 2020, 53(2): 2538-2543.
[16] DAHAL K, HOSSAIN A, VARGHESE B, et al. Scheduling in multiprocessor system using genetic algorithms [C]//2008 7th Computer Information Systems and Industrial Management Applications. Ostrava: IEEE, 2008: 281-286.
[17] OLMI R, SECCHI C, FANTUZZI C. Coordination of industrial AGVs [J]. International Journal of Vehicle Autonomous Systems, 2011, 9(1/2): 5-25.
[18] JIANG Z H, CHEN Y N, LI X Y, et al. A heuristic optimization approach for multi-vehicle and one-cargo green transportation scheduling in shipbuilding [J]. Advanced Engineering Informatics, 2021, 49: 101306.
[19] WOLFINGER D. A large neighborhood search for the pickup and delivery problem with time windows, split loads and transshipments [J]. Computers & Operations Research, 2021, 126: 105110.
[20] ZHONG M S, YANG Y S, DESSOUKY Y, et al. MultiAGV scheduling for conflict-free path planning in automated container terminals [J]. Computers & Industrial Engineering, 2020, 142: 106371.
[21] CHEN T J, SUN Y, DAI W, et al. On the shortest and conflict-free path planning of multi-AGV system based on dijkstra algorithm and the dynamic time-window method [J]. Advanced Materials Research, 2013, 645: 267-271.