基于萤火虫算法的订单分批问题研究

郜振华，陈 卓 GAO Zhenhua,CHEN Zhuo

（安徽工业大学 管理科学与工程学院，安徽 马鞍山 243032）

(School of Management Science and Engineering,Anhui University of Technology,Maanshan 243032,China)

0 引言

现阶段大多数配送中心是劳动力密集型的，配送中心中拣选作业劳动量占据配送中心全部劳动量的60%[1]，成本占40%[2]，时间占30～40%[3]。可见，拣选作业在配送中心的重要性不言而喻。

订单分批作为拣选作业的重要环节，是指将一定数目的订单根据一定的规则合并到一个批次进行集中拣选，以提高拣选作业效率的过程。

订单分批主要是为了缩短拣选订单时所用的时间和走过的距离。拣选人员在对订单进行分批作业时，可以将好几个订单合并在一起然后用一套拣选设备一次性拣完，这显然会极大地提高了拣选作业的效率，大中型配送中心应用十分广泛。订单分批比较适合于订单量庞大，但是单个订单下面的商品的种类数又不多的情况。而这与当今消费者的需求又是一致的，所以订单分批有极大的存在价值。

对于配送中心的拣选作业，一般来说最简单最常用的方式是先到先分批（FCFS）。这种分批方式虽然简单易行，但是当今社会对高效率的追求，使得这种分批方式已经不能够满足消费者的要求。这就需要一种新的分批方式，能够提高拣选作业的效率。本文就运用萤火虫算法来进行订单分批，并将萤火虫算法分批和按订单分批、先到先分批进行对比分析，验证其优越性。

1 订单分批数学模型建立

1.1 模型假设

建立订单分批数学模型前，需要对数学模型进行适当假设，以满足研究需要。所以，本研究将对订单分批问题模型的假设如下：

（1）配送中心的拣选区域是8排平行货架，仓库有2个区，仓库的布局如图1所示；

（2）拣选设备（或者拣选人员）数量为2个，以前的学者往往是针对单个拣选设备进行的拣选作业，然而实际生产生活中，多人多设备同时拣选的情况普遍存在，更符合实际；

（3）每一张订单至少包含一种货品；

（4）每个批次订单有多个拣选人员或（或拣选设备）进行拣选，该批次全部拣选完毕后下一个批次才开始拣选；（5）所有拣选设备的容量限制和重量限制是一致的；

（6）每一个批次进行拣选作业时，该批次所有货品总体积和总重量不大于所有拣选设备的总体积和总重量限制；

（7）一个订单是不能分割到两个或两个以上的拣选批次中；

（8）一个批次的订单必须一次拣选完，忽略拣选库位上货物库存不足情况导致的额外作业；

（9）不存在因突发情况而出现的订单插队状况，订单上的货品仓库都是有存货的，并且订单在拣选前一经确认，无法更改，不能再插入新的订单；

（10）拣选人员或者拣选设备的速度是一个恒定值，在拣选时保持不变；

（11）拣选人员对配送中心的平面布局非常熟悉，不考虑因失误导致的往返情况；

（12）所有订单中各个货品的数据以及存储位置是已知的；

（13）货物之间是紧密排列的，不考虑不同货物放在拣选设备产生空隙，存在容积浪费的情况；

（14）每一种货品对应仓库里的一个库位，即不存在一种货品摆放在不同库位或者相同库位存在多种货品的情况；

（15）忽略货品在货架上的垂直位移。仓库中的货架一般都是多层的，货品在货架上的垂直位移不计入到拣选距离的计算，垂直位移的多少不影响拣选人员的拣选距离；

（16）拣选过程中采用改进的S型策略（穿越策略），改进的S型策略指的是设备在第一区的巷道拣选完之后回到的是过道1，而设备在第二区的巷道拣选完之后回到的是过道2，这与单区型的S型策略（穿越策略）有所不同。

1.2 数学模型

建立的数学模型如下所示，该数学模型以拣选距离最短为目标：目标函数：

约束条件：

其中，各字母代表的含义如下：

k：订单的批次；K：所有订单分批的总批数；m：拣选人员或者拣选设备；M：拣选人员或者拣选设备的总数；x：货品x；y：货品y；Z：所有订单中货品的种类数；n：订单；N：需要拣选的订单总数；qnk：批次k中，订单n的货品重量，k=1,2,…,K；capmq：拣选设备最大能承载的货物的重量限制；vnk：拣选批次k中，订单n的货品总体积 ，k=1,2,…,K；capmv：拣选设备最大能承载的货物的体积限制；no_batchk：第k个拣选批次，k=1,2,…,K；Pnk：决策变量，取值为0或1，该决策变量决

