运用蚁群算法解决物流中心拣货路径问题

熊芳敏, 岑宇森, 曾碧卿

( 1. 华南师范大学南海校区计算机工程系，广东佛山 528225；2. 广东肇庆学院计算机学院，广东肇庆 526061)

运用蚁群算法解决物流中心拣货路径问题

熊芳敏1, 岑宇森2, 曾碧卿1

( 1. 华南师范大学南海校区计算机工程系，广东佛山 528225；2. 广东肇庆学院计算机学院，广东肇庆 526061)

研究了运用蚁群优化算法解决物流中心拣货路径问题，并与传统的基于穿越策略的拣货路径策略做比较．执行结果显示以蚁群优化算法解决物流中心仓储拣货作业，可明显减少拣货路径的距离及拣货时间，提高物流中心的作业效率与服务水平．

蚁群算法； 物流； 拣货路径； 优化

在物流中心的各项内部作业中，拣货作业是一项重要且繁杂的工作．拣货是将顾客订单上不同种类的产品予以分类，再依据产品的数量将产品从货架上取出．拣货员在拣货作业的过程中，由于采用不同的拣货路径策略，造成拣货顺序与行走路径有所差异，进而影响拣货路径的距离和拣货效率．最为常用的拣货策略是穿越策略．

所谓穿越策略是拣货员拣货时，从走道一端进入，另一端离开．当走道较窄时，拣货人员可同时拣取走道两侧货架上的商品．反之，如果走道较宽时，则拣货人员就必须横跨走道，如图1所示．因为所经过路径的轨迹类似“Z”字型，所以也称为“Z型穿越策略”．

图1 穿越策略路线图Fig.1 Z-traversal strategy

由于穿越策略没有对仓库内的具体结构和货物摆放特点做出分析，所以拣货员所走的路径往往不是最短路径和最省时间[1-3]．而对于物流中心，能否在合理的时间内完成拣货作业，直接关系着物流中心的经营成本与服务质量．本文分析物流中心传统仓储中的拣货路径问题，并建立适当的数学模型，然后利用蚁群优化算法寻找最优拣货路径，以缩短拣货路径距离及减少拣货作业时间，从而提高物流中心的作业效率与服务水平．

1 蚁群算法模型及描述

蚁群优化算法(Ant Colony Optimization,ACO)是20世纪90年代由意大利学者M.Dorigo、V.Maniezzo、A.Colorini等人通过模拟自然界蚂蚁觅食行为提出的一种全新的模拟进化算法．蚂蚁在觅食过程中，会依据一定的模式来选择行走的路径，并且会在走过的路径上留下独特的信息素，以利用信息素去寻找食物以及往来巢穴的路径．如图2所示，假设当蚂蚁有2条以上的直线路径可选择时，每条路径起初被选择的概率是相等的，如图2(A)．若中间出现障碍物时(如图2(B)所示)，由于蚂蚁必须在障碍物两侧的路径做选择，选择较短路径的蚂蚁(如图2(C)所示)，在外出寻找食物到回巢的时间一定少于选择另一较长路径的蚂蚁所花费的时间．因此，较短路径上遗留的信息素也会比较多，而下一批要出发的蚂蚁则会选择拥有较多信息素的路径行走．此过程持续循环，则蚂蚁都会趋向于行走相同的较短路径．反之，另一路径上的信息素则会慢慢蒸发不见，导致被选择的概率越来越小．根据此原理所发展出求解最优路径的算法，称为蚁群优化算法[4-5]．

图2 蚂蚁觅食原理图Fig.2 Ant foraging chart

假设现在有m只蚂蚁要寻找经过n个节点的最短路径，蚁群优化算法的流程可以描述如下[4-5]：

步骤1：将m只蚂蚁随机放在n个节点上(m≥n)．

步骤2：建立禁忌列表(tabu list)存放蚂蚁走过的节点[6]．

步骤3：每只蚂蚁走到下一个节点的概率是随机选择的，并且将所走的节点记录在禁忌列表中，重复此步骤，直到禁忌列表填满为止．蚂蚁随机选取的概率公式为：

(1)

步骤4：根据禁忌表计算每只蚂蚁所走的路线长度，并且记录到目前为止所走的最短路径，然后根据式(2)和式(3)计算每只蚂蚁在每条路径上所遗留的信息素．

(2)

(3)

步骤5：根据式(4)更新所有路径上的信息素数量，同时更新时间点t为t+n．

ij(t+n)=ρ·ij(t)+Δij,

(4)

步骤6：如果尚未到达停止条件，则将所有禁忌表清空，并且重复步骤2至步骤6，直到满足停止条件为止．

2 应用蚁群优化算法解决订单拣货路径问题架构

