CN105858044A - Optimal dispatching method for warehousing systems combining rail guided vehicles and lifts - Google Patents

Abstract

The invention discloses an optimal dispatching method for warehousing systems combining rail guided vehicles and lifts. With the minimum dispatching travel time as the target, a dispatching warehouse-out and warehouse-in model is optimized through the genetic algorithm, the storing and delivering travel time is greatly shortened, the time cost is obviously reduced, the energy is saved, the advantages of the high efficiency, the high density and the high utilization rate of rail guided sub-vehicle full-automatic stereoscopic warehouses can be given full play to, real-time and online optimal dispatching of the automatic stereoscopic warehouses can be realized, and the practical application significance is great.

Description

The warehousing system Optimization Scheduling that a kind of shuttle is combined with elevator

Technical field

The invention belongs to intensive storage inbound/outbound process dispatching technique field, be specifically related to one and shuttle back and forth main-auxiliary vehicle and elevator (1:1 Type) hybrid optimization dispatching method.

Background technology

Along with scientific and technical and industrial fast development, separately rise based on " intensive storage " concept, modern enterprise pair Require in producing, store in a warehouse and providing and delivering improves constantly, and promotes storage mode from the simple heap initially passing through manpower manual work Amass the warehouse-type storage by simple devices such as fork trucks be improved to use at present high position forklift, unmanned guide trolleys AGV, The tiered warehouse facility storage of the automation equipments such as shuttle.Rail mounted shuttle (RGV), low cost fast with its speed especially In the industry such as modern manufacturing industry, logistics, the most important role is play with good stability.

The inbound/outbound process using piler to realize goods scheduling in conventional stereo warehouse, the advantage of piler is to achieve warehouse more The mechanization of operation and automatization, be greatly improved work efficiency, meanwhile, utilizes computer to be controlled and manages, operation Process and information processing rapidly, accurately, in time, can be accelerated goods and materials turnover, reduce carrying cost.But, piler needs Taking corresponding tunnel and carry out operation, tiered warehouse facility effectively stores area and cannot make full use of, and, erecting of separate unit piler Directly cannot carry out with horizontal operation, goods inbound/outbound process is inefficient simultaneously.

There is minority tiered warehouse facility to use shuttle to be combined with piler at present both at home and abroad and carry out operation, take full advantage of warehouse Effective area and storage area, make cargo storage centralization, three-dimensional, reduces floor space, reduces Land Purchase expense. But, Chinese scholars is mostly based on static scheduling to the research of shuttle, seldom relates to dynamic mixed scheduling, meanwhile, Enterprise customizes service and deepens continuously, and small lot, the order of timeliness feature multiple batches of, high are on the increase, conventional palletizer Formula tiered warehouse facility can not meet the nowadays market demand with the most perfect vehicle type shelf that shuttle back and forth.

Summary of the invention

It is an object of the invention to provide the warehousing system Optimization Scheduling that a kind of shuttle is combined with elevator.

For reaching above-mentioned purpose, present invention employs techniques below scheme:

1) the dispatch situation foundation of a set of main-auxiliary vehicle that shuttles back and forth is joined for calculating tune according to an elevator in fully automatic stereo warehouse The mathematical model of degree journey time；

2) it being minimised as target dispatching journey time, utilizes step 1) mathematical model set up is to each in scheduler task The dispatching sequence of individual goods to be dispatched is optimized, and determines that this scheduler task is utilizing an elevator to join a set of primary and secondary that shuttles back and forth Car completes the optimal scheduling order under dispatch situation.

Described scheduler task includes accessing goods multiple working.

In the case of access goods multiple working, the mathematical model calculating scheduling journey time is expressed as:

T_d=∑ [m_ij×T_t+(1-m_ij)×T_b]

Wherein, T_dFor access goods multiple working scheduling journey time, T_tAn access is completed when same layer for access goods yard To scheduling journey time, T_bFor access goods yard do not complete when same layer one access to scheduling journey time, access The double goods scheduling taken afterwards is first deposited to representing；m_ij=0 or 1, value be 0 expression access to access goods not with One layer, value be 1 expression access to access goods at same layer, i is stock, and j is picking.

Described T_tAnd T_bIt is expressed as:

$T_t=\frac{2z_i}{v_s}+\frac{x_i+x_j}{{v_m}^{\′}}+\frac{y_i+y_j}{{v_z}^{\′}}+\frac{y_i+y_j}{v_z}+\frac{|x_i-x_j|}{v_m}+4t_z+2t_m+2{t_m}^{\′}+2{t_s}^{\′}$

