區(qū)域集群下板材訂單配置模型及算法研究

孫衛(wèi)紅，呂文新

(中國計量大學(xué) 機(jī)電工程學(xué)院，浙江 杭州 310018)

0 引言

為了適應(yīng)經(jīng)濟(jì)發(fā)展的大潮流，在某一地域范圍內(nèi)的中小型企業(yè)聯(lián)合協(xié)作，逐漸形成了以一個主導(dǎo)產(chǎn)業(yè)為核心的企業(yè)集群[1]。

板材資源作為集群企業(yè)常見的物理資源，批量大，庫存多，同類配套企業(yè)數(shù)量多，當(dāng)某一企業(yè)出現(xiàn)缺料情況時，集群的地理空間優(yōu)勢可以幫助企業(yè)需求方實現(xiàn)快速補(bǔ)充。然而在現(xiàn)實情況中，由于板材資源空間分布的不均衡、企業(yè)之間缺乏及時有效的信息交互，往往導(dǎo)致集群企業(yè)間未能進(jìn)行有效的協(xié)作和資源共享，無法發(fā)揮出集群的區(qū)域整體優(yōu)勢[2]。

利用網(wǎng)絡(luò)和云制造服務(wù)平臺，為集群企業(yè)的資源進(jìn)行聚合、共享、管理和調(diào)度提供了一個非常好的解決思路，但是由于平臺資源量巨大，需求與供應(yīng)之間是往往是多對多的匹配問題[3]，人工方法耗時耗力，需要通過調(diào)度算法實現(xiàn)平臺供需的智能匹配。

郝春亮等就固定的集群資源條件下，對內(nèi)部資源的快速獲取提出了四種調(diào)度結(jié)構(gòu)[4]；方伯芃等針對產(chǎn)業(yè)鏈內(nèi)部資源，對產(chǎn)業(yè)鏈生產(chǎn)與配送的協(xié)同調(diào)度優(yōu)化問題進(jìn)行建模，并通過啟發(fā)式尋優(yōu)求解得到最優(yōu)方案[5]；徐小峰等針對帶時間窗和資源約束的資源集成調(diào)配問題，構(gòu)造了網(wǎng)絡(luò)任與資源的集成調(diào)配模型，并采用遺傳算法對模型進(jìn)行求解[6]；陳友玲等從能力資源角度出發(fā)，根據(jù)不同需求訂單的效率值，為資源供應(yīng)方選擇對應(yīng)的需求方[7]；王靜等通過訂單拆分?jǐn)?shù)和訂單最小分解率兩個變量對云平臺下訂單生產(chǎn)計劃進(jìn)行調(diào)節(jié),并設(shè)計雙層編碼、運(yùn)用自適應(yīng)模擬退火遺傳算法對不同數(shù)據(jù)規(guī)模下的模型進(jìn)行求解[8]；顏波等提出了離散型帝國競爭算法對訂單調(diào)度流程進(jìn)行求解,以處理大批量復(fù)合訂單問題[9]；白小振等針對鋼材企業(yè)的板材資源提出了基于遺傳算法的無委托板坯合同優(yōu)化[10]；呼萬哲等設(shè)計了一種以最小化訂單余材為目標(biāo)的結(jié)合禁忌搜索和列生成技術(shù)的混合優(yōu)化算法[11]；王曉歡根據(jù)不同訂單的利潤水平提出了基于強(qiáng)化學(xué)習(xí)的企業(yè)訂單接受策略[12]。上述方法從產(chǎn)業(yè)優(yōu)化、減少庫存、獲取利潤等角度提出了多種解決資源調(diào)度的模型算法，旨在以資源供應(yīng)商的利益構(gòu)建訂單匹配模型，缺少從資源需求方的角度考慮資源的調(diào)度問題，而且在利用區(qū)域集群的地理優(yōu)勢上也相對欠缺。

本文中，將區(qū)域網(wǎng)絡(luò)化板材制造資源的共享與配置，分為服務(wù)平臺匹配和物流空間運(yùn)輸兩部分。以資源需求方的利益為主，著重考慮了訂單匹配成本和物流成本等因素，構(gòu)建區(qū)域板材資源共享平臺，解決集群企業(yè)板材資源調(diào)度問題，加深企業(yè)間的資源共享和網(wǎng)絡(luò)聯(lián)盟，降低產(chǎn)品制造成本。

1 集群資源特征與系統(tǒng)結(jié)構(gòu)控制

