CN108357848B - Modeling optimization method based on Multilayer shuttle car automated storage and retrieval system - Google Patents

Abstract

The invention discloses a modeling optimization method for an automatic storage system based on a multi-layer shuttle car, which includes: determining the movement rules of the hoist and the shuttle car and various service times during the operation process of the hoist and the shuttle car; respectively extracting the multi-layer shuttle The number of floors of the automatic storage system, the depth of the roadway, the height of a single shelf, the width of a single compartment, the speed and acceleration of the hoist, the speed and acceleration of the shuttle car, the time of a single pick-up and release, and the detailed information of the outbound task Parameters, establish a mathematical model of the multi-storey shuttle automatic storage system; build a mixed integer programming model with the goal of obtaining the shortest total pick-up time; use the GUROBI linear programming solver to solve the mixed integer programming model to obtain the shortest total pick-up time Delivery time and the optimal pick-up order of the system. The invention can quickly estimate the performance of the system under various shelves and equipment configurations, and provide decision support for the precise design of the system, the improvement of equipment utilization rate, and the saving of operating costs.

Description

Modeling optimization method based on multi-storey shuttle car automatic storage system

technical field

The invention relates to the technical field of automated three-dimensional warehouses, in particular to a modeling optimization method based on an automatic storage system of a multi-layer shuttle vehicle.

Background technique

In the traditional automated three-dimensional warehouse, the stacker is responsible for the storage and retrieval of goods, so the modeling of the traditional automated three-dimensional warehouse only needs to analyze the single equipment of the stacker.

With the development of orders to small batches and multi-batches, the automatic storage system of multi-storey shuttle vehicles is gradually put into use. Compared with the traditional automated three-dimensional warehouse, the multi-storey shuttle car automatic storage system uses elevators and shuttle cars to pick up goods, which greatly improves work efficiency. As shown in Figure 1, the multi-storey shuttle car automatic storage system is equipped with a hoist at the entrance of each roadway to be responsible for the vertical movement of the goods in the roadway and transport the goods to the I/O platform; each layer of shelves There is a shuttle car responsible for the horizontal movement of the goods on this layer. Obviously, the traditional modeling method of automated three-dimensional warehouse is only for the stacker, which is not suitable for the complex model of the multi-storey shuttle system. Previously, there have been many modeling methods for the automatic storage system of multi-storey shuttle vehicles, but most of them are based on queuing theory and other theories to establish approximate estimation models, and the accuracy of the modeling results needs to be improved.

Therefore, it is necessary to conduct in-depth research and improvement on the modeling method of the outbound task of the multi-storey shuttle automatic storage system, and find a more accurate modeling method. How to solve the problem that the modeling method of the traditional automated three-dimensional warehouse in the prior art is not suitable for the modeling of the outbound tasks of the multi-storey shuttle automatic storage system, how to solve the modeling of the multi-storey shuttle automatic storage system in the prior art The problem of low accuracy of the method and how to evaluate the performance of the multi-storey shuttle automatic storage system have become technical problems that need to be solved urgently at this stage.

Contents of the invention

The object of the present invention is to solve the above-mentioned problems, and provides a modeling optimization method based on the automatic storage system of the multi-storey shuttle car, which accurately describes the actual output of the automatic storage system based on the multi-layer shuttle Quickly calculate the performance of the automatic storage system based on multi-storey shuttle vehicles under various shelf and equipment configurations, and provide decision support for the precise design of automatic storage systems based on multi-storey shuttle vehicles, improve equipment utilization, and save operating costs .

To achieve the above object, the specific scheme of the present invention is as follows:

The invention discloses a modeling optimization method based on an automatic storage system of a multi-layer shuttle car, which includes the following steps:

(1) Determine the movement rules of the hoist and shuttle car and the service time of the hoist and shuttle car during the operation process; respectively extract the number of layers of the automatic storage system of the multi-layer shuttle car, the depth of the roadway, the height of the single-layer shelf, and the individual The width of the cargo grid, the speed and acceleration of the hoist, the speed and acceleration of the shuttle car, the time of single pick-up and release, and the detailed information parameters of the outbound task establish a mathematical model for the automatic storage system of the multi-layer shuttle car;

(2) Build a mixed integer programming model with the goal of obtaining the shortest total time for picking up goods;