$T_b=\frac{z_i+|z_i-z_j|+z_j}{v_s}+\frac{x_i+x_j}{{v_m}^{\′}}+\frac{y_i+y_j}{{v_z}^{\′}}+\frac{y_i+y_j}{v_z}+\frac{x_i+x_j}{v_m}+4t_z+2t_m+2{t_m}^{\′}+2t_s+2{t_s}^{\′}$

Wherein, x, y and z are goods correspondence goods yard coordinate under OXYZ coordinate system, in described OXYZ coordinate system, The I/O position in initial point O correspondence fully automatic stereo warehouse, X-axis correspondence mother's car moving direction, the corresponding sub-car side of movement of Y-axis To, Z axis correspondence elevator moving direction；t_zFor sub-car picking or unloading time；t_mFor car female under no-load condition take sub-car or Unload the time of sub-car；t_m' take sub-car for car female under full load conditions or unload the time of sub-car；t_sTake for elevator under no-load condition Female car or unload time of female car；t_s' take female car for elevator under full load conditions or unload the time of female car；v_sFor elevator speed； v_mFor female car no-load speed, v_m' it is female car full-load speed；v_zFor sub-car no-load speed, v_z' for sub-car full-load speed.

During described optimization, if the stock task amount included in scheduler task is more than picking task amount, then use respective counts That measures treats that the picking task that picking article coordinate is (0,0,0) makes access goods task amount equal.

The method of described optimization is genetic algorithm.

Crossover probability P in described genetic algorithm_cIt is 0.7～0.9, mutation probability P_mIt is 0.1～0.2.

Beneficial effects of the present invention is embodied in:

One elevator is joined the dispatch situation founding mathematical models of a set of main-auxiliary vehicle that shuttles back and forth by the present invention, then sets up and goes out accordingly Entering library model, after using genetic algorithm to optimize the library model that comes in and goes out, access journey time is greatly shortened, and can substantially save Time cost, saves the energy, makes the shuttle back and forth high efficiency in main-auxiliary vehicle fully automatic stereo warehouse, high density, and high usage Being not fully exerted etc. advantage, it is achieved the Optimized Operation that automatic stereowarehouse is real-time, online, having bigger reality should Use meaning.

Accompanying drawing explanation

Fig. 1 is the main-auxiliary vehicle fully automatic stereo warehouse schematic diagram that shuttles back and forth；

Fig. 2 is the main-auxiliary vehicle fully automatic stereo storehouse model figure that shuttles back and forth；

In figure: 1 is female track road, and 2 is sub-track road, and 3 is rail of lifter.

Detailed description of the invention

The present invention is described in detail with embodiment below in conjunction with the accompanying drawings.

The present invention provides one to shuttle back and forth main-auxiliary vehicle and elevator hybrid optimization dispatching method, specifically implements according to following steps:

One elevator is joined the dispatch situation of a set of main-auxiliary vehicle that shuttles back and forth (1:1 type) and is set up rational mathematical model by step 1；

1.1 pairs of main-auxiliary vehicle fully automatic stereo warehouses that shuttle back and forth are analyzed research, formulate goods access rule

Seeing Fig. 1, the main-auxiliary vehicle fully automatic stereo warehouse that shuttles back and forth comprises: the main-auxiliary vehicle that shuttles back and forth (being made up of sub-car and female car), mother Track (tunnel) is walked by garage, track is walked by sub-garage (shelf row), shuttle rack, pallet vertical promote system (lifting Machine), tray conveying system, CMS apparatus control system, WMS warehouse management system.By complete certainly for the actual main-auxiliary vehicle that shuttles back and forth Dynamic tiered warehouse facility is converted into the model under OXYZ coordinate system, as in figure 2 it is shown, include rail of lifter 3, female track road 1 and sub-track road 2.Wherein, elevator will be equipped with the main-auxiliary vehicle of goods and carries out the transport of Z-direction, female car by sub-car with Goods carries out X-direction transport, and goods is carried out Y direction transport by sub-car.Single goods yard coordinate is [x, y, z], this Coordinate refers to the centrical coordinate of goods, is above-mentioned coordinate origin O with I/O point (going out inbound station).

The present invention also sets following goods access rule:

