2007年 2月 系统工程理论与实践 第 2期
文章编号：1000．6788(2007)02．0139．05
自动化立体仓库拣选作业路径优化问题研究
常发亮，刘增晓，辛 征，刘冬冬
(山东大学 控制科学与工程学院，济南 250061)
摘要： 合理优化货物的拣选路径是提高 自动化仓库运行效率的一种有效方法 ．通过分析自动化仓库拣
选作业的工作特点，为自动化仓库拣选作业创建了含装箱约束条件的多目标优化新型数学模型，用遗传
算法对该数学模型进行了求解，基于不可行程度和作业次数对遗传算法初始种群的生成进行了改进．实
验仿真和工程实际应用表明该模型和算法是可行、有效的．
关键词： 遗传算法；自动化仓库；拣选路径；NP-难问题
中图分类号： 11)18 文献标志码： A
Research on the Order Picking Optimization Problem of the
Automated Warehouse
CHANG Fa—liang，LIU Zeng—xiao，XIN Zheng，LIU Dong—dong
(School of Control Science and Engineering，Shandong University，Ji nan 250061，China)
Abstract： Optimizing the order picking is effective on advancing the working efficiency of automatic warehouse．
According to the characters of picking working in automated warehouse，a llew mathematic model was proposed with
capacity constrains and multiple objective．A genetic algorithm was presented to solve the pmblem with the initial
population based on unfeasible degree and work times．Simulation and practice shows that this model and method is
useful an d effective．
Key wolds： genetic algorithm；automa ted warehouse；order picking；NP-hard pmblem
O 引言
自动化仓库集存储、输送、分发、管理等功能于一体，具有存储容量大、占地面积小、周转速度快、货物
破损率低、方便管理等特点，是现代物流系统的重要组成部分，也是 CIMS集成环节之一，在物资供应部
门、大型商业系统等领域有着越来越广泛的应用．拣选作业是 自动化仓库一种常用的作业方式，合理解决
拣选作业优化调度是提高自动化仓库运行效益的有效手段 ．国内外目前对拣选作业的研究大都将拣选路
径抽象成旅行售货商(TSP)问题_1“]，忽略了周转货箱的容量限制，将堆垛机假设成可携带无限多的货物
进出巷道，因此该数学模型只能应用于部分系统．目前我国不断投入使用的自动化仓库仅依赖硬件来提高
运行效率，拣选作业没能采用合适的优化算法，成为制约效率提高的主要瓶颈．为此，本文根据自动化仓库
拣选作业的特点创建了一种含装箱约束条件的多目标优化新型数学模型，并用改进的遗传算法进行了求
解，将该算法实际应用到了我们建造开发完成的某军械器材配送系统，取得了很好的优化效果．
1 拣选作业路径优化数学模型
由我们建造开发完成的某军械器材配送系统自动化仓库如图 1所示，有 10排固定货架，每排货架由
10层72列共720个货位组成，相邻两排货架间留有一条巷道，每条巷道内有一台堆垛机进出巷道进行货
物取放，堆垛机可同时沿巷道水平方向和垂直方向运动．系统有单元出库、单元入库、拣选出库、拣选入库、
收稿 日期 ：2005—11-16
资助项目：国家自然科学基金(60104009)；山东省自然科学基金(Z2005G03)
作者简介：常发亮(1965一)，男(汉)，山东省寿光市，教授，博士，主要研究方向计算机自动视觉，物流控制与调度，智能
交通等；刘增晓(1980一)，男(汉)，山东省青岛市，硕士研究生，研究方向为物流控制与调度．
维普资讯
140 系统工程理论与实践 2007年 2月
盘库、倒库等工作模式．对于小批量、多品种出入库，拣选作业的执行效率最高．执行拣选出库作业时，每条
巷道的堆垛机携带周转货箱从巷道口出发，依次经过若干个目的货位，从 目的货位中取出一定数量的货
物，周转货箱装满后将其送回巷道口，再取另一空周转货箱进入巷道取货，直到取完所有要取的货物 ．堆垛
机运行路线如图2．图2描述了堆垛机执行两次作业(即两次进入巷道取货)，从 5个货位点取货的情况，
图中每个结点表示一个货位，坐标(0，0)表示巷道口．
固定货架及堆垛机运行参数作如下设定：
设定 1：操作者对某一货位的拣选时间固定，不随该货位在拣选路径中的拣选顺序不同而变化．
设定 2：堆垛机在水平方向和垂直方向上独立运动，运行速度恒定，分别为 和 ．
设定 3：货位间距为常数，h为货格高度，b为货格宽度．
设定4：货物包装规则，周转货箱装箱能力仅与待装货物体积和周转货箱体积有关．
图 1 某军械器材配送系统自动化仓库
9h
81a
41a
3h
2h
h
图2 堆垛机运行路线
根据以上设定，堆垛机由货位点 i运行到货位点_『，水平方向和垂直方向走过的路程之和为
d =I X
．
／ 一 i I+I 一Yi I， (1)
其中： ，Yi为货位点i的坐标； ， 为货位点 的坐标．
所需要的时间为：
t = max{I X
．
／ 一 I Iv ，I 一Yi I Iv，}， (2)
执行每次拣选作业满足条件
∑g <Q， (3)
式中：g为第 个货位待拣选的货物体积；Q为周转货箱体积，Q≥max{gi，i=1，2，⋯，n}；N为该次作业待
拣选货位数目．
自动化仓库拣选作业路径问题(简称 w．OPP)优化算法可描述为：在每次作业拣选货物总量不超过周
转货箱装箱能力的前提下，如何安排货物的拣选顺序，以减少堆垛机运行时间，同时减少堆垛机作业次数
(提高货物装箱率，提高输送系统效率)，减少堆垛机垂直和水平方向走过的总路程(节省能源)．
将 n个待拣选货位依次编号为{1，2，3，⋯，n}，根据以上假设，可建立 w．OPP数学模型如下：
min∑t ∑ ：， (4)
rainm， (5)
min∑d ∑ ：． (6)
约束条件为：
骞 =
．
J ⋯一
， ㈩
∑ ：一∑ ：=0， =1，2，⋯，m；p=0，1，2，⋯，n， (8)
= 1，2，⋯，m， (9)
维普资讯
第 2期 自动化立体仓库拣选作业路径优化问题研究 141
式中：m为作业次数；n为待拣选的货位总数； 为从货位i到货位 的时间损耗； 为从货位i
路程； ={ ： 拣选完货位 的货物后立即拣选货位 的货物．
(10)
(11)
到货位 的
目标(4)是确定堆垛机运行时间最短，目标(5)是确定作业次数最少，目标(6)是确定水平方向和垂直
方向走过的总路程最短，约束(7)保证每个货位被访问一次，回到巷道口 m次，约束(8)要求访问某货位和
离开某货位在同一次作业，约束(9)要求每次作业拣选的货物体积不能大于周转货箱体积，约束(10)用于
消除子环，约束(11)是参数的取值范围．
最少进出巷道次数由(12)式决定
r ， 1
m：Uplnt【∑qi／Q J， (12)
(12)式中， 胁[]表示大于括号内数字的最小整数．
分析此类问题的数学模型可知，如果不考虑目标(5)、(6)和装箱约束条件，则该问题可规约为旅行商
问题，即旅行商问题是 W—OPP的特例．Garey已经证明旅行商问题是 NP一难问题，因此，我们认为 W—OPP具
有 NP一难问题难度．
2 遗传算法求解
遗传算法是一种基于生物进化机制的随机搜索算法，能有效进行概率意义下全局搜索．采用遗传算法
可以在有限的时间内获得 W—OPP的最优或次优解，满足工业现场的实际需求．解决 W—OPP的遗传算法可
作如下构造．
2．1 算法构造
1)染色体编码方式．采用 自然数编码，令每个染色体对应问题的一个解，则染色体可表示为(i。，i ，
⋯
，i，0 iⅢ ，⋯，i + 一。)．染色体的每个基因表示一个货位点的序号，将巷道口作为虚拟货位点，用 0表示，
每个染色体有 m一1个0．如染色体编码串(2 5 0 1 4 3)表示堆垛机第一次作业依次拣选 2、5货位，第二次
作业依次拣选 1、4、3货位．
2)初始种群．初始种群目前较多采用随机产生的方法．考虑到堆垛机执行 m次作业产生(9)式的 m
个约束条件，当 m值较小时，采用随机数产生的方法会在初始种群中产生大量不可行解，且一个染色体编
码往往有多个约束条件不能满足．为提高遗传算法收敛速度，又不至于使算法收敛于局部最优解，我们提
出了一种基于不可行程度和作业次数的启发式初始解筛选算法．首先随机产生一个染色体编码，如果该编
码违背约束条件的程度小于等于 P，则保留，如果大于 P，则删除．然后采用相同的方法依次产生含 pop
—
s／ze个染色体的初始种群．如果经 r(r>pop
—
s／ze)次计算还不能产生所需的 pop
—
s／ze个染色体，则认为可
行解区域太小，即使能最终产生可行解，目标函数(4)和(5)也难以达到最优或次优，应增加作业次数．当 P
=0时，相当于拒绝不可行解，条件过于苛刻，初始群体一般难以形成 ．P取一个较小的数可使算法从可行
域和不可行域两个方向搜索最优解．
3)适应值函数的确定 ．每个染色体的适应值通过(13)式确定 ．
fitness：1／( l t+ 2 d+ )， (13)
式中
= ∑ ∑ ；，
i ri k
d=∑d ∑ ，
1．，
P=∑max[∑q ∑ 一Q,O]，
(14)
(15)
(16)
m
2
=
m
一 一
2
l
1
=
U1
有
所 ～
f
对
=
一 ．
≤ ¨
∑
∑
维普资讯
142 系统工程理论与实践 2007年 2月
(13)式中 埘，和 埘：表示运行时间和运行路程在适应值函数中的重要性比例．肘是一个较大的整数
，保证
该算法同时从可行域和非可行域收敛于最优b ．M取值太大，则相当于拒绝处理，M取值太小
，有可能使
算法收敛于非可行解区域．(14)、(15)、(16)式分别表示运行时间、运行路程、不可行程度 ．
4)遗传算子．选择方法采用轮盘赌方式，交叉算子采用 OX ，变异算子采用逆序法 ．
2．2 算法步骤
Stepl 设置最大遗传代数 ，
—
gen，种群规模 pop
— s／ze，交叉概率 P ，变异概率 P ，根据(12)式计算
最小作业次数 m．
Step2 按 2．1所述方法产生初始种群．如果计算 r次未产生初始种群，则 m=m+1，重新产生初始种
群．迭代代数 gen=0．
Step3 按(13)式计算各染色体适应值，采用轮盘赌方式进行选则，如果这些染色体不包含最好解 best
f，则用 best f代替当代最差染色体．
step4 按交叉概率 P 选择染色体，采用 OX交叉算子进行交叉．
Step5 按变异概率 P 选择染色体，采用逆序法变异．
Step6 gen=gen+1，如果 gen小于最大代数，
— gen，转 Step3．
Step7 如果获得可行解，退出；否则，m=m+1，转 Step2．
3 实验仿真与使用效果
货架及堆垛机参数设定如下：b=1 m，h=1 m， =lm／s， =2m／s，Q=70d m，随机产生30条货单，各
货位点的横坐标、纵坐标和待拣选货物体积表示如下：{(63，4，9)(6，9，2)(22，8，9)(5，9，8)(26，5，7)(44，9，
8)(40，5，7)(58，7，9)(19，0，3)(54，1，8)(47，7，8)(4，5，2)(27，8，2)(18，7，3)(54，4，10)(30，3，4)(53，6，5)
(54，6，1)(2，1，6)(59，4，7)(53，7，1)(41，8，7)(38，5，7)(4，0，9)(27，6，8)(38，2，5)(47，0，7)(3，6，6)(20，0，4)
(2，3，5)}．
按照货单顺序进行拣选作业，箱满后回巷道口，
求得的性能指标作为优化前性能指标．取 P，=0．5，
P =0．06，，
—
gen=1000，埘1=0．08，埘2=0．O1，用
本文介绍的遗传算法求得一个最优拣选路径用货位
点次序表示为 {25，16，7，22，11，15，6}、{17，10，18，
21，8，1，20，27，26，23，13，29，14}、{24，28，12，4，9，5，
3，2，30，19}．优化前后性能指标比较如表 1，优化后
的运行时间是优化前的35．7％，运行路程是优化前
的43．7％，优化效果十分明显．取 Q=30d m，求得
表 1 拣选作业优化前后性能指标比较
周转箱体积 运行时间 运行路程 作业次数
(Q／d3m) (t／s) (d／m) (m)
优化前 844 948 3
Q=70
优化后 301．5 414 3
优化前 858 992 7
Q=30
优化后 6l1 750 6
一 个最优拣选路径表示为{28，12，2，5，29，4}、{26，20，15，14，9}、{8，10，7，19}、{13，16，23，27，1，18}、{30，3，
6，25}、{11，17，21，22，24}，优化前后性能指标比较如表 1．
采用同一批货位点，取 P =0．5，P =0．03，， — gen=500，Q=40d m，为便于比较，不考虑路程优化，
取 埘。=0．O1，埘：=0，初始种群随机产生和改进后的优化结果比较如表 2．由表 2可知，初始种群改进后求
得的 t更接近最优值，取 50次计算的均值，改进后比改进前节省 17．3s． ‘
表 2 种群初始化方法性能比较
运行时间(t／s)计算 50次统计
初始化方法
1一lO次均值 11—20次均值 21—30次均值 31—40次均值 41—50次均值 1—50次均值
随机法 482．0 495．8 478．5 493．4 485．4 487．0
改进算法 476．0 445．4 479．3 471．9 475．7 469．7
维普资讯
第 2期 自动化立体仓库拣选作业路径优化问题研究 143
该拣选作业数学模型和优化算法已成功应用到改造后的某军械器材配送系统．在实际应用中，优化率
不仅与待拣选货位的物理布局和货位点数 目有关 ，与各货位点待拣选货物体积的分布情况和周转箱装箱
的复杂性有很大关系．当各货位点待拣选的货物体积较大时，随机生成初始种群的方法往往需要多次增加
m 值，多次调用遗传算法才能生成可行解，而初始种群改进后一般调用一次遗传算法就能找到最优可行
解 ．
4 结论
实验仿真和工程实际应用都证明为 W．OPP创建的数学模型具有较强的实用性，为该数学模型设计的
改进遗传算法高效、可靠，能有效提高自动化仓库拣选作业的运行效率，节省能源．对遗传算法初始种群的
改进方法对解决某些组合优化问题和NP．hard问题也具有普遍意义．
随着 自动化仓库的迅速普及和发展，拣选作业路径优化算法的研究有着广阔的研究空间和发展前景．
可以尝试用其它的演化计算方法和运筹学方法解决 W．OPP，将 W．OPP纳入 自动化仓库整体作业，配合输
送系统统筹考虑．
参考文献：
[1] Ratliff，H．Donald，Rosenthal Amon S．Order-picking in a rectangular warehouse：A solvable case of the~avehng salesman problem
lJj．Operations Research，1983，31(3)：507—521．
[2] Rana，Krishan．Order picking in narrow·aisle warehouses[J]．International Journal of Physical Distribution＆Logistics Management，
1990，20(2)：9—15．
[3] 田国会，张攀，等．基于混合遗传算法的固定货架拣选优化问题研究[J]．机械工程学报，2OO4，40(2)：141—144．
Tian Guohui，Zhang Pan ，et a1．Research on the f'Lxed shelf order-picking optimization problem using a kind of hybrid genetic
algorithm[Jj．Chinese Journal of Mechanical Engineering，2004，40(2)：141—144．
[4] 田国会，张攀，等．一类仓库作业优化问题的混合遗传算法研究[J]．系统仿真学报，2004，16(6)：1198—1201．
Tian Guohui，Zhang Pan ，et a1．Research on one class ofoptimization problem ofthe automated warehouse using a new kind ofhybrid
genetic algorithm[J]．Journal of System Simulation，2004，16(6)：1198—1201．
[5] Misuo Gen，Runwei Cheng．Genetic Algorithms and Engineering Optimizationl Mj．John Wiley＆Sons，New Y0rk，2000．142—
237．
[6] Davis L．Adapting operator probabilities in genetic algorithm[c]／／Proceedings of the third international conference on genetic
algorithms．George Mason University，United States，1989．61—69．
维普资讯