(3) Use the GUROBI linear programming solver to solve the mixed integer programming model to obtain the shortest total picking time and the value of each state variable, so as to determine the optimal picking order of the system.

Further, the determination of the movement law of the hoist and the shuttle car is specifically:

Assuming that the current elevator is on the xth floor, according to the height of the single-layer shelf, determine the walking distance of the elevator from the I/O platform to this floor;

Consider the acceleration and maximum speed of the hoist to determine the travel time of the hoist;

Assuming that the current shuttle car is in the first row of the roadway, according to the width of a single cargo box, determine its travel distance to reach the qth depth position;

Consider the acceleration and maximum speed of the shuttle car to determine the travel time of the shuttle car.

Further, the determination of the various service hours of the hoist and shuttle operation process is specifically:

The service time for the elevator to transport the goods from the i-th floor to the I/O platform and release them;

The elevator transports the goods from the i-th floor to the I/O platform for release, and then returns to the service time of the j-th floor to pick up the goods;

The shuttle car takes out the service time of the outbound task located at the qth depth position on the i-th floor;

The hoist service time from the initial state, that is, the I/O platform to the i-th floor.

Further, the constructed mixed integer programming model with the goal of obtaining the shortest total pick-up time is specifically:

Among them, t _M is the start moment when the hoist performs the last outbound task, N is the numbered set of all shelf layers, M is the total number of outbound tasks in the system, Indicates the service time for the elevator to transport the goods from the i-th floor to the I/O platform and release, y _Mi indicates whether the last elevator task is the outbound task of the i-th floor (if the last elevator task is the i-th floor For outbound tasks, the value of this variable is 1; otherwise, the value of this variable is 0)

Further, in order to ensure the uniqueness of the outbound layer, pick-up order, and location position corresponding to each outbound task, the constraints of the mixed integer programming model are established, specifically:

1) The total number of outbound tasks on the i-th shelf is equal to the total number of elevator tasks on the i-th shelf; and the uniqueness of the outbound layer where any elevator task is located is guaranteed;

2) Among all the hoist tasks, the number of the nth outbound tasks on a certain floor is equal to the number of outbound tasks of all shelves greater than n; and it is guaranteed that any one hoist task will be outbound in its corresponding outbound layer. Uniqueness of library order;

3) Guarantee the uniqueness of the order of any outbound task in its corresponding outbound layer;

And guarantee the uniqueness of any outbound task in its corresponding outbound layer cargo location depth.

Further, according to the connection between the tasks of each elevator, the constraints between each elevator task are determined, specifically:

The start time of the first elevator task is greater than the time when the elevator reaches any shelf;

Moreover, the time difference between any two consecutive elevator tasks is greater than the time required for the elevator to go back and forth between two shelves.

Further, according to the connection between the tasks to be delivered in each shelf, the constraints between the tasks to be delivered in each shelf are determined, specifically:

The time for the first outbound task on any floor to wait for the dispatch of the hoist is later than the time required for the shuttle car to reach its location to complete the pick-up operation;

Moreover, the time difference between the completion times of two consecutive outbound tasks on any floor is greater than the time required for the shuttle to travel.

Furthermore, t _m is the start time when the hoist performs the m-th outbound task, and the time when the shuttle completes the n-th outbound task on the i-th floor and waits for the response of the hoist is recorded as r _in . According to t _m and The internal connection of r _in is established as follows:

The start time of the first elevator task is later than the time when the first goods to be out of the warehouse are taken out;

And, assuming that the m-th hoist task is the n-th outbound task of the i-th layer, the start time of the m-th hoist task is later than the completion time of the n-th task of the i-th layer;

And, assuming that the m-th hoist task is the n-1th outbound task of the i-th floor, the completion time of the n-th task on the i-th floor is later than the start time of the m-th hoist task and the travel time of the shuttle car Sum;

And, assuming that the mth hoist task is the nth outbound task of the i-th floor, the m-1th hoist task is the outbound task of the jth floor, and the nth task of the i-th floor is completed later The sum of the start time of the m-1th hoist task and the hoist travel time.

Furthermore, in order to ensure the non-negativity of the mixed integer programming model, the constraints are established as follows:

The start time for the hoist to execute the mth outbound task is not less than zero;

