王盛明，卢秉亮

(1.沈阳航空职业技术学院，沈阳 110034;2.沈阳航空航天大学计算机学院，沈阳 110136)

1 引言

对自动化立体仓库进行货位优化的意义在于［8］:根据货物大小来确定货物的存取位置，能够减少当货架出现空货位进行补货时所需的劳动;将出入库频率大的货物平均分配在不同的存储区域，能够避免在某一存储区域出现任务阻塞，进而提高效率，缩短对一批任务总的执行时间;当出入库货物中有易损坏的货物时，应该将易损坏的货物放在运行方向的后面，将不易损坏的货物放在运行方向的前面;相似的货物应该分开存放，避免出现拣选错误。

2 货位分配优化模型

2.1 求重心的方法

设某排货架共有p 列q 层，将距离巷道口最近的列，记为第1 列，最底层记为第1 层，处于第i 列j层的货位记为(i，j)(i=1……p)，(j=1……q)。根据物体的重心坐标公式求物体的重心可以将物体划分为多个小个体来求出重心，而求自动化立体仓库货架的重心则可以采用此种求重心的方法［1］:

Gmax——货架上每个货位所能承受最大重量;

Gij——任意一个货位上货物重量;

Xc、Yc——整体货架的重心坐标

为满足货架稳定性的需要，目标函数是使货架的Y 轴坐标重心最小，X 轴坐标位于货架的中心位置。

2.2 组合多目标优化

为了提高自动化立体仓库的出入库效率，通常将经常使用的出入库频率高的货物摆放至靠近起始点位置。设某货位区编号为R(R=1、2……q)，共有p种货品，其中一种货品的COI 值为Ii，COI为立方体索引号，Heskett 给出的COI 计算公式为:Ii=Ci/fi，其中Ci为某种货品的存储总量所需的库存容量;fi为某种货品的出库频率［6］。货品的存储总量所需的库存容量越小，并且出入库频率越高，则COI值就越小。根据这个原则，将COI 值小的货物存储在离出入口近的货架上，并得到下面目标条件:

为了减少货物存取时间，根据货物存放原则，对出入库频率较高的货物，应该有更少的出入库时间;对出入库频率相对较低的货物，则可以有相对长的出入库时间。这样，能保证整个出入库作业的总时间最短。因此，目标函数是对存取效率的要求，频繁存取的物品应放在能快速取到的货位上，建立公式(4)。

式中:tij——将第i 列j 层货位上的物品搬运到巷道口所用的时间;

Vx、Vy——分别为堆垛机的水平、垂直运行速度(m/s);

l、h——货位的长度、高度(m);

由于上述两个目标条件都是以提高货物的存取效率，减少货物的存取时间为目的，所以可以合并为一个目标函数:

可见，货位的分配需要同时考虑货架稳定性和存取效率，这是一个组合多目标优化问题。对于多目标优化问题，许多情况下各目标是相互冲突的，一般不存在唯一的全局最优解，而是存在一个最优解集合，最优解集中的元素就所有目标而言是不可比较的。使某一目标达到最优性能的解很可能意味着其他目标的性能很差，单纯追求其中某一个目标最优化并没有太大的实际意义，寻求使各维目标函数均较好的满意解(这个解可能对某一目标来说并不是最优的)具有重要的实际意义。通过比较各种算法后，选择Pareto 算法进行求解多目标优化问题。

Pareto 最优解的概念广泛应用于多目标优化问题。对min f(X)=［f1(X)，...，fn(X)］，设其定义域为a，X*∈a，若不存在X∈a，使得fi(X)≤fi(X*)(i=1，...，n)，则称X*是该问题的Pareto 最优解(有效解或非劣最优解)。

Pareto 最优解不是“最优的”，但可以说是“不坏的”，Pareto 最优解一般不是一个，而是一个集合。

3 组合多目标优化实例

由于Pareto 多目标优化问题不具有唯一解。而是具有一组解的集合，在尽可能满足各种约束条件的同时，得到的多个最优解。实例的自动化立体仓库与［3］完全相同。

矩阵(6)为平面货架存储货物矩阵，矩阵中每一个元素代表每个货位存储货物的重量。

初始摆放货物重心为:Xc=3.06，Yc=2.85

通过Pareto 算法进行重心优化后的重心为:Xc=3.01，Yc=2.00，得到矩阵(7)。

矩阵(8)表示初始的每一个货位上货物的出入库频率。

假设每个货位所装载的货物种类各不相同，则货物的COI 值为矩阵(9)所示。

通过Pareto 算法根据COI 值进行货位优化的最优结果见矩阵(10)。

假设单位货位货架的长、宽各为1m，且不计堆垛机启动后的加速运动和停止前的减速运动，堆垛机的水平匀速速度和垂直速度各为1m/s。起始点和终点在右下角。矩阵(11)为堆垛机到达各货位所用的时间，单位是秒。

由于第二个目标函数的最优解为货物的COI值和货物出入库时间的乘积，所以根据上面解，可以得出第二个目标函数的最优结果，用矩阵(12)表示。

由上面两个目标函数的各自最优解得出结论，当货物的纵坐标重心最小，横坐标重心接近中间时，货架最稳定。但此时存放货物的方式就不能以COI值小的货物靠近出入库口的方式存放(第二个目标函数的最优结果)。所以Pareto 多目标优化问题只能得出最优解的集合，难以得出一个满足所有目标函数的最优解。

如果采用传统顺序存放的方式［3］，则S=3210kg，T=621s;优化后，S=3013kg，T=505s。从优化结果进行分析，货位优化后，在降低货架重心的同时，总体出入库时间有较大幅度的减少，显著提高了货架的稳定性，并且提高了货物的存取效率。

4 结束语

对货位可移动式自动化立体仓库货位优化方法进行了研究。货位优化问题是自动化立体仓库运行的关键问题，对提高仓库工作效率起着举足轻重的作用。依据仓库工作情况，建立了优化问题的数学模型，通过Pareto 算法对货位优化问题进行了研究，方便了用户对仓库的管理，并提高了仓库系统的出入库效率和货架系统的运行稳定性。

［1］商允伟，裘聿皇，刘长有.自动化仓库货位分配优化问题研究［J］.计算机工程与应用，2004(26)，16－17，23.

［2］邹晖华，胡吉全，杨艳芳.自动化立体仓库货位分配策略优化研究［J］.湖北工业大学学报，2008，23(3):43－45.

［3］吴钟鸣，卢军锋，智淑亚.自动化立体仓库货位优化研究［J］.装备制造技术，2011(12):23－25，28.

［4］朱耀明.自动化立体仓库优化调度研究［D］.济南:山东大学，2006.

［5］程二九，方庆琯.非等概率条件下自动化立体仓库出入库周期计算［J］.起重运输，2008(7):19－21.

［6］柳赛男，柯映林，李江雄，等.基于调度策略的自动化仓库系统优化问题研究［J］.计算机集成与制造技术，2006(9):1438－1443.

［7］Leandro N de Castro，Jon Timmis.Artificial Immune Systems:A Novel Computational Intelligence ［J］.Approach.Springer－Verlag，2002，5(5):25－34

［8］CaronF，Marchet G，Perego.A Layout design in manual picking system:a simulation approach［J］.Integrated Manufacturing System 2000，11(2):55－59

［9］兰舟，孙世新.基于关键路径知识的任务调度遗传算法［J］.计算机应用，2008(2):272－274.