自动化立体仓库课程设计

兰州交通大学交通运输学院课程设计任务书1

所在系：物流管理系课程名称：仓储管理指导教师（签名）:国

专业班级：物流管理071班学生姓名学号：

一、课程设计题目

自动化立体仓库系统设计

二、课程设计的目的

通过本课程设计可以使学生深入了解什么是自动化立体仓库货位规划和堆垛机径

路优化问题，并掌握解决问题的根本方法，为今后走上工作岗位从事相关工作打下一

定根底，使理论和实践有效结合。

三、课程设计的主要内容和要求（包括原始数据、技术参数、设计要求、工作量要求

等）

一、货位规划

1、设计条件

某自动化立体仓库采用2行3列的单元货格式货架存放货物，一共有6个货格，

每个货格存放一个托盘货物。货格以按列编码的形式进行编号，如图1所示。其它参

数假定如下：假设堆垛机在水平方向的行驶速度Vx=3.Om/s,在垂直方向的行驶速度

Vy=2m/s；货格大小为L（长）XW（宽）XH（高）=lmXImXO.8口；堆垛机初始状态在

原点0处；货格j的横坐标盯和纵坐标方就是其所在的列和行，如货格6的坐标为（3,

x.xL（y.-l）xH

tj=max<--------------

2〕；叉车运行至货格j所用时间〔也。o现有6个托盘货物需要存

放到货架上，货物的出入库频率如表1所示。

246

135

图1原始货格图

表1托盘货物出入库频率表

货物频率货物频率货物频率

A6D15E4

B30D9F20

2、设计任务

根据以上条件，利用匈牙利算法合理安排各托盘货物的存放位置。

3、设计要求

（1）根据条件，计算出系数矩阵（先列式详细计算％F的值）；

(2)详细地写出匈牙利算法的每一步骤及计算结果；

(3)绘出最终的货位规划图。

(4)设计结束后，谈谈自己的看法。

二、堆垛机径路规划

1、设计条件

Vy

5(0)10(U)15(W)20(X)25(Y)

4(G)9(K)14(T)19(N)24(K)

3(D)8(J)13(H)18(E)23(S)

2(B)7(F)12(1)17(V)22(R)

1(A)6(D)11(M)16(P)21(L)

o图2最终的货位规划图vx

随机从图2中的25个货格中抽出7个货格的货物，分别用节点vl,v2,v3,V4,vo,

v6,v7表示。节点间的距离用直角距离公式为*一出“卜「其卜”求解。

2、设计任务

分别用最近邻点法和最近插入法找出堆垛机存取7个托盘货物的合理路线。

3、设计要求

(1)绘出货格和节点相对位置图及节点相对距离表(需要先列式计算各为的值)；

(2)详细地写出最近邻点法和最近插入法的每一步骤及计算结果.

(3)分析两种方法的结果。

(4)设计结束后，谈谈自己的看法。

四、工作进度安排

18周完成货位规划任务；

19周完成堆垛机径路规划任务。

五、主要参考文献

【1】焦永兰.《管理运筹学》.北京：中国铁道出版社，2000年3月

【2】蔡临宁.《物流系统规划一一建模及实例分析》.北京：机械工业出版社，

审核批准意见

系主任(签字)年月日

货位优化

（一）求系数矩阵

：Vx=3,Vy=2,L=1,H=0.8,/t={6,30J5,9,4,20}

根据系数矩阵中的系数/=AX〃，应先求0。

G为堆垛机运行至货格j所用的时间，且/广max

XjxL(j,-l)xH1x1(l-l)x0.8

/1=max<

(乃-I6”(2-l)x0.82

r;=max-

V.y5

x3x£(y3-1)x//(1一l)x0.82

~2~3

xxL())-1)x"2x1(2-l)x0.8

i-nidA4,f-)q

4叭v,J323

fx5xL(y5-1)x//)[3x1(l-l)x0.81,

