谁能给我提供一个关于解决货位优化的模拟退火算法的程序？

来源：互联网   发布日期：2011-09-28 19:22:28   浏览：5835次  

主要解决如下问题：
1.实例说明
假设某物流中心仓储区，仓储区有36个单元货格用来存放货物，假设货位为矩形。本文采用基于模拟退火的布置评价法对初始布置向量进行改进，从而得到每一层的最优布置向量，此最优布置向量主要由程序输出。最后用“空间填充曲线”逐一安排，产生最优方案。采用空间填充曲线时，该曲线的特点是可以连接每一个货格，即沿着曲线移动一个“点”总可以访问与当前网格相邻的货格，而且每个货格恰好只访问一次。后期布置时，每个货物会被若干个连续的货格所代替。当选取的空间填充曲线不同时，会得到不同的布置方案。最后通过方案的比选选出最优方案。
   
 2.模拟退火算法的实例应用
1.模型(这里i和j为下标，这里写不出来）
设m为某仓储区的货物总数，如表5-1，则m=12。根据货物的面积所计算出的各个货物所需的网格数也在表5-1中给出，设网格总数为n，则此案例中n=36。Cij 为将一个单元的货物从该层网格 i移动到网格 j的单位距离成本，见表5-2；fij 为单位时间从货物 i到货物 j的流量，见表5-3； dij为从货物 i到货物j 的距离（以部门矩心的最近直角距离来衡量），见表5-4。则  


表5-1 各部门物料总重量及所需网格数
部 门 编 号 1 2 3 4 5 6 7 8 9 10 11 12
物 料 总 重 量 60 100 90 130 120 30 150 50 70 80 40 140
网 格 数 3 2 3 1 1 4 5 2 3 4 5 3

下面的三个表格主要记录的是12个货物间的单位移动成本，单位流量以及单位距离，此数据被输入到程序中，从而算出货物间水平移动的最小成本。

表 5-2 各货物间移动的单位距离成本cij(i和j为下标)

部门编号 1 2 3 4 5 6 7 8 9 10 11 12
  1 0 5 3 2 4 2 6 5 4 3 4 5

  2 5 0 4 3 2 4 5 4 2 9 5 2

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

  5 4 2 2 3 0 4 6 3 2 1 4 3

  6 2 4 4 6 4 0 6 4 2 3 4 1

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

  8 5 4 5 5 3 4 2 0 3 2 4 1

  9 4 2 6 2 2 2 4 3 0 3 2 4

  10 3 3 4 4 1 3 3 2 3 0 3 2

  11 4 5 2 8 4 4 1 4 2 3 0 3

  12 5 2 3 4 3 1 2 1 4 2 3 0


表5-3 各货物间单位时间内流量fij(i和j为下标)

部门编号 1 2 3 4 5 6 7 8 9 10 11 12
  1 0 5 7 4 6 8 10 3 2 5 7 8
   
  2 5 0 4 7 6 5 4 3 4 5 7 6

  3 7 4 0 5 6 4 3 5 6 7 2 5

  4 4 7 5 0 3 2 4 7 6 4 3 5

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

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

  7 10 4 3 4 7 6 0 3 5 7 9 2

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

  9 2 4 6 6 5 7 5 6 0 7 4 1
   
  10 5 5 7 4 4 2 7 4 7 0 6 3
  
  11 7 7 2 3 5 4 9 3 4 6 0 7

  12 8 6 5 5 2 3 2 2 1 3 7 0

 表5-4 各货物间的距离dij(i和j为下标)

部门编号 1 2 3 4 5 6 7 8 9 10 11 12
  1 0 20 21 30 35 40 20 16 50 55 60 25
   
  2 20 0 25 30 20 40 55 30 20 60 40 30

  3 21 25 0 60 40 60 20 40 55 20 10 40

  4 30 30 60 0 50 20 40 16 60 20 40 20
 
  5 35 20 40 50 0 60 30 10 40 25 20 40

  6 40 40 60 20 60 0 30 40 25 40 10 60

  7 20 55 20 40 30 30 0 60 25 10 40 25

  8 16 30 40 16 10 40 60 0 20 40 60 10

  9 50 20 55 60 40 25 25 20 0 30 60 25
   
  10 55 60 20 20 25 40 10 40 30 0 20 40

  11 60 40 10 40 20 10 40 60 60 20 0 20

  12 25 30 40 20 40 60 25 10 25 25 40 0

计算步骤及过程
1，随机产生初始布置向量Xo，令X=Xo，X*=X，I=0，I=0,i=1,j=1。r=0.95，M=36。
2，根据以下公式计算当前布置成本Z（X），令To=Z(X)/40且T1=rTo。
minZ=ΣΣCij*fij*dij(i=1,2,...m j=1,2...m i≠j)(i和j为下标)
3a，在X中随机选取两个货物，交换他们的位置，得到领域布置向量Xp。
3b，计算布置成本的减少量⊿Z=Z（X）-Z(Xp),如果⊿Z>0,进行无条件移动，进入步骤3d；否则进行有条件移动，进入步骤3c。
3c，采样得到一个随机变量ξ∈U（0,1）。如果ξ<exp(⊿Z/Ti),进行邻域移动，进入步骤3d；否则不移动，返回步骤3a。
3d：接受领域布置向量，即X=Xp,Z（X）=Z(Xp),且I=I+1。如果Z（X）<Z(X*),就更新历史最优布置向量，即令X*=X，Z（X*）=Z(X)。如果Nj(x)中布置向量都被接受了，即I=Cm的二次方（领域中布置向量的个数），令I=0,进入步骤4；否则返回步骤3a。
4，令i=i+1且Ti=rTi-1，j=j+1。如果j<M,返回步骤3a；否则停止，输出X*。
算法中设置的变量说明：Xo为初始布置向量；X为当前布置向量；X*为历史最优布置向量；Xp为领域布置向量；To为初始温度；Nj(x)为第j个领域；M为要考虑的最大领域数；I为用于记录领域中布置向量被接受的读数器。

4.方案的比选

赞助本站