1.1 區(qū)域集群資源特征

區(qū)域集群的板材和企業(yè)通常具有以下幾個特征：

多樣性和確定性[13]：板材資源種類、規(guī)格、質(zhì)量標(biāo)準(zhǔn)等要素繁多，區(qū)域內(nèi)總資源數(shù)量龐大豐富。

產(chǎn)業(yè)一致：集群企業(yè)的產(chǎn)業(yè)關(guān)聯(lián)程度強(qiáng)，形成的核心產(chǎn)業(yè)簇群的資源基本相似，資源可獲得性高。

分布相對集中：各企業(yè)地理位置分布不同，但往往集中在某個區(qū)域內(nèi)，交通相對便利，有良好的合作基礎(chǔ)和區(qū)域優(yōu)勢。

1.2 系統(tǒng)配置結(jié)構(gòu)設(shè)計

企業(yè)板材資源需求與供應(yīng)匹配具體流程如圖1所示。板材資源的需求方將板材需求分解為子訂單上傳至共享平臺，根據(jù)子訂單中板材的種類、規(guī)格標(biāo)準(zhǔn)等物理要求進(jìn)行基本分組。板材供應(yīng)方對板材屬性按照模板參考分解后，做統(tǒng)一的規(guī)范指標(biāo)和描述，虛擬化處理后上傳至資源共享池，為接下來的匹配工作縮短匹配時間和提高匹配精度，讓其具有更好的針對性和適應(yīng)性。然后根據(jù)調(diào)度模型匹配出具有合適的供應(yīng)商，最后完成子訂單的配送。

圖1 板材訂單匹配流程

2 匹配要求及約束模型

對于集群企業(yè)來說，板材的采購與供應(yīng)基本上已經(jīng)建立起了長期互信的伙伴關(guān)系，這也是集群發(fā)展的重要基礎(chǔ)。因此，板材采購的成本控制成為了影響需求方企業(yè)經(jīng)濟(jì)利益的一個重要指標(biāo)。降低采購成本，是需求方企業(yè)在采購過程中最重要的考慮因素之一。

平臺上有多個板材資源申請請求，每個請求可以分解為多個子訂單。各子訂單在板材規(guī)格、型號等屬性方面約束不再討論。根據(jù)客戶要求，本文建立了一個以資源需求企業(yè)采購總費用最低為目標(biāo)的優(yōu)化模型，來指導(dǎo)平臺將子訂單分配給合適的集群供應(yīng)商。

2.1 符號定義

模型中參數(shù)或變量符號定義：

(1)訂單表示

i為訂單分解后的子訂單序號，共Qm個；

ωi為子訂單i所需要的訂單量；

Porder為訂單的預(yù)算成本，包括所有訂單的采購成本與運(yùn)輸成本。

(2)供應(yīng)商表示

j為平臺上針對子訂單i的供應(yīng)商序號，共Ni個；

pij為企業(yè)編號是j的供應(yīng)商對i子訂單提出的貨物單價；

dij為子訂單i的需求方與供應(yīng)商的距離；

ωij為供應(yīng)商的庫存量；

tcon為該區(qū)域每單位訂單量在單位運(yùn)距下的運(yùn)輸成本。

(3)決策變量

Zij為0-1變量，若子訂單分配給供應(yīng)商j，則為1，否則為0。

2.2 資源配置目標(biāo)函數(shù)

分解后的子訂單費用可以分為兩部分，分別是用戶購買物料資源的花費成本和物料的物流運(yùn)輸成本。

以子訂單分配的供應(yīng)商給出的單位參考價格為標(biāo)準(zhǔn)，計算出每個子訂單對應(yīng)板材需求量的材料采購成本。訂單用于購買材料的花費為C1所有子訂單采購成本之和，其表達(dá)式如下：

由于區(qū)域企業(yè)集群各企業(yè)間具有良好的交通優(yōu)勢，在同等情況下，應(yīng)該優(yōu)先考慮距離板材需求方更近的供應(yīng)商，同時也可以降低運(yùn)輸成本。各個子訂單材料物流運(yùn)輸總費用之和C2可以表示為:

綜上所述，平臺上一個訂單總費用之和C可以表示為:

2.3 約束條件

根據(jù)模型，可以建立模型的約束條件如下:

dij≤s,i∈Om,j∈Ni

(1)

(2)

ωi≤ωij,i∈Om,j∈Ni

(3)

C≤Porder

(4)

dij>0

