基于多階段評價(jià)選擇遺傳算法的材料訂購和運(yùn)輸最優(yōu)化問題研究

王子怡

（西南林業(yè)大學(xué)大數(shù)據(jù)與智能工程學(xué)院，云南 昆明 650051）

1 研究背景

本研究中的某建筑企業(yè)所用原材料主要是木質(zhì)纖維和其他植物素纖維材料，總體可分為A、B、C 3種類型。該企業(yè)計(jì)劃每年按48周安排生產(chǎn)，在生產(chǎn)之前，還需要提前制定24周的原材料訂購和轉(zhuǎn)運(yùn)計(jì)劃。因此，需要根據(jù)產(chǎn)能要求確定原材料的供應(yīng)商和相應(yīng)每周原材料的訂購數(shù)目，并在最后委托合適的第三方物流公司轉(zhuǎn)運(yùn)生產(chǎn)的原材料。該企業(yè)每周的產(chǎn)能為2.82萬m3，每立方米產(chǎn)品需要消耗A類、B類或C類原材料。同時(shí)供應(yīng)商供貨量可能多余或少于訂貨量，所以企業(yè)需要保證庫存里有不少于2周生產(chǎn)需求的原材料數(shù)目[1]。

2 基于TOPSIS的供應(yīng)商重要性評價(jià)模型

2.1 供應(yīng)商重要性評價(jià)體系

先衡量供應(yīng)商對生產(chǎn)企業(yè)重要性的評價(jià)指標(biāo)并給出具體定義，然后構(gòu)建出供應(yīng)商重要性衡量體系，具體如下。

失信次數(shù)ηi：供應(yīng)商未按量供貨（包括不供貨的情況）的次數(shù)。

失信率α：供應(yīng)商未能按量供貨的次數(shù)占企業(yè)向該供應(yīng)商訂購次數(shù)的比例。公式為α=ηi/ηn，其中，ηi為供應(yīng)商未能按量供貨的次數(shù)（包含未供貨的次數(shù)），ηn為生產(chǎn)企業(yè)向該供應(yīng)商訂貨的次數(shù)。

供貨次數(shù)ω：各供應(yīng)商240周中提供貨物的次數(shù)。

供貨次率ψ：各供應(yīng)商240周中提供貨物的次數(shù)占240周的比例。公式為ψ=ω/N，其中N取值為240。

單周最大供貨量β+：各供應(yīng)商240周中供貨量最大的1周的供貨數(shù)量。該指標(biāo)可以有效衡量供應(yīng)商的最大供貨能力，供應(yīng)商的重要性很大程度體現(xiàn)在供應(yīng)商的供貨能力，從數(shù)據(jù)中可以得到各供應(yīng)商5年來的最佳供貨數(shù)據(jù)，從而可以分析該供應(yīng)商的供應(yīng)能力，有助于生產(chǎn)企業(yè)進(jìn)行決策。

總供貨量β：供應(yīng)商240周總供貨量。為了衡量供應(yīng)商的供貨實(shí)力，對供應(yīng)商5年來供貨總量的評定很有必要，供應(yīng)商5年來能提供的貨物數(shù)量在一定程度上反映了這家供應(yīng)商的綜合實(shí)力，這可以作為企業(yè)向供貨商訂購貨物的依據(jù)，供貨實(shí)力強(qiáng)的供應(yīng)商，企業(yè)會優(yōu)先考慮大額訂單。

平均供貨量β-：供應(yīng)商平均每次供貨的貨物數(shù)量。公式為β-=εi/ηn，其中，εi為供應(yīng)商5年總共提供的貨物，ηn為5年來供應(yīng)商向生產(chǎn)企業(yè)供貨的次數(shù)。在供應(yīng)商供貨能力的評定上，需要比較均衡地了解每家供應(yīng)商的供貨能力，平均值是一組數(shù)據(jù)中最有代表性的統(tǒng)計(jì)量，其能較好地衡量出每家供應(yīng)商的平均供貨水平。

供貨率ε：供應(yīng)商提供的貨物占企業(yè)訂購貨物的比例。公式為ε=βi/βn，其中，βi為供應(yīng)商提供的貨物數(shù)量，βn為企業(yè)訂購的貨物。衡量供應(yīng)商供應(yīng)能力的另一重要指標(biāo)是供貨過程中能提供的數(shù)量。

供貨量標(biāo)準(zhǔn)差γ：反映供應(yīng)商供貨數(shù)據(jù)的離散程度，即240周總體供貨量與平均供貨量離差平方的算術(shù)平均數(shù)的平方根，公式為其中，βi為供應(yīng)商每周提供的貨物量，為240周平均每周提供的貨物量?？紤]到供應(yīng)商每次供貨量數(shù)值變化不確定，故需采用標(biāo)準(zhǔn)差對供貨量進(jìn)行分析，為了觀察供貨數(shù)據(jù)的波動性，衡量供應(yīng)商的供貨穩(wěn)定性，采用該指標(biāo)衡量供應(yīng)商供貨能力的波動性。

