基于混合蛙跳算法的企业集团订单分配研究

周凌云，郭顺生，李西兴，王 磊

（1.武汉理工大学 信息工程学院，武汉 430070；2.武汉理工大学 机电工程学院，武汉 430070）

设计与应用

基于混合蛙跳算法的企业集团订单分配研究

周凌云1，郭顺生2，李西兴2，王 磊2

（1.武汉理工大学 信息工程学院，武汉 430070；2.武汉理工大学 机电工程学院，武汉 430070）

针对企业集团在订单分配时优先选择内部企业的问题，提出了一个基于产品经济参数和内部企业贡献因子的订单分配策略，解决企业集团订单优先分配量与价格、质量和时间的优化问题。以某建材装备制造集团的订单分配为例，构建了一个基于采购成本最低、不合格产品损失和延期交货损失最少以及对企业集团的贡献最大为优化目标的数学模型。采用改进的混合蛙跳算法对模型进行求解，验证所建模型的合理性和有效性，并与遗传算法、蚁群算法的结果相互比较，验证算法的优越性。

企业集团；订单分配；优先分配；改进混合蛙跳算法

0 引言

在建材装备制造领域，采购成本约占产品成本的70%[1]，使得其对供应商的选择和订单的分配管理显得尤为重要。K. L. Choy研究发现，基于企业智能化信息系统的订单分配管理方式不仅可以提高订单分配的效率，而且还可以优化订单的分配方式，提高订单质量和控制采购成本[2]。

关于订单分配的问题，国内外学者已经进行大量的研究。以成本、质量、折扣等因素构建单个或多目标优化模型[3,4]，同时以生产负荷均衡为目标确保生产周期最短[5]，可以有效地帮助企业控制产品的成本、质量和交货期，其结果具有十分重要的借鉴意义，但建材装备企业集团的订单分配还存在以下问题：一是无法解决集团内部企业优先分配的问题；二是追求生产周期最短对于按单制造企业来说并无益处；三是以零生产负荷来建模，容易出现超负荷分配的现象。

因此，本文根据建材装备集团的实际情况改进了订单分配模型，同时采用一种全新的群智能优化算法——改进的混合蛙跳算法（OSFLA）来求解模型。混合蛙跳算法具有高效的计算性能和优良的全局搜索能力，可以应用于解决多目标优化问题[6]。

1 订单分配模型

1.1 问题描述

集团签订产品合同后，首先确定主导企业来生产核心部件，然后再确定提供外协订单的协作企业，其生产流程如图1所示。

对于建材装备制造集团而言，订单分配需要在内部企业优先分配的前提下，满足产品质量和供货时间的要求，追求采购成本的最小化，其订单分配需要解决的问题，一是权衡选择内部企业与外部企业的利弊，二是规避延期风险与提高质量降低成本的矛盾。

1.2 参数设定

假设集团共有q类订单O={O1,O2,O3,…,Oq}，由n个协作企业j={1,2,3,…,n}来完成。针对建材装备制造集团的订单分配问题，做如下假设：

图1 建材装备制造集团生产流程

1）采购成本包含产品的价格成本和运输成本，不考虑库存成本；

2）每一类订单可由一个或多个协作企业完成，每一个订单只能由一个协作企业生产，且不同的协作企业完成同类订单的周期（交货时间）相同；

3）订单下达时刻，各协作企业的生产负荷已知；

4）交货延迟率以延迟交货一天的概率计算，且延迟多天的概率与一天相同。

为了便于清晰的描述订单模型，本文采用的相关符号和变量如表1所示。

1.3 数学模型

本文确定以综合采购成本C最低、不合格订单数量W最少和延期交货订单数量D最少为优化目标，同时增加集团内部企业的订单修正函数Cλ，确保内部企业可以优先分配订单。

1）成本目标函数。包含价格成本和物流成本：

2）质量目标函数。以不合格订单的数量W来衡量订单质量，不合格率参考以往统计的平均数据：

式(4)为合格产品数量的约束条件，为第i个订单所属的订单类别的不合格率，

3）工期目标函数。以延期交货的订单数量D最少为目标，延迟率Tqj参考以往统计的平均数据：