「maxJ-----，---------产彳一T，----；----(=[

〔也匕・J132

根据公式与二力Xfj求各种货物存入货格后，堆垛机存取时所需的时间计算过程如下:

对于货物A：

^A\=/A=6X§=2

2

%二/XG=6X1=2

/2/

rXt6x4

=/A3=-=

=fA=6XQ=4

CA5=/八XZ5=6X1=6

CA6=/A*"=6x1=6

对于货物B：

Cm=jBx，[—30x-=10

2

CB2~fBX，2=30X—=12

5

2

CB3=fHxG=30x-=20

J

2

C/3A=fRX=30X—=20

C/J5=fHX=30x1=30

CB6=JBX，6=30x1=30

对于货物D：

cc\=Z?x4=15x§=5

2

，C2=fcxq=15xg=6

,2

=fcX/Q=15x—=10

2

CC4=fcxr4=15x-=l()

=fcx=15x1=15

CC6=/cx^6=15x1=15

对于货物D：

°Dl=fDX，1=9x—=3

-J

2]8

CD2=fD乂，2=9x《二三七4

2

CD3=/DXJ=9X-=6

2

%4=//)x〃=9x-=6

CD5=fnx^5=9x1=9

，D6=fi)=9x1=9

对于货物E：

,.14,

CE\一于E**\=4X—=—•«1

nJ

28

CEZ=fEX，2=4X—=—X2

55

28

CE3=fEXS=4x—=—«3

JJ

,)28i

CE4=hXt4=4x-=-«3

=Ax^5=4x1=4

Q6=/EX^=4X1=4

对于货物F：

12°，

%=/FX^I=20x3=y

2

cF2=/Fxr2=20x-=8

2

AX40

-一

333«I3

2

A

X-40

3一3司3

XXH=

2020

CF6=fFX，6=20x1=20

综上得到系数矩阵表如表2：

表2系数矩阵表

ABDDEF

12105317

22126428

3420106313

4420106313

5630159420

6630159420

(二)用匈牙利算法求解：

匈牙利算法的步骤：

第一步：建立等效矩阵

(1)从系数矩阵的每行元素中减去该行的最小元素。

(2)再从所得系数矩阵的每列元素中减去该列的最小元素。

2105317-■100000

2126428010000

4201()6313__、183104

420106313183104

63015942021773010

63()159420_2177301()

第二步：找独立0元素，进行试指派。

(1)从只有一个。元素的行(或列)开始，给这个。元素加括号(0),表示行所代表

的货格已有一种货物分配。然后划去(0)所在列〔或行〕的其他0元素，记作,

表示这列所代表的货物己指派。

⑵对中有一个0元素的列1或行)的0元素加括号(0),然后划去(0)所在行(或

列)的0元素，记作O

如果在［1),(2)两步中，遇到每一行利每一列都有两个或两个以上的0元素，可以

任选一个加括号，同时把其所在的行和列的0元素都划去。

(3)重复(1),(2)两步，直到所有的0元素都被加括号或打叉。

(4)加括号的。元素即为独立的0元素，假设其个数m等于矩阵的阶数n,那么已得

到问题的最优解。假设水n,那么转入第三步。

1(0)。,。放一

(0)16,°。

1831(0)4

183104

21773,1()

_21773010

独立0元素的个数m=3〈矩阵的阶数n=6,转入第三步。

第三步：用最少的直线覆盖所有0元素。

(1)对没有独立0元素的行打“V”。

(2)对已打"J”的行中所有含0元素的列打“J二

(3)在对⑵中打的列中含有独立0元素的行打“

(4)重复⑵，⑶,直到得不到新的打的行、列为止。

(5)对没有打“J”的行和己打“的行用直线覆盖，且直线的数目一定等于独立

0元素的个数。转第四步。

(0)1I“八小&t

。甲Y，

rn'l1(hA(

(0)1,V