(5)

其中：約束(1)為距離約束，表示物料需求企業(yè)和物料供應(yīng)企業(yè)之間具有距離限制，要求物料需求企業(yè)與物料供應(yīng)企業(yè)在同一個企業(yè)集群中，確保兩者在可配送范圍內(nèi)。s為該物料需求企業(yè)距離物流供應(yīng)企業(yè)的距離上限；約束(2)為供應(yīng)商選擇約束，確保訂單i提出的需求只能由一個企業(yè)供應(yīng)商供應(yīng)，避免多家物料供應(yīng)企業(yè)重復(fù)接同一子訂單；約束(3)為供應(yīng)庫存約束，要求物料供應(yīng)企業(yè)的物料庫存可以滿足訂單i的物料需求量，ωij為物料供應(yīng)企業(yè)的物料庫存；約束(4)為成本約束，要求訂單分配后的總成本在用戶給出的成本范圍之內(nèi)；約束(5)為自然約束，避免不符合常規(guī)的約束。

3 IA-PSO混合算法實現(xiàn)訂單配置

PSO算法具有結(jié)構(gòu)簡單、運(yùn)行速度快的優(yōu)點，但是該算法卻也往往有搜索精度不高，容易陷入局部最優(yōu)，出現(xiàn)早熟收斂等缺陷[14]。如果在進(jìn)化探索階段，能夠保持其種群的多樣性，就能大大避免算法出現(xiàn)早熟收斂的現(xiàn)象。

本文提出的IA-PSO算法，將人工免疫算法與粒子群優(yōu)化算法相結(jié)合，在保留了交叉、變異等固有遺傳操作的基礎(chǔ)上，借助免疫記憶特性和克隆選擇等粒子群算法所欠缺的機(jī)理，根據(jù)抗體適應(yīng)度將抗體群劃分為支配解與非支配解，對其進(jìn)行促進(jìn)或抑制作用。這樣不僅提高了算法的全局搜索能力，達(dá)到避免早熟收斂的目的，而且算法對個體的評價也更加全面，個體選擇方式也更為合理，保證了解的多樣性。其算法流程圖如圖2所示。

圖2 算法流程圖

3.1 基因編碼

在可行解空間隨機(jī)產(chǎn)生初始數(shù)量為的抗體群。如圖3所示，免疫系統(tǒng)是由基因長度為M的N個抗體組成，抗體基因編碼需要考慮每一位對應(yīng)基因的順序。設(shè)抗體ai為一個可行的訂單分配方案，ai=[ai1,ai2,…,ain],其中，i∈{1,2,…,N}是訂單編號，aij∈{1,2,…,n}表示第i個訂單中的子訂單j所分配的供應(yīng)商企業(yè)編號。例如一個訂單分配的可行解為[2,7,15,21,19]，它代表該訂單分解后的子訂單1、2、3、4、5分別分配到編號為2,7,15,21,19的企業(yè)供應(yīng)商上。

圖3 抗體基因表示

3.2 交叉操作

由于單點交叉交換基因量大，容易破壞優(yōu)秀個體，因此交叉操作采用雙點交叉法，操作方法如圖4所示，結(jié)合來自父代交配種群中的信息，隨機(jī)確定兩個不同的交叉位置，將切點中間位置信息作為交換對象，產(chǎn)生新的個體。

圖4 雙切點交叉操作

3.3 免疫克隆操作

由于免疫算法在抑制高濃度個體時，與抗原親和度最高的個體也會受到抑制，這樣很可能會導(dǎo)致已經(jīng)求得的最優(yōu)解丟失。為了防止這種情況發(fā)生，采用精英保留策略，先將與抗原親和度按降序排列取前N/2個體存入記憶庫，剩余群體按照期望繁殖概率選擇優(yōu)秀個體存入記憶庫。

為了在剩余抗體群中選擇出更優(yōu)的個體，本文提出了一種懲罰制度，通過比較適應(yīng)值結(jié)果與用戶給出的訂單預(yù)期成本，將剩余抗體種群劃分為支配解和非支配解。當(dāng)訂單分配后的方案總費用高于用戶預(yù)期，定義其抗體種群為非支配解，給予抗體抗原親和度值一個費用違反懲罰。

設(shè)計非支配解其抗體與抗原之間的親和力函數(shù)Av如下：

其中，F(xiàn)(xi)為該抗體得到的訂單分配方案所生成的總費用，xi為抗體對應(yīng)基因位上每個子訂單分配給供應(yīng)商的解。

