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.
CHEN Yini(陈旖旎), JIANG Zuhua* (蒋祖华)
. Multi-AGVs Scheduling with Vehicle Conflict Consideration in Ship Outfitting Items Warehouse[J]. Journal of Shanghai Jiaotong University(Science), 2024
, 29(3)
: 492
-508
.
DOI: 10.1007/s12204-022-2561-z
[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.