图1 仓库布局

定该订单n是否存在拣选批次k中；j：路径；Tjk：拣选批次k中的拣选路径j，j=1,2,…,L；在第k个拣选批次中，拣选设备m在拣选完货物x后再接着拣选货物y所经过的距离决策变量，取值为0或1，该决策变量决定在第k批次里，是否在拣选完货物x后就马上拣选货物y。

式（1）为订单分批数学模型的目标函数，目标函数是求最小值，在拣选完所有批次的货物后，使得总拣选距离最小。式（2）表示，在任意一个拣选批次，该批次所有货品的总重量不超过所有拣选设备所能承受的总重量。式（3）表示，在任意一个拣选批次，该批次所有货品的总体积不超过所有拣选设备所能承受的总容积。式（2）和式（3）对应模型准备中的第（6）条规则。式（4）表示一个订单是不能分割到两个或两个以上的拣选批次中的。式（4）对应模型准备中的第（7）条规则。式（5）表示在一个批次中，拣选路径的总数等于拣选设备的数量，表示该批次货品要做到一次拣选完毕。式（6）为决策变量，决定订单n是否在拣选批次k中，若在则取值为1，不在则取值为0。式（7）为决策变量，决定在第k个拣选批次中，拣选设备m拣选完货品x后是否立即拣选货品y，也就是说如果货品x、y是连续拣选的就取值为1，不是连续拣选的就取值为0。

2 订单分批问题萤火虫算法设计

2.1 萤火虫算法编码

由于本文配送中心订单分批和拣选路径优化问题求解的是配送路径最小时订单的分批组合，解空间对应的是离散的整数域空间，因此需要在萤火虫位置状态与本文研究问题的解通过编码的方式建立一种映射关系，通过对萤火虫位置状态的解码计算目标函数值。萤火虫编码是将所研究问题的可行解从解空间转换到萤火虫算法所能处理的搜索空间中。基于实数进行编码，随机产生分批批次的萤火虫，增加初始萤火虫状态的随机性，尽量使得萤火虫分布到整个解空间=1,2,…,D，其中D代表每条编码长度，同时代表订单号，每个实数xj的取值范围是 1,[ ]m ，m代表最大分批批次。

下面以一个简单例子对本文编码方式进行说明。假设有6个订单，分3个批次完成。随机产生一只萤火虫的编码Xi代表订单1、2、6为第一批次，3、5为第二批次，4为第三批次。

2.2 萤火虫算法解码

萤火虫解码是由算法解空间向实际模型解空间的转换，根据上述的编码方式，本文在解码过程中根据重量、体积约束将不合法萤火虫位置进行调整，依次将每一批次订单的待拣选货物聚成两类，两个拣选设备以改进S型方式分别拣选这两类，计算其路程。

2.3 萤火虫构建

根据萤火虫算法的基本原理，将问题的目标函数与萤火虫的荧光素联系起来，荧光素浓度为：

式（8）中，ρ表示荧光素挥发因子，γ表示荧光素增强因子，fi表示萤火虫的目标函数值。

萤火虫将会向荧光素浓度大的位置移动，萤火虫荧光素浓度大的位置对其他萤火虫的吸引力：

式（9）中，ε表示光照吸收率，dij表示萤火虫与荧光素浓度大的位置的距离。萤火虫将向吸引力最大的位置移动，如果没有比自身位置荧光素更浓的位置，萤火虫则随机移动一步。发挥群体智能作用，萤火虫从局部寻优实现最终全局寻优。

萤火虫携带信息包括变量与函数两部分信息。

（1）变量部分：包括萤火虫总数N、荧光素挥发因子ρ、荧光素增强因子γ、光照吸收率ε、移动的步长Step等基本参数部分，另外还包括萤火虫位置状态编码为订单号。萤火虫个体之间的距离计算采用同一位置上不同数字的总个数。举例子来说明萤火虫个体间的距离相同位置上只有第5、6位相同，那么两只萤火虫之间的距离为4。

（2）函数部分：主要是包括目标函数以及萤火虫的两种行为函数以及行为评价函数。选择更低的总路径作为萤火虫执行行为的行为评价准则。