(1) use a set of main-auxiliary vehicle that shuttles back and forth, once transport and be only capable of carrying a goods.Individually stock (or picking) feelings Under condition, the main-auxiliary vehicle stock (picking) that shuttles back and forth returns to out inbound station (I/O point) after terminating；In the case of access goods multiple working, After the main-auxiliary vehicle stock that shuttles back and forth terminates, carry out ensuing picking task, after final task terminates, elevator from this point Main-auxiliary vehicle all returns to out inbound station with shuttling back and forth.

(2) initial position of elevator and the main-auxiliary vehicle that shuttles back and forth is going out inbound station (i.e. I/O point).

Going out to put in storage after order (i.e. scheduler task) assigns, order is analyzed by warehouse management system (WMS), according to Simple stock operation, simple unstaffing, three kinds of situations of access goods multiple working, apparatus control system (CMS) regulates and controls Main-auxiliary vehicle is risen to corresponding layer by elevator, and female car, at tunnel movement, rests at the goods row at goods place, female car Discharging sub-car, sub-car returns after completing stock or unstaffing.

1.2 set up an elevator joins a set of main-auxiliary vehicle that shuttles back and forth (1:1 type) access goods mathematical model

Definition: the sub-car loading, unloading goods time is t_z；Female car loading, unloading unloaded sub-car time is t_m, female car loading, unloading are fully loaded with The sub-car time is t_m', elevator loading, unloading zero load mother is t the car time_s, elevator loading, unloading fully loaded female car time is t_s', dress The same with the time of unloading；Elevator speed is v_s；Female car no-load speed is v_m, female car full-load speed is v_m'；Sub-car zero load speed Degree is v_z, sub-car full-load speed is v_z'。

(1) simple stock job model

Because the initial position of elevator and main-auxiliary vehicle is at O point, and main-auxiliary vehicle is returned to O point after every time stock completes, so Total activation journey time T of simple stock_cAs follows:

T_c=∑ T_c1

$T_{c1}=(\frac{2z_i}{v_s}+\frac{x_i}{v_m}+\frac{x_i}{{v_m}^{\′}}+\frac{y_i}{v_z}+\frac{y_i}{{v_z}^{\′}}+t_s+{t_s}^{\′}+t_m+{t_m}^{\′}+2t_z)---\left(1\right)$

(2) simple unstaffing model

Because the initial position of elevator and main-auxiliary vehicle is at O point, and main-auxiliary vehicle is returned to O point after every time picking completes, so Total activation journey time T of simple picking_qAs follows:

T_q=∑ T_q1

$T_{q1}=(\frac{2z_j}{v_s}+\frac{x_j}{v_m}+\frac{x_j}{{v_m}^{\′}}+\frac{y_j}{v_z}+\frac{y_j}{{v_z}^{\′}}+t_s+{t_s}^{\′}+t_m+{t_m}^{\′}+2t_z)---\left(2\right)$

(3) access goods multiple working model

The access of goods being matched, it is right to be referred to as accessing, and i.e. one deposits one is taken as a unit.It is right for each access, In two kinds of situation:

A () picking goods yard and stock goods yard are at same layer；

B () picking goods yard and stock goods yard be not at same layer；

Meanwhile, by access to access goods whether be set to a 0-1 variable m at same layer_ij,

Then each access is to (i is stock, and j is picking), and access goods yard is at same layer (z_i=z_j) scheduling journey time T_t, access goods yard not in scheduling journey time T of same layer_bAs follows:

$T_t=\frac{2z_i}{v_s}+\frac{x_i+x_j}{{v_m}^{\′}}+\frac{y_i+y_j}{{v_z}^{\′}}+\frac{y_i+y_j}{v_z}+\frac{|x_i-x_j|}{v_m}+4t_z+2t_m+2{t_m}^{\′}+2{t_s}^{\′}---\left(3\right)$

$T_b=\frac{z_i+|z_i-z_j|+z_j}{v_s}+\frac{x_i+x_j}{{v_m}^{\′}}+\frac{y_i+y_j}{{v_z}^{\′}}+\frac{y_i+y_j}{v_z}+\frac{x_i+x_j}{v_m}+4t_z+2t_m+2{t_m}^{\′}+2t_s+2{t_s}^{\′}---\left(4\right)$

Access goods multiple working access to total activation journey time T_dAs follows:

T_d=∑ [m_ij×T_t+(1-m_ij)×T_b] (5)

To sum up, the Access Model of the tiered warehouse facility joining a set of main-auxiliary vehicle that shuttles back and forth for an elevator is as follows:

Step 2 is optimized emulation to Access Model, determines input work optimal scheduling order and the shortest scheduling time.