式(6)为生产负荷的约束条件，为第i个订单所属订单类别的延迟交货率，

4）修正函数。引入完成单个订单对集团的贡献因子ζ( αi, βi, γi)，以经济价值表示：

式(7)中，αi表示内部企业完成第i个订单后与集团的利润共享值，βi表示内部企业之间资源和技术的共享优势，γi表示内部企业完成订单对自身以及集团发展的贡献值。zj表示协作企业是否为内部企业，zj=1表示是，zj=0表示否。

表1 相关符号及变量描述

5）总体优化目标函数。由于不合格订单与延期交货订单都将会使企业的产品成本增加，直接导致经济损失。因此，可以将不合格与延期交货订单的数量转换为成本损失金额，式(3)、式(5)可分别更新为：

这样可以将多目标优化问题转换成单目标优化问题，即采购过程中所产生的综合资金费用最低：

式(11)即为总体优化目标函数。C(k)、Wp(k)、Dp(k)、Cλ(k)为第k种分配方案的采购成本、不合格订单损失、延迟交货损失和修正函数值。C(min)、Wp(min)、Dp(min)、Cλ(min)为k种分配方案中四个目标函数的最小值。

2 改进混合蛙跳算法OSFLA

2.1 算法改进

混合蛙跳算法（SLFA）是通过模拟青蛙群体觅食过程而产生的基于群体的协同搜索方法，包括局部搜索和全局信息交换[7]，算法流程如图2所示。

图2 混合蛙跳算法流程图

初始种群的质量将直接影响到整个算法的求解过程，为了提高蛙跳算法中初始种群的质量，提出采用模糊聚类轮盘赌的方法降低某一类超级个体的数量，保证初始种群的多样性，初始种群数定义为Initial_Pop。

步骤1：依据个体的适应度值的大小对初始化种群进行分组，分组的个数即聚类数H，满足公式同时以随机率参数rH设定对应的初始聚类中心(f1,f2,…,fH)；

步骤2：对于群体中的每一个体按照个体与聚类中心之间相邻距离最近的原则分别对每一个个体进行聚类，如果，则

步骤3：生产新的聚类中心，即求解每个聚类样本个体的平均适应度值

步骤4：如果新的聚类中心与上一个聚类中心相同，则输出H个聚类，否则转步骤2。

2.2 OSFLA求解过程

订单分配问题是求解第i个订单是否由协作企业j获得，每个协作企业获得的每一类订单的订单量即为将每一种分配结果看成一个青蛙个体，将式(11)视为青蛙的适应度函数。运算步骤如下：

步骤1：初始化种群。随机生成一个由F只青蛙组成的群体，所有青蛙按照位置的适应度值降序排列，其中位置最好的青蛙用Fg表示。并采用聚类轮盘赌的方法对随机产生的解进行处理，构建符合条件的初始化种群。

步骤2：划分子群体。将F只青蛙（分配方案）分成x个子群体，每个子群体有y只青蛙。分配原则是：按照排序，1～x只青蛙依次进入1～x群体，第x+1只青蛙分入第1个群体，第x+2只青蛙分入第2个群体，循环往复，直至所有青蛙分配完成，每个子群体中位置最好的青蛙用Fb表示，位置最差的用Fw表示。

步骤3：执行局部搜索。首先对每个子群体执行局部搜索，即对子群体中最差适应度的青蛙个体进行更新操作，更新策略为：

S表示青蛙个体跳动的距离，Smax表示允许青蛙移动的最大距离。Rand(0,1)表示0～1之间的随机数。在更新过程中，如果新个体F′w的适应度优于Fw，则更新Fw，否则用Fg替代Fb，重新执行式(12)、式(13)。如果仍然不能产生新的可替代个体，则随机产生一个新个体来替代位置最差的青蛙个体。

步骤4：全局信息交换。当所有子群体完成预定迭代次数后，所有种群内的青蛙个体重新混合，再次排序分组，开始新一轮的局部搜索。

步骤5：输出最优结果。当满足停止条件时，运算结束，输出最优结果。

3 应用算例