（3）解空间：萤火虫算法中萤火虫所在的位置对应着数学问题中的解空间，根据本文研究的模型，解空间是非常庞大的。用公式表示如下：SP=mn，其中SP代表解空间。n表示订单数量，m代表订单所在的批次。

2.4 行为实现

（1） 吸引行为

假设某萤火虫当前的位置信息是Xi，搜索当前邻域内的其它萤火虫，记录亮度最强的萤火虫位置Xj，如果该萤火虫的亮度强于自身的亮度，则向Xj的方向移动一步，否则，执行随机行为，如式（10）：

（2） 随机行为

如果当前萤火虫位置为视野范围内亮度最强的位置，则萤火虫执行随机行为，本文的萤火虫编码为离散的整数，因此本文的随机行为采用单点变换的方式进行，如随机取一个位置2，则随机行为后的位置就变成了

2.5 算法的终止条件

本文终止条件的依据是是否存在更高的适应度值。根据这一准则可以以最大迭代次数Maxgen作为算法的终止条件，如果满足终止条件，则输出最优路径值以及对应的订单分批批次，否则，继续迭代。

3 订单分批问题萤火虫算法分批

3.1 库位编码和距离计算

3.1.1 库位编码

为方便进行计算，需要对仓库模型的各个参数进行说明，该仓库分为第一区和第二区两个区域，一共有8排货架，3个过道，7个巷道，1排货架一共有24个库位（一区二区各12个），入口处和离入口最远处的通道是没有拣选库位的。图1中，过道宽度a=2m，存储货品库位的长度和宽度是一致的b=c=1m，巷道宽度d=1.5m。

为了计算两个待拣选点之间的距离，可以首先对一个待拣选点进行编码操作，具体的编码方式是：[区域编号，巷道编号，巷道左右侧编号，库位编号 ]，这样就可以清晰明确地知道待拣选点的具体位置，各个编号都是自然数编码。区域编号指的是，将仓库分为两个区，靠近出入口的是第一区，编号为1，远离出入口的是第二区，编号为2。区域编号只能是1或者2中的一个。巷道从出入口的第一个巷道开始编号，越远离出入口，巷道编号越大，因为巷道一共是7条，所以巷道编号为1到7的自然数。巷道左右侧编号指的是，背向过道1，面向过道2时，位于巷道左侧的待拣选点，编号为1，位于巷道右侧的待拣选点，编号为2。库位编号指的是库位点的编号，以过道为分界线，从左到右依次从小到大编号，库位点一共是14个，所以库位编号为1到14的自然数。出入口的编号是[0,0,0,]0。例如，图1中标号为2的待拣选点的编号是标号为7的待拣选点的编号是[1,1,2,]3。这种标号方式清晰自然，而且可以很便捷地进行扩展。考虑到每个待拣选点都有货品需要拣取，可以将每个待拣选点的货品重量和体积信息编码进去，这样每个待拣选点的信息将会更加全面。例如编号指的是在第二区，第4个巷道，该待拣选点位于巷道右侧，从左到右第8个货架的位置上，该待拣选点上的货品重量为2KG，体积为1dm3。

3.1.2 距离计算

库位编码是为了更好地计算两个库位之间的距离。对于任意两个库位，两个库位的编码分别是]和采用如下步骤进行求解：

（3）计算穿越库位的距离，分为以下几种情况：

图2 穿越库位的两种路线

总距离为穿越过道的距离、穿越巷道的距离、穿越库位的距离之和。

3.2 萤火虫算法分批

设置拣选货品的重量限制为1～5KG，拣选货品的体积限制为1～10dm3，拣选设备的数量为2，拣选设备的重量限制为1～50KG，拣选货品的体积限制为1～100dm3。随机100个订单数据，预设订单批次数50，订单批次数订单中货品的待拣选库位的数量为1～10。萤火虫算法的代码限于篇幅不做附录。运用萤火虫算法对100个订单数据进行订单分批。每次迭代的结果如图3所示。在萤火虫算法进化的过程中，适应度值是目标函数值的倒数，随着迭代次数的增加，其值是不断上升的，表明个体的适应度是在不断增加的，具体如图4所示。

萤火虫算法进行分批，一共分为了25个批次。限于篇幅，不做一一展示。其中第1、第2批次的拣选路径图如图5、图6所示。

图3 萤火虫算法进化图