Moreover, the shuttle car completes the nth outbound task on the i-th floor, and the waiting time for the hoist to respond is not less than zero.

Further, the optimal picking order of the obtaining system is specifically:

The value of each state variable calculated by the solver identifies the order of picking in the system, and the specific method of determining the order of picking:

If and only if y _mi =1, z _mn =1, x _inq =1, it means that the mth item taken out is located at the qth depth position of the i-th layer, and it is the nth item taken out on the shelf of this layer , that is, the m-th outbound operation is the n-th outbound operation in the i-th layer, and the outbound operation is at the qth depth position;

According to the above rules, the unique corresponding outbound layer, pick-up order, and location information of each outbound task are sequentially judged, and the optimal pick-up order of the system is further obtained;

Among them, y _mi identifies whether the m-th elevator task is the outbound task of the i-th layer, z _mn indicates whether the m-th hoist task is the n-th outbound task of a certain layer, and x _inq identifies the i-th layer’s outbound task. Whether the nth outbound job is at the qth depth position.

Beneficial effects of the present invention:

The integer programming model established by the present invention can accurately simulate the actual outbound task process of the system, and can quickly estimate the performance of the system under various shelves and equipment configurations, which provides the precise design of the system, the improvement of equipment utilization, and the saving of operating costs. policy support.

The result obtained by the modeling method provided by the present invention can accurately locate the order of each outbound task, and compared with the total picking time required by random picking order, the total time for picking up the goods is greatly reduced.

The present invention abstracts the internal connection between outbound tasks into precise mathematical components, establishes an integer programming model of outbound tasks in the multi-layer shuttle car system and its solution algorithm, and overcomes the inability of traditional warehouse modeling to adapt to multi-layer shuttles According to the characteristics of multiple servers in the car automatic storage system, the system performance can be calculated quickly and accurately by using tools.

Utilizing the model and solving algorithm of the present invention, the optimal configuration combination of the shuttle car and the hoist can be quickly and effectively found out, which not only saves system operating costs, but also provides theoretical guidance for logistics storage system designers.

Description of drawings

Figure 1 is a schematic diagram of the multi-storey shuttle car automatic storage system;

Figure 2 is a flow chart of the outbound task.

Detailed ways:

The present invention is described in detail below in conjunction with accompanying drawing:

In a single outbound task, the task first requests the response of the shuttle car on the corresponding floor. According to the system scheduling, the shuttle car first moves horizontally to the delivery location assigned by the system, uses the fork to take out the goods, and then the shuttle car runs to the first column of the floor, requesting the response of the roadway hoist. Similarly, the hoist goes to the corresponding floor to complete the handover of goods with the shuttle car according to the system scheduling. The outbound task flow is shown in Figure 2.

Based on this, the present invention discloses a modeling optimization method based on an automatic storage system of a multi-storey shuttle, comprising the following steps:

(1) Model the multi-storey shuttle car automatic storage system, extract the number of layers, the number of rows, the speed and acceleration of the hoist, the speed and acceleration of the shuttle car, and the time for taking out goods, and abstract them into a mathematical model the various inputs.

(1-1) The basic input required by the analysis model; specifically includes:

The number of floors N of the multi-storey shuttle car automatic storage system, the depth C of the roadway, the height D _h of a single shelf, the width D _w of a single shelf, the maximum speed V _w of the shuttle car, the acceleration a _w of the shuttle car, and the maximum speed of the hoist V _h , hoist acceleration a _h , shuttle car pick-up and release time t _w , hoist pick-up and release time t _h , solution scale constant T, including detailed information of all outbound tasks (task layer, depth location) dictionary Q.

(1-2) Analyze the movement rules of the hoist and shuttle car, specifically:

Assuming that the hoist is currently on floor x, the travel distance of the hoist from the I/O platform to this floor is

H=(x-1)×D _h

Considering the acceleration and maximum speed of the hoist, the travel time of the hoist is:

Similarly, assuming that the current shuttle is in the first column of the roadway, its travel distance to reach the qth depth position is

W=q× _Dw

Considering the acceleration and maximum speed of the shuttle, the travel time of the shuttle is:

(1-3) Calculate the service time of hoists and shuttles, specifically:

Calculate the service time for the elevator to transport the goods from the i-th floor to the I/O platform and release

