杨小明，徐子奇，金雯，舒 帆

(1.上海海事大学离岸工程研究院，上海 201306;2.上海海事大学物流工程学院，上海 201306)

0 引言

订单货物拣选作业在物流配送中心总劳动量占比高达60%以上，是物流配送中心诸多作业中最费时费力的环节[1]。堆垛机自动化拣选作业是解决人工拣选效率低下的重要技术手段。因此，在电商迅猛发展背景下自动化立体仓库得到了快速发展。近年，配送速度逐渐成为电商最重要的竞争力之一，以盒马生鲜、京东到家为代表的新兴电商甚至要求门店附近3公里范围内，30分钟送货上门。在制造企业中，生产线上零配件的准时需求同样关键，越来越多的制造企业开始重视零配件的仓储管理和配送效率。

仓储配送中心货物拣选通常分为摘取式(digital picking)和播种式(digital assorting)，为适应高标准的拣选效率和拣选质量，避免错漏等问题影响配送和生产，“播种+摘取”的复合式拣选方式得到快速推广。该方式秉持了播种式进行领料需求汇总的方法，将需要的物料逐个取出并放置于分拣区内，再根据领料单先后顺序进行拣选，既发挥播种式拣选优点，避免堆垛机杂乱反复行走，又能兼顾领料单先后顺序，但这种拣选方式也给堆垛机拣选作业序列的决策带来了新的困难。

自动化立体仓库堆垛机拣选序列优化问题类似于旅行商问题(Traveling Salesman problem，TSP)，都是属于NP难题[2]。近年来国内外有众多学者对这类问题展开了研究，研究的重点主要集中于系统拣选效率的提高。

堆垛机拣选路径优化问题中一个重要目标是设备拣选行程最短。……