The present invention uses MATLAB to carry out simulation analysis based on genetic algorithm, joins a set of primary and secondary that shuttles back and forth for an elevator The dispatch situation of car, studies, respectively in terms of two: inventory amounts is equal to picking quantity, and inventory amounts More than picking quantity.Inventory amounts is not considered less than the situation of picking quantity.Access goods quantity phase is here discussed in detail Deng time 30 task amounts result of study, wherein parameter value is shown in Table 1.Specifically comprise the following steps that

Number respectively to the goods yard of all goods to be accessed, using the traversal order in goods yard as the coding of genetic algorithm.

The initial population being made up of 100 (population number n=100) random ergodic order is produced in MATLAB.Goods Position compiling before specify, it is possible to use the coordinate parameters of stochastic generation.

Use the selection in basic genetic algorithmic, intersection, mutation operation that the traversal order in goods yard is optimized, choose repeatedly Generation number c=50, crossover probability P_c=0.9, mutation probability P_m=0.2, adaptation value is eliminated and is accelerated exponent m=2.In the present invention The objective function used is as follows:

Fitness (i, 1)=(1-((len (i, 1)-minlen)/(maxlen-minlen+0.0001))) ^m

Wherein, len (i, 1) represents the scheduling journey time that any individual i is corresponding, maxlen and minlen is respectively in colony Journey time is the longest and the time used by shortest path in scheduling.

Utilizing fitness > rand selects individuality, by less for the time (fitness is bigger) individual selection and remain.

When inventory amounts is exactly equal to picking quantity:

30 goods correspondence goods yard coordinates are expressed as N (x y z) and N ' (x y z), and wherein, 15 is stock (square Battle array A), N represents stock goods yard numbering (N=1～15), and 15 is picking (matrix B), and N ' represents picking goods yard numbering (N '=1 '～15 ').For seeking the shortest time that a paths makes access goods complete, the goods yard coordinate that goods is corresponding is as follows:

A=[1 (13 10 3)；2(7 6 4)；3(15 11 2)；4(3 5 2)；5(14 9 3)；6(8 2 1)；7(12 12 2)；8(16 3 4)；9(20 9 2)；10(2 4 3)；11(3 8 2)；12(3 10 3)；13(13 9 1)；14(5 8 2)；15(14 4 3)]；

B=[1 ' (5 7 4)；2’(16 4 1)；3’(17 6 2)；4’(4 11 2)；5’(10 11 1)；6’(9 2 3)；7’(8 4 2)；8’(16 5 3)；9’(19 5 1)；10’(13 6 1)；11’(17 9 3)；12’(7 3 2)；13’(2 2 4)；14’(12 1 2)；15’(18 7 2)]；

Stochastic generation 100 about in A element put in order that (traversal order array a), stochastic generation 100 is about B The putting in order of middle element (traversal order array b), it is then determined that element (representing a traversal order) and number in array a The one_to_one corresponding mapping relations of element (representing a traversal order) in group b, by 100 mapping relations thus form 100 The traversal order of the individual access goods multiple working about 30 car loadings.Element in array a and array b is utilized respectively heredity Algorithm is optimized, and changes the value (i.e. traversal order) of element in array, and according to the traversal time of access goods multiple working Sequence calculating adaptation value (it is the adaptation value of respective element in array a, is also the adaptation value of respective element in array b, so-called Corresponding two elements i.e. constituting mapping relations).

According to the random gained of program one group access goods multiple working order it is: (8 → 3 ') → (12 → 14 ') → (3 → 12 ') → (13 →10’)→(9→15’)→(1→11’)→(2→1’)→(5→5’)→(10→6’)→(7→4’)→(11→7’)→(6→13’)→ (14→8’)→(15→9’)→(4→2’).Journey time is: RTime=1015.2 (s).

After optimizing, gained one group access goods multiple working order is: (13 → 9 ') → (14 → 4 ') → (6 → 10 ') → (7 → 14 ') →(9→2’)→(8→1’)→(5→8’)→(12→13’)→(11→7’)→(15→11’)→(4→12’)→(2→15’)→(10 →6’)→(3→3’)→(1→5’).Journey time is: RTime=977.75 (s).Optimize efficiency: η=(optimization front travel Time m-optimization after journey time)/optimize front travel time=(1015.2-977.75)/1015.2=3.7%.

The result finally given ibid, is concluded into table 2 by other situation methods.Wherein, when inventory amounts ＞ picking quantity, (0 0 0) that can introduce respective numbers put as picking goods yard coordinate so that inventory amounts=picking quantity.Simultaneously as A set of shuttle back and forth main-auxiliary vehicle time, for simple stock or the order of simple picking, its journey time and stock or picking It is the most unrelated, so table 2 does not carry out record.

Learnt the discrepancy library model set up by the present invention by table 2, after algorithm optimization, taking of goods yard is deposited operation sequencing and is obtained To optimizing, the journey time of shuttle and elevator and substantially shortening, time cost can be greatly saved, improve efficiency, Further demonstrate the feasibility of this model, for automatic stereowarehouse the most on the market, economic benefits.

Table 1. model program parameters

Table 2. simulation analysis result

Claims (7)

1. the warehousing system Optimization Scheduling that a shuttle is combined with elevator, it is characterised in that: comprise the following steps:

1) the dispatch situation foundation of a set of main-auxiliary vehicle that shuttles back and forth is joined for calculating tune according to an elevator in fully automatic stereo warehouse The mathematical model of degree journey time；

2) it being minimised as target dispatching journey time, utilizes step 1) mathematical model set up is to each in scheduler task The dispatching sequence of individual goods to be dispatched is optimized, and determines that this scheduler task is utilizing an elevator to join a set of primary and secondary that shuttles back and forth Car completes the optimal scheduling order under dispatch situation.

