Research On Path Planning And Scheduling Technology Of Multiple Four-Direction Shuttles

The storage strategy of traditional shuttle vehicle intensive warehouse is "first in,first out".Only one kind of goods can be stored in the same aisle,and the cross-aisle operation of Shuttle Railway Guided Vehicle(SRGV)in the same layer can only rely on the handling of stacker.With the continuous development of modern intelligent logistics,the development of intensive storage has ushered in new opportunities.Four-direction Shuttle compact storage and retrieval system(FS-CS/RS)came into being,which is a new type of intensive storage.As the key component of FS-CS/RS,Four-direction Shuttle(FS)originated in Europe in 2013 and then was introduced into China,and was first exhibited at Ce MAT asiaz in 2015.FS can cooperate with the elevator to carry out the warehouse in and out operation(I/O),realizing the cross-layer and cross-aisle transportation of goods.Besides,different goods can be stored in the same aisle of FSCS/RS,which greatly improves the storage efficiency and reduces the operation cost of storage.However,how to dynamically determine the reasonable FS’s operation path and avoid multi vehicle traffic congestion or even deadlock when multiple FSs are operating in the same layer is a severe challenge in the promotion and application of FS.Therefore,supported by the scientific research project of Shanghai Science and Technology Commission(17dz2283800)and the collaborative service oriented efficient intelligent storage system development and demonstration application project of Songjiang District in 2018,this project will study the path planning and traffic scheduling technology in the single layer of FS-CS/RS from the following aspects:(1)Modeling of electronic map and digraph for FS’s operationIn order to solve the problem of FS’s optimal path planning and traffic jam when multiple vehicles are conducting different tasks at the same time,the demand of FSCS/RS in detail is analyzed at first,then the grid model of electronic map according to the actual storage environment is established,and finally the problem model and algorithm directed graph model of FS’s optimal path search is given further.For the problem of multi vehicle traffic congestion,this paper proposes a directed graph model of traffic jam mode based on graph theory,which is a Directed Graph Model of Traffic Jam Mode shorted for DGMTJ.FSs are taken as the vertexes and the traffic relationship between them are taken as the edges,the congestion between vehicles is described in the form of digraph model,which clarifies the problem of multi-vehicle path planning and congestion avoidance scheduling,and provides the data structure foundation for the function design of subsequent path planning and scheduling algorithm.(2)Path planning of multi-vehicle congestion avoidance based on A* algorithmConsidering that frequent turning in the process of FS’s actual task execution and there may be overlapping areas between the multi-vehicle’s paths,a multi vehicle path planning algorithm is proposed by improving A* algorithm.Firstly,the assignment of vehicles to execute the task based on some principles are selected,such as FS’s shortest travelling path,least cross-layer times and balance of job scheduling frequency.Secondly,the improved A* algorithm is adopted to search the optimal path planning of FSs,taking the shortest travelling path of FS and the least number of turns in the layer as the optimized objectives.The risk cost is introduced into the heuristic function ?(9))of A* algorithm to evaluate collision risk degree between FSs according to the distance between the overlapping area and the vehicle.The overlapping area with high collision risk increases the path cost and reduces the path search priority in the risk area to achieve the optimal path planning without traffic jam of multiple FSs.The results after doing experiment indicate that the proposed algorithm can make FSs effectively avoid obstacles and congestion while searching an optimal path,which compared with the traditional A* algorithm under the multi vehicle parallel environment.(3)Research on multi vehicle traffic scheduling technologyConsidering the problems of traffic jam and interlock when multiple vehicles are executing tasks at the same time,a real-time multi vehicle traffic scheduling algorithm based on DGMTJ is proposed.Firstly,the path overlaps and position relationship of every two vehicles are measured based on the real-time position status of the car.Secondly,the traffic jam relationship of FS is identified in advance according to the prior rules of congestion pattern determination,such as path intersection,rear end collision and encounter,and the corresponding DGMTJ is established in real time.Then,the blocking dependence chain in DGMTJ is analyzed,and the stop control command is sent to the blocked item in advance to avoid blocking.According to the obtained prior information of traffic jam mode and the real-time status of the car,the congested item is added to the obstacle set dynamically,and the improved A* algorithm is called again to replan the remaining paths of the blocked items in real time in order to solve the problem of multi-vehicle traffic deadlock.The results after experiments indicate that the proposed traffic scheduling algorithm can make FS avoid congestion in real-time and has a timely response.(4)Implementation and application of FS path planning and scheduling algorithm moduleBy using technology of OPC communication,web service and SQL Server database,the path planning and traffic scheduling algorithm module is designed and developed,realizing its integration with Warehouse Management and Control System(WMCs),and the application test in the enterprise initially verified the effectiveness of the function module proposed in this paper,providing the key technical basis for the promotion and application of FS-CS/RS.