Calculate the service time for the hoist to transport the goods from floor i to the I/O platform for release, and then return to floor j to pick up the goods

Calculate the service time for the shuttle car to take out the outbound task at the qth depth position on the i-th floor

Calculate the service time of the hoist from the initial state, that is, the I/O platform to the i-th floor

(2) Model the dynamic picking process of the multi-storey shuttle automatic storage system, aiming to obtain the shortest total picking time, and establish a mixed integer programming model.

(2-1) The objective function of the model:

Among them, t _m is the start moment when the hoist executes the m-th outbound task, and N is the numbered set of all shelf layers. When the objective function obtains the minimum value, the total pick-up time of the multi-storey shuttle automatic storage system is the shortest.

(2-2) Establish constraints to ensure the uniqueness of the outbound layer, pick-up order, and location of each outbound task, specifically:

∑ _i∈N y _mi =1 i∈N,m∈{1,2,...,M};

Among them, S _i identifies the number of outbound tasks on the i-th shelf, and the variable y _mi identifies whether the m-th elevator task is an outbound task on the i-th floor. The value rule of y _mi is:

Among them, S _max represents the maximum value of the outbound task of a single shelf, Z _n identifies the number of outbound tasks for all shelves greater than n, and the variable z _mn indicates whether the mth hoist task is the nth task of a certain layer outbound tasks, the value rule of z _mn is:

Among them, Q _i represents the set of depth numbers of the outbound tasks on the i-th shelf, and the variable x _inq indicates whether the nth outbound task on the i-th layer is at the qth depth position. The value rule of x _inq is:

(2-3) Analyze the connection between each elevator task, and establish constraints as follows:

The start time of the first elevator task is greater than the time when the elevator reaches any shelf, that is

Assuming that the m-1th hoist task is located on the i-th shelf, and the m-th hoist task is located on the j-th shelf, the time difference between any two consecutive hoist tasks must be greater than the time required for the hoist to go back and forth between the two shelves. time, namely

(2-4) Analyze the connection between the tasks to be delivered in each shelf, and establish the constraints as follows:

The time for the first outbound task on any floor to wait for the dispatch of the hoist must be later than the time required for the shuttle car to reach its location to complete the pick-up operation, that is,

The time difference between the completion times of two consecutive outbound tasks on any floor must be greater than that of the shuttle car required time, that is

(2-5) Record the moment when the shuttle car completes the outbound task at the nth depth of the i-th floor and waits for the response of the hoist as r _in , analyze the internal relationship between t _m and r _in , and establish constraints as follows:

The start time of the first elevator task is later than the time when the first goods to be out of the warehouse are taken out, that is

t ₁ ≥r _i1 -T(3-y _1,i -z _m1 -x _i1q ); m∈{1,2,…,M},q∈{1,2,…,C};

Assuming that the m-th hoist task is the n-th outbound task of the i-th floor, the start time of the m-th hoist task is later than the completion time of the n-th task of the i-th floor, that is

t _m ≥ r _in -T(2-y _mi -z _mn ), i∈N,n∈{1,2,…,S _max },m∈{1,2,…,M};

Assuming that the m-th elevator task is the n-1th outbound task of the i-th floor, then the completion time of the n-th task on the i-th floor is later than the time between the start time of the m-th elevator task and the travel time of the shuttle car. and, namely

i∈N,n∈{2,...,S _max },m∈{2,...,M};

Assuming that the mth hoist task is the nth outbound task of the i-th floor, and the m-1th hoist task is the outbound task of the j-th floor, then the nth task of the i-th floor is completed later than The sum of the start time of the m-1th elevator task and the travel time of the elevator, that is

i,j∈N,n∈{1,...,S _max },m∈{2,...,M}.

(2-6) To ensure the non-negativity of the model, add other necessary simple constraints, t _m ≥ 0, r _in ≥ 0.

(3) Using Python language programming, use the GUROBI linear programming solver to generate the configuration file for the designed model, solve the shortest total pickup time and the optimal pickup order of the system, and obtain various configurations through further statistics The calculation results under these conditions are easy to analyze and obtain the optimal configuration of the multi-storey shuttle automatic storage system.

The optimal pick-up sequence for obtaining the system is as follows:

The value of each state variable calculated by the solver identifies the order of picking in the system, and the specific method of determining the order of picking:

If and only if y _mi =1, z _mn =1, x _inq =1, it means that the mth item taken out is located at the qth depth position of the i-th layer, and it is the nth item taken out on the shelf of this layer , that is, the m-th outbound operation is the n-th outbound operation in the i-th layer, and the outbound operation is at the qth depth position;

According to the above rules, the unique corresponding outbound layer, pick-up order, and location information of each outbound task are sequentially judged, and the optimal pick-up order of the system is further obtained;

Among them, y _mi identifies whether the m-th elevator task is the outbound task of the i-th layer, z _mn indicates whether the m-th hoist task is the n-th outbound task of a certain layer, and x _inq identifies the i-th layer’s outbound task. Whether the nth outbound job is at the qth depth position.

In order to verify the validity of the model, the simulation scenarios of six multi-storey shuttle systems are set up as shown in Table 1, and the results are quickly calculated using the above-mentioned accurate method of the model. In each group of scenarios, the total pick-up time under four random pick-up orders were recorded, and compared with the calculation results of the model, the obtained data records are shown in Table 2.

Table 1 Scene setting table

Table 2 Analysis of model calculation results

Obviously, the total pick-up time calculated by the model is significantly shorter than that under the random pick-up order, and the pick-up order calculated by the model is the best pick-up order.

Table 3 is the most commonly used basic configuration of the multi-storey shuttle automatic storage system, and the above results are calculated under this configuration condition.

Table 3 Basic configuration of multi-storey shuttle car automatic storage system

Although the specific implementation of the present invention has been described above in conjunction with the accompanying drawings, it does not limit the protection scope of the present invention. Those skilled in the art should understand that on the basis of the technical solution of the present invention, those skilled in the art do not need to pay creative work Various modifications or variations that can be made are still within the protection scope of the present invention.

Claims (9)

1. the modeling optimization method based on Multilayer shuttle car automated storage and retrieval system, which is characterized in that include the following steps：

(1) characteristics of motion of elevator and shuttle and the respective services time of elevator and shuttle operation process are determined； The number of plies of Multilayer shuttle car automated storage and retrieval system, the width of the depth in tunnel, the height of single layer shelf, single goods lattice are extracted respectively The velocity and acceleration of degree, the velocity and acceleration of elevator, shuttle, single picks and places ETCD estimated time of commencing discharging and outbound task is believed in detail Parameter is ceased, the mathematical model of Multilayer shuttle car automated storage and retrieval system is established；

(2) building is to obtain shortest picking total time as the mixed-integer programming model of target；

The mixed-integer programming model is specially：

Wherein, t_MIt is at the beginning of elevator executes the last one outbound task, N is the number set of all shelf numbers of plies, M It is total for the outbound task of system,Indicate the service time that elevator transports cargo to I/O platform and release from i-th layer, y_MiIdentify the last one elevator task whether the outbound task for being i-th layer, if the last one elevator task be i-th layer go out Library task, y_MiValue be 1；Otherwise, y_MiValue be 0；

(3) mixed-integer programming model is solved using GUROBI linear programming for solution device, when obtaining shortest total picking Between and system optimal picking sequence.

2. as described in claim 1 based on the modeling optimization method of Multilayer shuttle car automated storage and retrieval system, which is characterized in that institute The characteristics of motion of determining elevator and shuttle is stated, specially：

Assuming that current elevator determines walking of the elevator from I/O platform to this layer according to the height of single layer shelf in xth layer Distance；

The acceleration and maximum speed for considering elevator, determine the travel time of elevator；

Assuming that current shuttle is in tunnel, first according to the width of single goods lattice determines that it reaches the walking of q-th of depth location Distance；

The acceleration and maximum speed for considering shuttle, determine the travel time of shuttle.

3. as described in claim 1 based on the modeling optimization method of Multilayer shuttle car automated storage and retrieval system, which is characterized in that institute The respective services time of determining elevator and shuttle operation process is stated, specially：

Cargo is transported the service time to I/O platform and release by elevator from i-th layer；

Elevator discharges cargo from i-th layer of transport to I/O platform, is subsequently returning to the service time of jth layer picking；

Shuttle takes out the service time for being located at the outbound task of i-th layer of q-th of depth location；

Elevator is from initial conditions, i.e., to i-th layer of service time at I/O platform.