The warehousing system Optimization Scheduling that a kind of shuttle is combined with elevator, its feature It is: described scheduler task includes accessing goods multiple working.

The warehousing system Optimization Scheduling that a kind of shuttle is combined with elevator, its feature Being: in the case of access goods multiple working, the mathematical model calculating scheduling journey time is expressed as:

T_d=∑ [m_ij×T_t+(1-m_ij)×T_b]

Wherein, T_dFor access goods multiple working scheduling journey time, T_tAn access is completed when same layer for access goods yard To scheduling journey time, T_bFor access goods yard do not complete when same layer one access to scheduling journey time, access The double goods scheduling taken afterwards is first deposited to representing；m_ij=0 or 1, value be 0 expression access to access goods not with One layer, value be 1 expression access to access goods at same layer, i is stock, and j is picking.

The warehousing system Optimization Scheduling that a kind of shuttle is combined with elevator, its feature It is: described T_tAnd T_bIt is expressed as:

$T_t=\frac{2z_i}{v_s}+\frac{x_i+x_j}{{v_m}^{\′}}+\frac{y_i+y_j}{{v_z}^{\′}}+\frac{y_i+y_j}{v_z}+\frac{|x_i-x_j|}{v_m}+4t_z+2t_m+2{t_m}^{\′}+2{t_s}^{\′}$

$T_b=\frac{z_i+|z_i-z_j|+z_j}{v_s}+\frac{x_i+x_j}{{v_m}^{\′}}+\frac{y_i+y_j}{{v_z}^{\′}}+\frac{y_i+y_j}{v_z}+\frac{x_i+x_j}{v_m}+4t_z+2t_m+2{t_m}^{\′}+2t_s+2{t_s}^{\′}$

Wherein, x, y and z are goods correspondence goods yard coordinate under OXYZ coordinate system, in described OXYZ coordinate system, The I/O position in initial point O correspondence fully automatic stereo warehouse, X-axis correspondence mother's car moving direction, the corresponding sub-car side of movement of Y-axis To, Z axis correspondence elevator moving direction；t_zFor sub-car picking or unloading time；t_mFor car female under no-load condition take sub-car or Unload the time of sub-car；t_m' take sub-car for car female under full load conditions or unload the time of sub-car；t_sTake for elevator under no-load condition Female car or unload time of female car；t_s' take female car for elevator under full load conditions or unload the time of female car；v_sFor elevator speed； v_mFor female car no-load speed, v_m' it is female car full-load speed；v_zFor sub-car no-load speed, v_z' for sub-car full-load speed.

The warehousing system Optimization Scheduling that a kind of shuttle is combined with elevator, its feature It is: during described optimization, if the stock task amount included in scheduler task is more than picking task amount, then with corresponding Quantity treat that the picking task that picking article coordinate is (0,0,0) makes access goods task amount equal.

The warehousing system Optimization Scheduling that a kind of shuttle is combined with elevator, its feature It is: the method for described optimization is genetic algorithm.

The warehousing system Optimization Scheduling that a kind of shuttle is combined with elevator, its feature It is: crossover probability P in described genetic algorithm_cIt is 0.7～0.9, mutation probability P_mIt is 0.1～0.2.