第1批次29个拣选点，为订单28,32,37,63,96。第2批次7个拣选点，为订单13,100。第3批次22个拣选点，为订单21,34,47。第4批次35个拣选点，为订单17,25,61,81,99。第5批次27个拣选点，为订单27,40,41,48,69。第6批次25个拣选点，为订单45,56,65。第7批次32个拣选点，为订单9,11,29,33,54。第8批次26个拣选点，为订单26,91,93。第9批次9个拣选点，为订单59,84。第10批次28个拣选点，为订单8,22,35,55,76。第11批次30个拣选点，为订单2,44,52,83,92。第12批次27个拣选点，为订单18,36,58,82。第13批次29个拣选点，为订单30,68,71,73。第14批次27个拣选点，为订单5,38,70,85。第15批次33个拣选点，为订单6,39,60,67,86,98。第16批次33个拣选点，为订单43,51,77,79,95。第17批次30个拣选点，为订单19,31,49,50,80。第 18批次26个拣选点，为订单 57,62,87,89。第19批次30个拣选点，为订单7,16,53,64,74,90。第20批次23个拣选点，为订单42,72,94,97。第21批次18个拣选点，为订单20,23,46。第22批次23个拣选点，为订单4,10,66。第23批次25个拣选点，为订单1,3,14,15。第24批次15个拣选点，为订单24,88。第25批次7个拣选点，为订单12,75,78。

图4 萤火虫算法适应度值图

图5 萤火虫算法分批第1批次拣选路径图

图6 萤火虫算法分批第2批次拣选路径图

4 比较分析

4.1 按订单分批

按订单分批十分简单易行，也是最原始的订单分批方式，按照订单到达的前后次序，对订单进行顺序的拣选，每次拣选作业只处理一个订单，即从1～100个订单一一拣选。按照改进的S型策略进行拣选，运用MATLAB编程，具体编程限于篇幅，不做详述。

分别计算设备1和设备2的拣选距离。总拣选距离即为设备1和设备2的拣选距离之和。

按订单分批的设备1拣选距离：

按订单分批的设备2拣选距离：

按订单拣选的拣选路径总距离为9 235+10 340=19 575m。

4.2 先到先分批

先到先分批分批指的是，订单按照订单到达先后顺序从1～100个订单依次进行分批，但是要满足分批原则，即满足拣选车辆的载重量和容量限制。一个批次可以处理多个订单。按照改进的S型策略进行拣选，运用MATLAB编程，具体编程限于篇幅，不做详述。按照先到先服务分批策略进行分批，一共分为了23个批次，各批次情况如下（数字代表订单号，括号内订单表示同一个批次）：

分别计算设备1和设备2的拣选距离。总拣选距离即为设备1和设备2的拣选距离之和。

先到先分批分批设备1拣选距离：

先到先分批分批设备2拣选距离：

先到先分批的拣选路径总距离为4 108+4 305=8 413m。

4.3 萤火虫算法分批

分别计算设备1和设备2的拣选距离。总拣选距离即为设备1和设备2的拣选距离之和。

萤火虫算法分批设备1拣选距离：

萤火虫算法分批设备2拣选距离：

萤火虫算法进行分批的总拣选距离即为3 801+4 128=7 929m。

4.4 比较分析

按订单分批、先到先分批、萤火虫算法分批三种分批方式，分批的批次数分别为100、23、25，总拣选距离分别为19 575m、8 413m、7 929m。可见，先到先分批和萤火虫算法分批比按订单分批的分批次数分别减少77%、75%，先到先分批和萤火虫算法分批比按订单分批的总拣选距离分别减少了57.02%、59.49%。具体如表1所示。

表1 三种分批方式拣选距离对比

5 总结与展望

5.1 研究总结

本文针对配送中心拣选作业的订单分批问题，建立了订单分批问题的数学模型，设计了萤火虫算法，并运用MATLAB编程对其进行求解，将求解的结果与传统的按订单分批和先到先分批进行了对比分析，验证了萤火虫算法分批在订单分批问题上的优越性。

5.2 研究展望

（1）本文的仓库模型是双区型，拣选设备是2个。可以考虑将仓库模型改为多区型，拣选设备设定为多个，这样会更加符合实际。

（2）本文拣选的时候采用的是改进的S型策略。还可以考虑更多策略的结合与运用。

（3）本文只是以拣选距离最短为单一的目标函数。实际上订单分批还受到拥堵状况、消费者需求等的影响，可以考虑建立订单分批的多目标数学模型。