以上9個評價(jià)指標(biāo)，可層次構(gòu)成供應(yīng)商重要性評價(jià)體系。

2.2 TOPSIS分析過程

TOPSⅠS（Technique for order preference by similarity to ideal solution）法是用于研究與理想方案相似性的順序選優(yōu)技術(shù)?？梢岳斫鉃?，數(shù)據(jù)越大越優(yōu)，數(shù)據(jù)越小越劣，結(jié)合數(shù)據(jù)間的大小，計(jì)算正負(fù)理想解與評價(jià)對象的距離以及綜合得分，最后得出優(yōu)劣方案的排序[2]。

TOPSⅠS分析通常分為以下幾步：①特征數(shù)據(jù)屬性正向化處理；②正向化矩陣標(biāo)準(zhǔn)化得到標(biāo)準(zhǔn)矩陣M③找出最優(yōu)矩陣向量M+和最劣矩陣向量M-；④分別計(jì)算評價(jià)對象與正理想解距離D+或負(fù)理想解距離D-；⑤計(jì)算各評價(jià)對象與最優(yōu)方案的相對近似度C，進(jìn)行排序即可得到結(jié)果。由TOPSⅠS方法可知，對供應(yīng)商的失信率、供貨率、供貨量標(biāo)準(zhǔn)差、平均供貨量、總體供貨量等評價(jià)指標(biāo)進(jìn)行正向化處理和標(biāo)準(zhǔn)化處理后，建立TOPSⅠS模型。

2.3 數(shù)據(jù)預(yù)處理

對所有特征數(shù)據(jù)進(jìn)行正向化處理即把所有指標(biāo)轉(zhuǎn)化為極大型，所有的數(shù)字越大，評分越高。對處理后的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，在多指標(biāo)評價(jià)體系中，由于各評價(jià)指標(biāo)的性質(zhì)不同，通常具有不同的量綱，所以在數(shù)據(jù)樣本充足的情況下，往往直接使用標(biāo)準(zhǔn)化對數(shù)據(jù)進(jìn)行無量綱預(yù)處理，便于不同指標(biāo)之間進(jìn)行加權(quán)和求和。

綜上可知，各個評價(jià)指標(biāo)最終綜合表現(xiàn)為與正理想解的相對近似度。相對近似度越大，供應(yīng)商越重要。該相對近似度大小的確定需要根據(jù)9個指標(biāo)的數(shù)據(jù)進(jìn)行求解，求解過程及結(jié)果在下面模型求解中給出。

2.4 模型的求解

假設(shè)有n個待評價(jià)對象，m個評價(jià)指標(biāo)的標(biāo)準(zhǔn)矩陣為M。取最優(yōu)矩陣向量M+，取最劣矩陣向量M-，然后計(jì)算評價(jià)對象與正理想解的距離、評價(jià)對象與負(fù)理想解的距離，即可計(jì)算各評價(jià)對象與最優(yōu)方案的相對近似度C。

計(jì)算得到綜合排名前27的供應(yīng)商如下：201、S140、S229、S361、S108、S151、S340、S282、S139、S275、S329、S308、S330、S395、S131、S356、S268、S306、S348、S194、S126、S352、S143、S307、S247、S284、S374。

3 遺傳算法模型

3.1 供應(yīng)商最少

該問題要求在盡可能滿足生產(chǎn)需求的情況下選擇最少的供應(yīng)商數(shù)量。根據(jù)供應(yīng)商重要性排名，綜合考慮各供應(yīng)商的供貨能力和供貨穩(wěn)定性，考慮采用各供應(yīng)商平均供貨量來表示各供應(yīng)商每周的供貨能力。這里提出一個新的數(shù)量名詞，出產(chǎn)量φ，即供應(yīng)商提供的貨物能為生產(chǎn)企業(yè)帶來的產(chǎn)能，然后在50家最重要的供應(yīng)商中按順序累加其每周出產(chǎn)量直到滿足生產(chǎn)需求，求出最少供應(yīng)商數(shù)，即計(jì)算出的最少供應(yīng)商數(shù)n為22。

3.2 最經(jīng)濟(jì)的訂購方案

模型的建立。該問題要求制定未來24周每周最經(jīng)濟(jì)的原材料訂購方案，實(shí)際上就是要從上文中的50家供應(yīng)商中組合出最經(jīng)濟(jì)的方案。選擇使用遺傳算法進(jìn)行迭代優(yōu)化選擇，遺傳算法是根據(jù)基因變異的思想進(jìn)行隨機(jī)優(yōu)化的搜索方法，結(jié)合自適應(yīng)的概率優(yōu)化算法，能夠在全局范圍內(nèi)尋找最優(yōu)解，滿足題目要求，公式如下：

