三、CRAFT

CRAFT（计算机化的设施相对位置布置技术）可用于解决多达几十个生产单位的布置问题；这样的大规模布置问题（实际中一般都在二十个以上）用手工算法是难以或有能解决的，而用 CRAFT 则能较好、较快地予以解决（已开发有软件，可在微机上求解）。

CRAFT 是一种启发式算法：在给定的初始布置方案基础上，按照一定的调整规则，在总运输量（费）减少的方向上，逐次对已有的布置方案进行调整和改进，直到布置方案不能得以改进为止。其调整规则或改变生产单位间的相对位置的方式如下：

（1）2 个单位之间的对调；

（2）3 个单位之间的对调；

  1. 先 2 个单位之间的对调，再 3 个单位之间的对调；

  2. 先 3 个单位之间的对调，再 2 个单位之间的对调；四种规则或方式

中，可任选一种进行位置调整，由于对调的范围在 4 个单位以下，即不能进

行多于 3 个生产单位问的对调，因此常常不能保证得到最优的布置方案。最终得到的布置方案，可能由于（1）所用调整规则的不同、（2）初始

布置方案的不同而有所不同，所以为了得到一个更好的最终布置方案，可分别采用（1）多种规则、（2）多种初始布置方案进行求解，在所得到的多种最终布置方案中择优。

CRAFT 涉及的距离，一般是指两个生产单位中心之间的欧拉距离。所需的输入数据是：生产单位之间的运输量（从至运输量表），生产单位之间的运输费用率（从至费用率表），初始布置方案（初始块状区划图），以及生产单位的固定性（是否固定在某个位置而不能移动）。

表 11—14 给出了一个关于 13 个生产单位的布置问题。生产单位 D 为一个位置固定的单位（行政办公单位）、且为不到达区（无物流）。

表 11-14 从至运输量和从至运输费用率表

至从

1

 2

3

4

 5

6

7

8

9

A

B

C

D

面积

（ m2

面积单位数

1(进料)

1000

3.00

300

1.500

600

 38

2(切削)

1000

1.23

200

0.98

600

 27

3(磨削)

200

0.98

400

1.23

600

1.10

200

 13

4(焊接)

600

2.10

250

 16

5(X 光

照)

200

1.80

400

1.50

210

 13

6(检验)

600

1.00

400

1.50

400

1.20

285

 18

7(打磨)

400

1.00

200

1.00

600

2.40

125

 8

续表

至

从

 1

2

3

4

5

6

7

8

 9

A

B

C

D

面积

(m2)

面积单位数

8(整修表)

200

1.00

275

17

9(油漆)

200

1.30

400

2.10

285

18

A(清洗)

600

1.7

0

150

9

B(装标牌)

200

2.00

75

5

C(储存装运)

715

45

D(行政办公)

576

36

注：方格上方数据为月物流量，下方数据为一个距离单位的单位物货运费；1 个面积单位＝4m×4m 的正方形，一个距离单位 4m；全部可甲面积二 84m

×84m=7056m2，共 16×16＝256 个面积单位。

图 11-8 为一个给定的初始布置方案（初始块状区划图），其相应的总运输费用为 84530.43。在此基础上可用不同的调整规则予以改善：

（1）2 个生产单位间的对调。先对调单位 8 和单位 C 然后再对调单位 3 和单位 C，再对调单位 A 和单位 B，最后对调单位 8 和单位 A。由于不能继续改进，便得到相应的最终布置方案，如图 11-9 所示，对应的总运输费用为73432.23；

（2）先 2 个生产单位问的对调，再 3 个单位间的对调。先 2 个单位间的对调结果同（1），在此基础上，再改变单位 3、4 和 5 的相对位置，得到不能再进一步改进的最终布置方案，如图 11—10 所示，对应的总运输费用为70866.89。

对于同样的初始布置方案，由于先用 3 个单位间的对调方式不能得以改

善，所以，采用 3 个单位间的对调方式的最终方案即为初始方案；采用先 3

个单位间的对调，再 2 个单位间的对调方式的最终方案同于采用 2 个单位间的对调方式的最终结果。各方案对调过程可在微机上显示出来。

比较同一初始方案下的不同调整方式的最终结果，可以发现其中最好的方案为先 2 个生产单位间的对调、再 3 个单位问的对调方式所对产生的最终方案。改变初始方案，也可作类似的分析，可能得到更多的最终结果，使择优的范围更大，这里从略。

1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

1 1 1 1 1 1 1 1 3 3 3 9 9 9 9 9 9

2 1 1 1 3 3 9 9

3 1 1 3 3 3 3 9 9 9 9 9 9

4 1 1 3 3 3 8 8 8 8 A A A

5 1 1 7 7 7 8 8 A A

6 1 1 1 1 1 1 7 7 7 8 8 A A A

7 2 2 2 2 2 2 7 7 8 8 8 8 8 B B B

8 2 2 2 6 6 C C C C C C B B

9 2 2 6 6 6 C C C C

10 2 2 6 6 C C

11 2 2 2 2 2 6 6 6 C C

  1. 4 4 4 4 5 C C C C C C C C C C C

  2. 4 4 5 5 5 C C C C D D D D D D

  3. 4 4 5 5 D D D D D D

15 4 4 5 5 D D

16 4 4 4 4 5 5 5 D D D D D D D D D the total contribution is 84 530.43

图 11-8 初始布置方案

1

2

3

4

 5 6 7 8 9 0 1 2 3 4

5

 6
1 1

1

1

1

 1 1 1 C C C 9 9 9 9

9

 9
2 1 1 1 C C 9

9
3 1 1 C C C 9 9 9 9

9

 9
4 1 1 C C C C C C C B

B

 8
5 1 1 7 7 7 C C B

B

 8
6 1

1

1

1

 1 1 7 7 7 C C B

8

 8
7 2

2

2

2

 2 2 7 7 C C C 8

8

 8
8 2 2 2 6 6 C C C C C 3

8

 8
9 2 2 6 6 6 C 3 3 3 A A

8

 8
10 2 2 6 6 C 3 3 A A

8

 8
11 2

2

2

2

 2 6 6 6 C 3 3 3 A A

8

 8
12 4

4

4

4

 5 C C C C 3 3 A A A

8

 8
13 4

4

5

 5 5 C C C 3 D D D D

D

 D
14 4

4

5

 5 D D D D D D
15 4

4

5

 5 D D
16 4

4

4

5

 5 5 D D D D D D D D

D

 D

最小总运输费用=73742.23

图 11 — 9 最终布置方案（ 1 ）

1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

1 1 1 1 1 1 1 1 C C C 9 9 9 9 9 9

2 1 1 1 C C 9 9

3 1 1 C C C 9 9 9 9 9 9

4 1 1 C C C C C C C B B 8

5 1 1 7 7 7 C C B B 8

6 1 1 1 1 1 1 7 7 7 C C B 8 8

7 2 2 2 2 2 2 7 7 C C C 8 8 8

8 2 2 2 6 6 C C C C C 5 8 8

9 2 2 6 6 6 C 5 5 5 A A 8 8

10 2 2 6 6 C 5 5 A A 8 8

11 2 2 2 2 2 6 6 6 C 5 5 5 A A 8 8

12 3 3 3 3 4 C C C C 5 5 A A A 8 8

  1. 3 3 4 4 4 C C C 5 D D D D D D

  2. 3 3 4 4 D D D D D D

15 3 3 3 4 4 D D

16 4 4 4 4 4 4 D D D D D D D D D D

最小总运输费用＝ 70866.89

图 11 — 10 最终布置方案（ 2 ）