4. as described in claim 1 based on the modeling optimization method of Multilayer shuttle car automated storage and retrieval system, which is characterized in that be Guarantee the corresponding outbound layer of each outbound task, picking order, goods yard position uniqueness, establish mixed-integer programming model Constraint condition, specially：

1) the outbound task sum on i-th layer of shelf is equal to the elevator total task number of i-th layer of shelf；And guarantee any one The uniqueness of outbound layer where elevator task；

2) be in all elevator tasks certain layer of n-th of outbound task number be equal to all shelf outbound task number be greater than N numbers；And guarantee any one elevator task in the uniqueness of its corresponding outbound layer outbound order；

3) guarantee any one outbound task in the uniqueness of its corresponding outbound layer outbound order；

And guarantee any one outbound task in the uniqueness of its corresponding outbound layer goods yard depth.

5. as described in claim 1 based on the modeling optimization method of Multilayer shuttle car automated storage and retrieval system, which is characterized in that root The constraint between each elevator task is determined according to the connection between each elevator task, specially：

First elevator task reaches the time of any one layer of shelf greater than elevator at the time of beginning；

Also, the time difference that the continuous elevator task of any two is separated by, which is greater than between elevator round-trip two layers of shelf, to be needed Time.

6. as described in claim 1 based on the modeling optimization method of Multilayer shuttle car automated storage and retrieval system, which is characterized in that root It is determined in every layer of shelf to the constraint between outbound task, specially according in every layer of shelf to the connection between outbound task：

First outbound task of any layer is later than goods yard where shuttle reaches it and completes to take at the time of waiting elevator scheduling The time required to goods operation；

Also, the time difference that the continuous outbound task of two of any layer completes the moment is greater than the time that shuttle walking needs.

7. as described in claim 1 based on the modeling optimization method of Multilayer shuttle car automated storage and retrieval system, which is characterized in that will Elevator is t at the beginning of executing m-th of outbound task_m, shuttle is completed into i-th layer of n-th of outbound task, waiting mentions R is denoted as at the time of the response of the machine of liter_in, according to t_mAnd r_inInner link, establish that constrain part as follows：

At the time of first elevator task is later than first cargo to outbound and is removed at the time of beginning；

And, it is assumed that m-th of elevator task is i-th layer of n-th of outbound task, at the time of m-th of elevator task starts At the time of being later than i-th layer of n-th of task completion；

And, it is assumed that m-th of elevator task is i-th layer of (n-1)th outbound task, i-th layer of n-th of task complete when Quarter is later than the sum of time and the shuttle travel time that m-th of elevator task starts；

And, it is assumed that m-th of elevator task is i-th layer of n-th of outbound task, and the m-1 elevator task is jth layer Outbound task, i-th layer of n-th of task are later than the time and elevator row that the m-1 elevator task starts at the time of completion Walk the sum of time.

8. as described in claim 1 based on the modeling optimization method of Multilayer shuttle car automated storage and retrieval system, which is characterized in that be Guarantee the nonnegativity of mixed-integer programming model, establishing a constraint part is specially：

Elevator is not less than zero at the beginning of executing m-th of outbound task；

Also, shuttle completes the outbound task on i-th layer of q-th of depth location, is not less than at the time of waiting elevator response Zero.

9. as described in claim 1 based on the modeling optimization method of Multilayer shuttle car automated storage and retrieval system, which is characterized in that institute The acquisition system optimal stated picking sequence be specially：

By the value for each state variable that solver calculates, picking sequence in mark system, specific picking sequence is sentenced Fixed method：

And if only if y_mi=1, z_mn=1, x_inqIndicate that m-th of cargo being removed is located at i-th layer of q-th of depth location when=1 On, it is n-th of cargo being removed on this layer of shelf, i.e. m-th of Delivery is i-th layer of n-th of Delivery, simultaneously should Delivery is on q-th of depth location；

According to the above rule, every outbound task uniquely corresponding outbound layer, picking order, goods yard position letter are successively judged Breath further obtains the picking sequence of system optimal；

Wherein, y_miIdentify m-th of elevator task whether the outbound task for being i-th layer, z_mnWhether identify m-th of elevator task For n-th of outbound task of a certain layer, x_inqWhether n-th of Delivery of i-th layer of mark be on q-th of depth location.