式（1）（2）中：xi為是否向第i個企業(yè)訂貨，xi=0或1；mi為第i個供應(yīng)商的供貨量；ri為該企業(yè)所提供材料的系數(shù)。

這是個0-1背包問題，很難用傳統(tǒng)的線性規(guī)劃求解，故本題設(shè)計(jì)用遺傳算法來解決[3]。

首先，確定種群數(shù)量，給染色體編碼，隨機(jī)生產(chǎn)第一代種群；其次，確定個體評價(jià)方案，判斷是否滿足停止條件，若是則停止，輸出最優(yōu)解，否則繼續(xù)進(jìn)行操作，通常第一代種群不會滿足停止條件；最后，對種群進(jìn)行選擇、交叉、變異操作，得到下一代種群，再進(jìn)行評價(jià)，反復(fù)循環(huán)，直到滿足生產(chǎn)需求。

其中遺傳算法的主要流程如圖1所示。

根據(jù)圖1的算法流程，首先對種群進(jìn)行編碼，然后初始化種群并進(jìn)行多階段評價(jià)與選擇，在一般的遺傳算法中，通常只有一個評價(jià)和選擇階段。本文需要在滿足生產(chǎn)的條件下，還要求價(jià)格最低，所以首先以供貨量為評價(jià)指標(biāo)來評價(jià)個體的適應(yīng)性。在選擇過程中，按供貨量從大到小進(jìn)行排序，淘汰后50%的個體。而第二階段的評價(jià)與選擇和上述過程一致，適應(yīng)性指標(biāo)換成了總價(jià)。選擇過程采用升序方式，選擇前50%的個體保留下來。

圖1 遺傳算法的流程

做完多階段評價(jià)與選擇后則進(jìn)行交叉與變異和補(bǔ)充種群的操作。本算法在交叉和變異階段進(jìn)行了種群個體數(shù)量的補(bǔ)充。在生物界，交叉出現(xiàn)的情況比變異多，故在交叉階段補(bǔ)充70%的個體，在變異階段補(bǔ)充30%的個體。

最后是綜合評價(jià)階段。在迭代完成后，將所有個體按照供貨量升序、價(jià)格降序聯(lián)合排序，找出最接近于2.82萬的個體作為輸出結(jié)果。

根據(jù)以上算法得出原材料訂購方案，如圖2所示。

圖2 原材料訂購方案

圖2中展示了最優(yōu)解、次優(yōu)解和二次優(yōu)解的訂貨方案。例如最優(yōu)解中首先選擇了編號為S201的供應(yīng)商，它的供貨量為2 982.178 571。同時(shí)，分析本文將最優(yōu)解、次優(yōu)解和二次優(yōu)解三者之間的差異可知，最優(yōu)解與次優(yōu)解有20個不同的供應(yīng)商。

4 模型評價(jià)與推廣

4.1 模型優(yōu)點(diǎn)

采用遺傳算法的優(yōu)點(diǎn)如下：①快速隨機(jī)的搜索能力；②搜索從群體出發(fā)，具有潛在的并行性，可以同時(shí)進(jìn)行多個個體的比較；③搜索使用評價(jià)函數(shù)啟發(fā)，過程簡單。

采用Topsis綜合分析方法的優(yōu)點(diǎn)如下：①不需要目標(biāo)函數(shù)，是無人監(jiān)督的分析方法；②對于數(shù)據(jù)分布及樣本量、指標(biāo)多少無嚴(yán)格限制，可以既適用于小樣本資料，也適用于多評價(jià)單元、多指標(biāo)的大系統(tǒng)。

4.2 模型缺點(diǎn)

采用遺傳算法的缺點(diǎn)如下：①遺傳算法的編程實(shí)現(xiàn)比較復(fù)雜，首先需要對問題進(jìn)行編碼，找到最優(yōu)解之后還需要對問題進(jìn)行解碼；②另外3個算子的實(shí)現(xiàn)也有許多參數(shù)，如交叉率和變異率，并且這些參數(shù)的選擇嚴(yán)重影響解的品質(zhì)，而目前這些參數(shù)的選擇大部分是依靠經(jīng)驗(yàn)。

采用Topsis綜合分析方法的缺點(diǎn)如下：①求解規(guī)范決策矩陣比較繁雜；②對于正理想解和負(fù)理想解的求解過程比較困難；③不確定指標(biāo)的選取個數(shù)為多少，個數(shù)確定才能很好地去刻畫指標(biāo)的影響力度。