基于混合蛙跳算法的企業集團訂單分配研究

周凌云，郭順生，李西興，王 磊

（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 -），男，湖北枝江人，碩士研究生，研究方向為制造業信息化。