为验证算法的有效性，本文以国内某建材装备集团完成国外定制的某批次大型水泥生产设备为例，进行实例分析与验证。假设集团下各子公司的订单统一分配，以集团生产计划为目标，承担生产任务的企业包括集团下属子公司和提供外协资源的外协公司，统一称为协作企业。各类参数如表2～表8所示。

表2 协作企业每类订单产品的价格（元/件）

表3 协作企业产品的不合格率（%）

表4 协作企业现有生产能力（天/件）

表5 协作企业最低订单量（件）

表6 协作企业的订单延期交货率（%）

表7 协作企业的距离（公里）

表8 每类订单的供货时间（天）、需求总量（件）及运输单价（元/件·公里）

为了使算法更具说明性，同时与传统蛙跳算法（SFLA）、遗传算法（GA）、蚁群算法（ACO）进行对比分析。

3.1 参数设定

设定需要采购的外协订单类别q=5，完成外协订单的协作企业j=1～6，其中协作企业j={1,2}为集团内部企业，即每个协作企业都可以完成这5类订单。设定且所有延期产品在7天内完成交货。权重值

1）OSFLA参数设定

设定初始种群个数为80，子群体个数为10，局部搜索迭代次数为50次，全局迭代次数为200次。

2）GA参数设定

设定初始种群个数为80，迭代次数为200次，变异概率为0.2，交叉概率为0.8，种群初始化方法选择轮盘赌选择法，选择概率为0.8。

3）ACO参数设定

设定迭代次数为200，蚂蚁种群数量为80，信息素挥发系数为0.5，信息素初始值为1，信息素增量为1。

3.2 运算结果

本文采用MATLAB（2013a）进行仿真实验，分别对四种算法进行了30次的重复运算，四种算法的仿真结果如表9所示。同时依据置信水平为5%的T方法，如公式(14)所示。

表9 仿真结果

表10 置信水平为5%的置信区间和T检验结果

图3 四种算法最佳适应度进化曲线

4 结束语

本文针对建材装备制造集团的生产特点和订单分配存在的问题，提出了一种内部企业优先分配策略，在基于产品经济参数的模型里，增加内部企业订单分配的修正函数。同时根据建材装备产品的特点，在最大化供货时间与生产负荷的条件下，通过订单分配寻求产品最优的价格与质量。最后采用改进的混合蛙跳算法进行求解，通过对比仿真实验证明，该算法除了计算时间有待进一步改进外，在搜寻全局最优解、收敛性以及稳定性上，具有很好的优势。

[1] 潘伟.基于供应中断风险的模糊多目标订单分配模型[J].管理科学学报,2015,18(3):45-51.

[2] K. L.Choy, W.B.Lee, Victor Lo. Development of a case based intelligent customer–supplier relationship management system [J]. Expert Systems with Applications,2002,23(3):281-297.

[3] Kenneth L. Mc Millian. The Impact of Order Allocation Decision on Supply Chain Bene fi ts Under Multiple Suppliers[J].Journal of the Institute of Industrial Engineers,2011(285):103-107.

[4] H. Haleh, A. Hamidi. A fuzzy MCDM model for allocating orders to suppliers in a supply chain under uncertainty over a multi-period time horizon[J].Expert Systems with Applications, 2011,38(8):9076-9083.

[5] 屠建飞,张远龙,方志梅.以供应商负荷产能相对均衡为目标的订单分配方法[J].机械设计与研究,2014,30(06):67-69+85.

[6] 罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题[J].通信学报,2009,30(7),130-135.

[7] 王松,孙振忠,郭建文,张智聪.基于混合蛙跳算法的复杂产品装配序列规划[J].计算机集成制造系统,2014,12:2991-2999.

The research of order allocation based on shuffled frog leaping algorithm in enterprise group

ZHOU Ling-yun1, GUO Shun-sheng2, LI Xi-xing2, WANG Lei2

TP399

A

1009-0134(2017)04-0100-05

2016-10-25

湖北省科技支撑计划项目（2015BAA063）；湖北省科技支撑计划项目（2014BAA032）；中央高校基本科研业务费专项资金资助（2016III024）

周凌云（1983 -），男，湖北枝江人，硕士研究生，研究方向为制造业信息化。