1831(041831(()4J

今1831/

183104)4V

217730102177310J

21773。1021773r10J

第四步：增加0元素。

从没有被直线覆盖的元素中找出最小元素。未被覆盖的元素都减去该最小元素，而被

两条直线覆盖的元素都加上该最小元素，其它元素不变.这样得到新系

数矩阵，转第二步，重新确定独立()元素。

100010

010010

072003

072003

1166209

1166209

1(0)°。1。

。1(0)。1

。72(0)。3

(0)72©。3

11662(0)9

11662。9

-10002()■

010020

072013

加减最小元素重新确定独立0元素

-----------------------------►072013---------------------------------------►

0155108

0155108

I(0),°2--W—~d~=-6

。1(0)。2#~1~W—;—电

。72(0)13a12(⑴3

m<n用直线覆盖

(0)7213723

。------------------->(0)a

。1551(0)84、155（（）8

。1551。81558

300240

10240

050011

加减最小兀素>重新确定独立o元素

050011---------------------------->

0133106

0133106

3(0)。24。--010000

21。24(0)000001

。5(0)。11001000

m二n

。5。(0)11---------------------------►000100

(0)1331。6100000

。1331(0)6000010

由解可得最优分配方案：A货物放5货格，B货物放1货格,D货物放3货格，D货物

放4货格，E货物放6货格，F货物放2货格。

2(B)7(F)12(I)17(V)22(R)

1(A)6(D)11(M)16(P)21(L)

图2最终的货位规划图

随机从图2中的25个货格中抽出7个货格的货物G、U、T、X、E、P、R分别用节点匕、

匕、匕、丫4、%、嗫、匕表示。货格和节点的相对位置如图3、图4所不。

5(0)1()(U)15(W)20(X)25(Y)

货格

4(G)9(K)14(T)19(N)24(Q)对位

3(D)8(J)13(H)18(E)23(S)

2(B)7(F)12(1)17(V)22(R)

1(A)6(D)11(M)16(P)21(L)

图4节点位置相对国

计算两节点之间的距离：d广|xj-Xj|XL+lyj-y；|XH

_-

d,iv2=|Xv2xvi|XL+1yv2yviIXH=|2-11X1+15-41XO.8=1.6

_

d，iv3=IXv3xviIXL+1yV3-yvilXH=|3-11X1+|4-41X0.8=2

d小产|xv4-xvl|XL+|yv-yvl|XH=|4-1|Xl+|5-4|XO.8=3.8

13———

d.jvs1Xv5Xvi|XL+1yv5~yviIXH=1411X1+1341X0.8=3.8

d.IvG=|xve-xvl|XL+|yrC-yvl|X11=14-11X1+|1-4|XO.8=5.4

=———

d，iv7IXv?XviIXL+1yV7yviIXH=15~11X1+1241X0.8=5.6

d，2v3=Ixv3-xv21XL+|yv3-yv21XH=|3-2|Xl+|4-51XO.8=1.8

d.2v4=IXv「Xv21XL+1yv.-yv21XH=14-21X1+|5-51X0.8=2

d,2vs=Ixv5-xv21XL+|yv5-yV21XH=|4-21X1+|3-51X0.8=3.6

d,2v6=|xv6-xv2|XL+|yv6-yv2|XH=|4-2|X1+|1-5|XO.8=5.2

d，2v7=Ixv7-xv21XL+|yv7-yv21XH=15-21X1+12-51X0.8=5.4

d.3V产Ixv4-xv3|XL+|yv.ryv3|XH=14-31X1+15-41XO.8=1.8

=_-=

d.3vs-IXv5-xv31XL+1yV5-yV31XH1431X1+1341X0.81.8

d.3v6=|xv6-xv3|XL+|yv6-yv31XH=14-31X1+|1-4|XO.8=3.4

_

d,3v7=|xv7-xv31XL+|yV7yV31XH=|5-31X1+|2-4|X0.8=3.6

deIxv5-xvJXL+|yv5-yv41XH=14-41X1+13-51X0.8=1.6

d，4v6=IXv6—XviIXL+1Yve-YviIXH=14—41X1+11—5X0.8=3.2

d,4v7=|xv7-xv4|XL+|yv7-yv4|XH=15-41X1+12-51XO.8=3.4

d.5v6=|xv6-xv5|XL+|yv6-yV51XH=|4-41X1+|1-3|XO.8=1.6

d，5v7=|xv7-xv5|XL+1yv7-yvsIXH=|5-4|X1+|2-3|XO.8=1.8

d.6V7=IX\「x比|XL+|yv7-yV61XH=|5-4|X1+|2-11XO.8=1.8

讦算结果如表3

表3节点相对距离表

元素V.v2v3v.,v5v6v7

%—1.823.83.85.45.6

—

V21.81.823.65.25.4

—

V321.81.81.83.43.6

—

V.t3.821.81.63.23.4

3.83.61.81.6—1.61.8

V5

—

v65.45.23.43.21.61.8

—

V75.65.43.63.41.81.8

一、最近邻点法

1、最近邻点法的思路

（1）从零点开始，作为整个回路的起点。

（2）找到离刚刚参加到回路的顶点最近的一个顶点，并将其参加到回路中。

（3）重复步骤（2）,直到所有顶点都参加到回路中。

（4）最后，将最后一个参加的顶点和起点连接起来。

2、应用过程

（1）先将节点vi参加到回路中，T={vi}o

（2）从节点vi出发，比拟其到2、3、4、5、6、7的距离，选择其最小值，参加到回

路中。

Min{dii|ieN,l</<7,且i工1}二出2=1.8

因此将节点V2参力口到回路中，T={V1,V2）O

（3）从节点V2出发，在节点3、4、5、6、7中，找出离V2最近的节点。

Min{t/2r.|/GM1<Z<7,且i/l,2}=d23=L8

这样就可以将V3参加到回路中，T={V1,V2,V3)O

(4)从节点V3出发，在节点4、5、6、7中，找出离V3最近的节点。

Min{〃3,|i£N,l且irl23}=dx=J45=1.8

这样V4.V5是最近的点，在此选择将V4参加到回路中，T={V|,V2,V3,V4)

(5)从节点V4出发，在节点5、6、7中，找出离V4最近的节点。

Min{</4/|zeMl<z<7,且iw1,2,3,4}=d45=1.6

这样V5是最近的点,将V5参加到回路中,T={V1,V2,V3,V4,V5)

(6)从节点V5出发，在节点6、7中，找出离V5最近的节点。

Min{tZ5i.|/GM1</<7,且iw1,2,3,4,5}=d56=1.6

这样V6是最近的点，将V6参加到同路中，T={V|,V2,V4,V4,V5,V6)

(7)从节点V6出发，V7是最后一个点，直接参加就可以了。然后，将V7和VI相连。

得到的最后解为T={V1,V2,V3,V4,V5,V6,V7,V1),见图5o

图5最近邻点法求解结果

所以堆垛机运行路线为：4—10-14—20—18—16—22

即取送货物次序为：G-UfT-X-EfP-R

堆垛机总行驶距离为：f=l.8+1.8+1.8+1.6+1.6+1.8+5.6=16

二、最近插入法

1、最近插入法的思路

(1)先将节点vl参加到回路中，找到八最小的节点vk,形成一个子回路，

T={v,,vk,v(}o

(2)在剩下的节点中，寻找一个离子回路中某一节点最近的节点Vk。

(3)在子回路中找到一条弧(i,j),使得里程增量相+%-%最小。如果有多条满足

条件，任选条，然后将节点Vk插入到节点Vi和Vj之间，用两天新的弧（i,k）和（k,j）

代替原来的弧（i,j）,并将节点Vk参加到子回路中。

（4）重复步骤（2）和（3）,直到所有的节点都参加到子回路中。

2^应用过程

（1）比拟货格相对距离表中从w出发的所有路径的大小

Mintij一且iwl}=G2=L8

这样就由节点V］和V2构成的子回路，T={vbv2,vj如图6所示。

图6由VI和V2构成的子回路

（2）然后考虑剩下的节点\，3、Vov5>'%、v?到5和V2中某一个节点的最小距离;

Min{4,c/ieMl4"Z且Ml,2}=%=1.8

（3）山于对称性，无论将3插入到1和2之间往返路径中，结果都是一样的，这样,

构成一个新的子回路T={V.,V2,V3,v.）,其结果如图7所示。

V2

V3

图7由5,匕和V3构成的子回路

⑷接着考虑剩下的节点V八丫5、V6、V7到V1,丫2和V3中某一个节点的最小距离;

Minhj,C2i，C3i且iwl,2,3}=C34=1.8

（5）由图可知，节点5有3个位置（条弧线）可以插入。现在分析将V、参加到哪里适

宜:

①插入到（1,2）间，△=dM+d42-dI2=3.8+2-1.8=4

-

②插入到（2,3）间,△=d24+d43d23=2+l.8-1.8=2

③插入到（3,1）间，△二九+品-d3i=l.8+3.8-2=3.6

比拟上面3种情况增量,插入（2,3）之间的增量最小，所以任意将。节点参加到（2,3）,

所以结果为：T={\%V2,n,V3.vJ其子回路那么变为如图8所示。

图8由Vi,V2,V,和v《构成的了回路

(6)接着考虑剩下的节点V5,V6，V7到V”V2,V3,V.I中某一节点的最小距离

Min{c,,c2i,c3/,c4/|ZGN,\<z<7,且iw1,23,4)=c4S=1.6

由图可知，节点v、有4个位置(条弧线)可以插入。现在分析将vs参加到哪里适宜:

①插入到(1,2)间,△=di5+d52"di2=3.8+3.6-1.8=5.6

②插入到(2,4)I日J,△=dzs+ck「d24=3.6+1.6-2=3.2

③插入到(3,4)间,△=dg+ds厂d34=L8+1.6—1.8=1.6

④插入到(3,1)间,△-dxs+dsi-dsi-1.8+3.8-2=3.6

比拟上面4种情况增量，可将插入(3,4)之间的增量最小，所以将相插入(3,4)

之间，那么结果为：T={V”如V4,v5,v3,vj其子回路那么变为如图9所示。

图9由VI,V2,V3,w和匕构成的子回路

(7)接着考虑剩下的节点V6,