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

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

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

0 引言

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

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

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

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

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

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

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

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

多樣性和確定性[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è)簇群的資源基本相似，資源可獲得性高。

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

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

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

圖1 板材訂單匹配流程

2 匹配要求及約束模型

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

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

2.1 符號(hào)定義

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

(1)訂單表示

i為訂單分解后的子訂單序號(hào)，共Qm個(gè)；

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

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

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

j為平臺(tái)上針對(duì)子訂單i的供應(yīng)商序號(hào)，共Ni個(gè)；

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

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ù)

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

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

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

綜上所述，平臺(tái)上一個(gè)訂單總費(fèi)用之和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è)在同一個(gè)企業(yè)集群中，確保兩者在可配送范圍內(nèi)。s為該物料需求企業(yè)距離物流供應(yīng)企業(yè)的距離上限；約束(2)為供應(yīng)商選擇約束，確保訂單i提出的需求只能由一個(gè)企業(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混合算法實(shí)現(xiàn)訂單配置

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

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

圖2 算法流程圖

3.1 基因編碼

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

圖3 抗體基因表示

3.2 交叉操作

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

圖4 雙切點(diǎn)交叉操作

3.3 免疫克隆操作

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

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

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

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

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

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

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

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

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

表2 訂單分解

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

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

表4 子訂單分配方案

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

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

同時(shí)，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)后算法的費(fèi)用節(jié)省了全部訂單費(fèi)用的5.2%。

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

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

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

5 結(jié)論

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