定義剩余抗體被選擇的概率可以表示為:

其中，α為常數(shù)。根據(jù)上式可以得到，當(dāng)費用過高的時候，抗體被選擇的概率會降低，抗體上每個基因位對應(yīng)的解即為每個訂單對應(yīng)分配企業(yè)的編號，從而獲取每個訂單解。這保證了高適應(yīng)度個體的繁殖，同時又確保了個體多樣性。

4 實例應(yīng)用與結(jié)果

為驗證模型和算法的有效性，以浙江某木制玩具企業(yè)集群為背景，對模型進(jìn)行試驗與分析。構(gòu)建一個用于管理企業(yè)板材資源的信息平臺，選取部分企業(yè)用戶實際訂單需求與企業(yè)愿意承擔(dān)的訂單預(yù)期成本作為參考，通過信息平臺發(fā)布為板材需求訂單，分解為子訂單后上傳至信息管理平臺，供應(yīng)商企業(yè)通過上傳自身板材資源庫存信息將區(qū)域分散的板材資源進(jìn)行整合,經(jīng)過匹配后為用戶的不同子訂單選擇出價格最低的供應(yīng)商企業(yè)作為參考。

表1 申請資源發(fā)布訂單

表2 訂單分解

平臺上有六個企業(yè)用戶發(fā)布了訂單與訂單預(yù)期成本，如表1所示。每個訂單經(jīng)過分解后，對應(yīng)為如表2所示的相應(yīng)子訂單。平臺上對應(yīng)的供應(yīng)商及其提供的板材資源如表3所示。

表3 平臺板材資源供應(yīng)

表4 子訂單分配方案

根據(jù)調(diào)度模型及算法，使用MATLAB對訂單分配模型進(jìn)行編程求解。為了測試算法的實用性，在給出相同實驗條件下，采用粒子群算法作為對比實驗。

IA-PSO算法初始化參數(shù)如下：迭代次數(shù)為100，種群規(guī)模為50，記憶庫容量為10，交叉概率為0.5，變異概率為0.4，多樣性評價參數(shù)設(shè)為0.95，抗體親和度閾值取0.7。經(jīng)過算法匹配，各訂單的分配方案如表4所示。以編號為1的訂單為例，訂單1經(jīng)過處理后被分解為6個子訂單，通過運(yùn)算配置，子訂單依次被分配給編號為23、4、16、7、6、2的供應(yīng)商企業(yè)，并給出了每一個子訂單的成本費用，訂單1的總費用為109900元，低于用戶給出的訂單預(yù)期成本，說明該算法對于集群內(nèi)訂單的分配具有一定指導(dǎo)意義。

同時，IA-PSO混合算法與傳統(tǒng)PSO算法相比較，算法最優(yōu)解的變化曲線如圖5所示，傳統(tǒng)PSO算法在迭代50次左右陷入了局部最優(yōu)，并最終收斂于最優(yōu)解582960，IA-PSO混合算法收斂于其最優(yōu)值554125，證明了IA-PSO算法明顯具有更好的全局搜索能力，改進(jìn)后算法的費用節(jié)省了全部訂單費用的5.2%。

圖6展示了板材訂單資源的供應(yīng)方與需求方在集群地理位置上空間分布。排除庫存量不足的供應(yīng)商，訂單的分配幾乎均選擇了距離用戶的較近范圍內(nèi)的供應(yīng)商，不但縮短了板材運(yùn)送時間，同時也節(jié)省了相關(guān)的物流運(yùn)輸費用。

圖5 算法最優(yōu)解變化曲線

圖6 訂單分配企業(yè)地理位置示意圖

5 結(jié)論

針對區(qū)域企業(yè)集群中板材資源特點，綜合考慮區(qū)域集群中企業(yè)用戶資源庫存和區(qū)域物流的空間等因素，著重參考了集群內(nèi)企業(yè)分布、訂單分配總費用最小化等需求，構(gòu)建了區(qū)域內(nèi)企業(yè)集群板材訂單分配數(shù)學(xué)模型，并提出IA-PSO混合算法對其進(jìn)行求解計算，使整個訂單分配收斂于全局最優(yōu)解。最后以某木玩集群板材訂單匹配為例進(jìn)行試驗驗證，結(jié)果證明該算法能夠得到更優(yōu)的訂單分配方案，有效解決了區(qū)域集群內(nèi)板材訂單的分配問題。