本文利用蚁群优化算法解决物流中心仓储的订单拣货路径问题，具体架构如图3所示．首先，收集物流中心所存储的商品的基本信息(如：商品体积、商品编号、商品名称及商品代号等)，并将商品安排在适当的存储位置；接着，按照客户订单信息(如：商品数量、订单号码、商品名称及商品代号等)，计算每笔订单的总体体积，在依据拣货车载运商品的体积限制，依照订单的接单次序依次将订单划分为若干拣货批次；最后，利用蚁群优化算法，配合拣货批次的信息(如商品编号及存储位置坐标等)，获得该批次商品的最佳拣货路径．

图3 应用蚁群优化算法解决订单拣货路径问题架构

Fig.3 Structure of applying ACO to solve order form picking

3 实验过程与结果分析

本文与某大型食品物流中心合作，进行实例探讨．该物流中心在每天晚上固定时间停止接收客户订单，并依照顾客订单拣货需求，使用穿越策略进行拣货作业，实现商品在次日送达顾客手中．

3.1收集仓储基本资料

本文从物流中心收集的数据分为2类：

(1)商品资料：商品编号排序、商品名称、商品代号、体积．

(2)订单资料：订单日期、订单编号、商品名称、商品代号、商品数量．

3.2建立商品存储位置

此物流中心的仓储布署为无中间走道的长条式储位，为了改善拣货效率及突出本文所提算法的优越性，经过与该物流中心主管讨论并确认其可行性后，修改了其原始仓储设计，在仓储储位中增加一条宽度为二公尺的穿越走道，而商品储位位置安排则是按照商品编号依序排列．

3.3订单分批

建立商品存储位置后，按照顾客订单及商品体积资料，计算每一笔订单商品的总体体积，接着，依据订单的先后顺序，在满足拣货车体积承载的限制下，完成所有顾客订单的分批工作．籍此，即可得知每个拣货批次所需拣取商品及其存储位置．本文以2009年3月1日订单为例，其订单分批完成后的第一笔拣货单资料如表1所示．

表1 2009年3月1日的第一笔拣货单资料Tab.1 The first picking order form on Mar. 1, 2009

3.4求解拣货路径

本文使用C++语言编译蚁群优化算法，并依据订单分批后的拣货单资料求解最优拣货路径，其中蚁群优化算法的参数设定如表2所示．

表2 蚁群优化算法参数设定值Tab.2 enact parameters value of ACO

表2中的参数是根据以往学者提出的蚁群算法参数优化设置的策略所得[6-8]．

以2009年3月1日的订单批次结果为例，针对每一笔拣货单，利用蚁群优化算法重复求解10次的执行结果，如表3所示．

3.5结果比较与分析

该物流中心原本是采用穿越策略进行拣货作业，以2009年3月1日的订单为例，比较以蚁群优化算法及穿越策略所获得的拣货路径，整理如表4所示．

根据表4可知，相对于传统的穿越策略，运用蚁群优化算法求解拣货路径问题可以有效地减少拣货距离．以第一笔拣货单为例，以穿越策略及利用蚁群优化算法所获得的拣货路径如图4所示．

表3蚁群优化算法求解拣货路径结果整理(以2009年3月1日的订单批次为例)

Tab.3 Results of using ACO to solve order picking route problem (e.g. order forms on Mar. 1, 2009)

拣货单编号平均拣货距离/m最大拣货距离/m最小拣货距离/m拣货距离标准差/m平均CPU时间/s18208298125.38.329389389380.066.2310481061102710.880.849709759692.2102.5599810059857.481.5

表4传统穿越策略与蚁群优化算法的拣货路径结果比较

Tab.4 Comparisons between traditional Z-traversal strategy and ACO on picking route

拣货单编号以穿越策略的拣货距离/m以蚁群算法获得的拣货路径平均距离/m平均改善距离/m平均改善百分比/%11083820262.924.2821322938384.029.05316471048595.036.2141529970559.036.5651691998693.040.98

由图4可知，应用传统穿越策略拣货时，需要从走道一端进入再从走道另一端离开，以拣取该走道的所有待取商品，接着，再拣取下一个走道的商品，因此，在拣货上将会绕行多余的路程[2-3]．相反，蚁群优化算法所获取的拣货路径有数个回转点，故能籍此缩短拣货的路径距离．

图4 蚁群优化算法及穿越策略所获得的拣货路径图Fig.4 Picking route chart achieved by ACO and traversing strategy

仿照前述方式，本文将2009年3月2日—7日的订单进行批次后，利用蚁群优化算法所获得的最佳拣货路径，其相对于传统的穿越策略在拣货距离上的改善结果整理如表5所示．

依据表5可知，对于每日的订单而言，蚁群优化算法皆可有效减少拣货距离，而且大部分的拣货距离改善平均可以达到20%以上，其中以改善30%～40%的居多．此外，蚁群算法的CPU执行时间平均大约为3 min，即使是最长的执行时间也不会超过5 min．若以目前该物流中心每天最多的60车次来计算，也只需要花费5 h的CPU运算时间即可获得最佳路径．而该物流中心的作业方式为每日晚间7点截止收单，并于凌晨2点开始拣货．因此，根据拣货路径的改善结果以及算法所耗费的CPU时间，对于该物流中心而言，本文所提出的利用蚁群优化算法解决仓储的订单拣货路径的方法，是行之有效的．

表5 拣货距离改善统计表Tab.5 Improving picking distance statistic table

4 结论

本文研究透过蚁群优化算法求解物流中心仓储中的最佳拣货路径，以节省更多的拣货路径与时间．根据实例探讨的结果可知，蚁群优化算法所获得的拣货路径明确优于传统的穿越策略拣货路径，且蚁群优化算法的每次CPU执行时间最多不超过5 min．因此，物流中心有充裕的时间整理订单、分批、执行蚁群优化算法程序，并将程序执行结果交由拣货员进行拣货，籍此可明显减少拣货员拣货时间与行走路径长度．因此，本文认为，将蚁群优化算法应用在物流中心的仓储拣货作业上是一种有效且可行的方法．

[1] 彭本红, 邓谨.第三方物流合作伙伴关系的竞争协调模型和治理模式探讨[J].商业研究,2006(21):114-117.

PENG Benhong,DENG Jing. Competition-coordination mode and governance pattern in third-party logistics partnership[J]. Commercial Research,2006(21):114-117.

[2] 雷宣云,叶飞,杨立洪.不完全信息条件下的虚拟企业合作伙伴选择模型[J].工业工程,2005,8(4):63-65;69.

LEI Xuanyun,YE Fei, YANG Lihong. Parthers selection model for virtual enterprises under the conditions of imperfect information[J]. Industrial Engineering Journal,2005,8(4):63-65;69.

[3] 李绍新,张延娇. 改进的遗传算法在蛋白质结构预测中的应用[J]. 华南师范大学学报:自然科学版,2009(1): 56-60.

LI Shaoxin, ZHANG Yanjiao. The application of improved genetic algorithms for predicting protein structures[J]. Journal of South China Normal University:Natural Science Edition, 2009(1): 56-60.

[4] DORIGO M,MANIEZZO V, COLORNI A. Ant system:opti-mization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man and Cybernetics-Part B, 1996, 26(1):28-41.

[5] BEKTAS T. The multiple traveling salesman problem[J]. An Overview of Formulations and Solution Procedures, 2006,34(33)：209-219.

[6] 黄美玲,白似雪.蚁群神经网络在旅行商问题中的应用[J]. 计算机辅助设计与图形学学报, 2007, 19(5): 600-603.

HUANG Meiling,BAI Sixue. Application research for TSP based on neural Network-Ant colony algorithm[J]. Journal of Computer-Aided Design and Computer Graphics, 2007,19(5):600-603.

[7] 蒋玲艳,张军,钟树鸿.蚁群算法的参数分析[J].计算机工程与应用,2007,43 (20):31-36.

JIANG Lingyan,ZHANG Jun, ZHONG Shuhong. Analysis of parameters in ant colony system[J]. Computer Engineering and Applications,2007,43 (20):31-36.

[8] 刘利强,戴运桃,王丽华.蚁群算法参数优化[J].计算机工程,2008,34(11):208-210.

LIU Liqiang,DAI Yuntao,WANG Lihua. Ant colony algorithm parameters optimization[J]. Computer Engineering, 2008,34(11):208-210.

Keywords： ant colony optimization algorithm; logistics; order picking tour; optimization

【责任编辑 庄晓琼】

RESOLVINGORDERPICKINGTOURPROBLEMSINTHEDISTRIBUTIONCENTERTHROUGHANTCOLONYOPTIMIZATIONALGORITHM

XIONG Fangmin1, Cen Yusen2, ZENG Biqing1

(1.Department of Computer and Engineering, School of Naihai, South China Normal University, Foshan, Guangdong 528225, China; 2.School of Computer Science, Zhaoqing University, Zhaoqing, Guangdong 526061, China)

The order picking problems in a warehouse of the distribution center through ant colony optimization algorithm (ACO) is studied, which is compared with the traditional picking tours based on the Z-traversal strategy. The results reveal that the ACO can reduce both the picking tour distances and the operation time significantly, thus the operation efficiency and service quality can be improved in a traditional warehouse of the distribution center.

2009-09-17

广东省自然科学基金资助项目 (8151063101000040)

熊芳敏(1979—),女,广东梅州人, 华南师范大学南海校区讲师，主要研究方向：系统智能和软件工程，Email:xfangmin@126.com.

1000-5463(2010)02-0050-05

TP391

A