互聯(lián)網(wǎng)家裝服務(wù)中的供應(yīng)鏈優(yōu)化模型

張 巍

(上海交通大學(xué) 安泰經(jīng)濟(jì)與管理學(xué)院 管理科學(xué)與工程系，上海 200030)

1 文獻(xiàn)綜述

庫(kù)存路徑問(wèn)題研究的是考慮庫(kù)存和運(yùn)輸?shù)南嗷ビ绊懀诟鞣N約束條件的限制下確定補(bǔ)貨策略和配送策略，使得庫(kù)存和運(yùn)輸?shù)目偝杀咀畹蚚1]。庫(kù)存路徑問(wèn)題由于整合了庫(kù)存管理和運(yùn)輸問(wèn)題，是車輛路由問(wèn)題的進(jìn)一步延伸，更具有研究?jī)r(jià)值。庫(kù)存路徑問(wèn)題通常不考慮貨物的生產(chǎn)制造過(guò)程，主要同時(shí)解決三個(gè)關(guān)鍵問(wèn)題：何時(shí)向客戶送貨、車輛向客戶送多少貨物以及車輛的行駛路徑規(guī)劃[2]。

設(shè)計(jì)啟發(fā)式算法是目前學(xué)者處理庫(kù)存路徑問(wèn)題的主流研究方向。利用已有的車輛路由問(wèn)題、經(jīng)濟(jì)批量訂貨模型等研究基礎(chǔ)，設(shè)計(jì)兩階段啟發(fā)式算法尋找近似解在研究初期被廣泛使用。兩階段法的基本思路是先確定車輛向各個(gè)客戶配送貨物的數(shù)量，再利用已有的車輛路由問(wèn)題成果確定車輛行駛路徑；另外，也可以先確定車輛行駛路線，再確定給客戶的配送量。代穎等[3]考慮了一種多周期的定位庫(kù)存路徑優(yōu)化問(wèn)題模型，并設(shè)計(jì)先定位分配后設(shè)計(jì)路徑的兩階段啟發(fā)式算法進(jìn)行求解。Campbell和Savelsbergh[4-5]提出包含時(shí)間窗的庫(kù)存路徑優(yōu)化問(wèn)題，并利用先客戶分區(qū)后確定線路的啟發(fā)式算法進(jìn)行求解。

由于庫(kù)存路徑問(wèn)題各規(guī)劃期內(nèi)的庫(kù)存變化具有馬爾科夫性，部分文獻(xiàn)提出利用馬爾科夫決策過(guò)程解決庫(kù)存路徑問(wèn)題。Kelywegf等[6-7]建立了馬爾科夫決策過(guò)程離散模型用于研究直接送貨策略，但計(jì)算過(guò)程存在求解困難的問(wèn)題。Adelman[8]引入松弛函數(shù)對(duì)類似離散模型進(jìn)行研究。此外，Hvattum等[9]采用決策樹(shù)方式對(duì)庫(kù)存路徑問(wèn)題進(jìn)行了近似求解。

利用計(jì)算機(jī)極強(qiáng)的處理能力，設(shè)計(jì)元啟發(fā)式算法求解的文獻(xiàn)近年來(lái)陸續(xù)增加。Liu和Lin[10]在將庫(kù)存路徑問(wèn)題使用兩階段法拆分后，利用禁忌搜索算法和模擬退火算法對(duì)解進(jìn)行進(jìn)一步改進(jìn)。呂飛等[11]針對(duì)帶軟時(shí)間窗的選址庫(kù)存路徑備件物流問(wèn)題，設(shè)計(jì)了基于禁忌搜索算法和C-W節(jié)約算法的混合算法進(jìn)行求解。Huang等[12]使用改進(jìn)后的蟻群算法，對(duì)需求不確定下的多產(chǎn)品補(bǔ)貨調(diào)度問(wèn)題進(jìn)行求解，獲取隨機(jī)性條件下的配送和補(bǔ)貨數(shù)量方案。Moin等[13]設(shè)計(jì)了一個(gè)先分配貨物后設(shè)計(jì)行進(jìn)線路的兩階段遺傳算法，引入新的交叉與變異算子和新染色體標(biāo)識(shí)，成功對(duì)多周期多產(chǎn)品有裝載容量限制的艦隊(duì)配送網(wǎng)絡(luò)優(yōu)化問(wèn)題進(jìn)行了求解。

由于具體行業(yè)中對(duì)搭建供應(yīng)鏈模型存在多種實(shí)用性或技術(shù)可行性限制，針對(duì)具體行業(yè)的物流系統(tǒng)或供應(yīng)鏈庫(kù)存路由問(wèn)題的相關(guān)文獻(xiàn)相對(duì)較少，主要集中在原油運(yùn)輸供應(yīng)[14]、煤炭開(kāi)發(fā)運(yùn)輸[15-16]、天然氣海路運(yùn)輸[17]、售后備件物流[11,18]、水泥生產(chǎn)運(yùn)輸[19]、家畜運(yùn)輸屠宰[20]等領(lǐng)域。

2 問(wèn)題描述及模型

2.1 問(wèn)題描述

基于前述業(yè)務(wù)流程，我們可以構(gòu)造一個(gè)以單個(gè)倉(cāng)庫(kù)為決策中心的供應(yīng)鏈優(yōu)化問(wèn)題，問(wèn)題描述如下：

整個(gè)供應(yīng)鏈模型由一個(gè)倉(cāng)庫(kù)、多個(gè)一級(jí)供應(yīng)商和多個(gè)客戶組成。供應(yīng)鏈的總運(yùn)營(yíng)成本包括建材的訂貨成本、庫(kù)存成本以及運(yùn)輸成本。訂貨成本在倉(cāng)庫(kù)向供應(yīng)商發(fā)出訂單時(shí)產(chǎn)生，訂貨成本與訂單的訂貨數(shù)量無(wú)關(guān)；將建材存儲(chǔ)于倉(cāng)庫(kù)中會(huì)產(chǎn)生庫(kù)存成本，當(dāng)建材配送至客戶裝修現(xiàn)場(chǎng)后不再產(chǎn)生庫(kù)存成本；卡車配送建材時(shí)會(huì)產(chǎn)生運(yùn)輸成本，運(yùn)輸成本取決于卡車行駛路徑。

倉(cāng)庫(kù)作為決策中心，在規(guī)劃周期內(nèi)的每個(gè)規(guī)劃日需要確定是否向一級(jí)供應(yīng)商發(fā)出訂單(若發(fā)出訂單則需要確定訂貨數(shù)量)、是否向客戶配送建材(若配送則需要確定各建材的配送數(shù)量)、卡車配送建材的類別數(shù)量以及卡車的行駛路徑。倉(cāng)庫(kù)的決策目標(biāo)是使前述的總運(yùn)營(yíng)成本最低。

整個(gè)優(yōu)化過(guò)程周期跨度為T。下達(dá)訂單的客戶共有N位，客戶對(duì)建材的需求互不相同。裝修過(guò)程涉及建材M類，分別對(duì)應(yīng)M個(gè)一級(jí)供應(yīng)商。建材m有其固定的型號(hào)規(guī)格，體積為Vm。倉(cāng)庫(kù)配送過(guò)程可供使用的卡車總數(shù)為L(zhǎng)，其規(guī)格相同。

客戶n在簽訂合同后，裝修期間每日所需要的建材數(shù)量是確定的，客戶n在時(shí)間t所需要的建材m數(shù)量為dmnt，需求發(fā)生在每個(gè)規(guī)劃期的開(kāi)始。倉(cāng)庫(kù)需要將建材及時(shí)送到客戶處，整個(gè)規(guī)劃過(guò)程中不允許缺貨。裝修現(xiàn)場(chǎng)可容納的建材總量有限，客戶n所能容納的最大建材體積為Cn?？蛻鬾初始建材庫(kù)存為invmn0=0。

各個(gè)供應(yīng)商負(fù)責(zé)提供相應(yīng)的建材。建材m在倉(cāng)庫(kù)中的安全庫(kù)存為Sm，當(dāng)建材在倉(cāng)庫(kù)中的存量即將低于安全庫(kù)存時(shí)，倉(cāng)庫(kù)需要向相應(yīng)供應(yīng)商發(fā)出訂單，整個(gè)規(guī)劃周期內(nèi)任意建材倉(cāng)庫(kù)儲(chǔ)量不得低于其安全庫(kù)存。供應(yīng)商對(duì)倉(cāng)庫(kù)訂單的訂貨量有要求，建材m單次訂單所需要的最低訂貨量為Qminm。供應(yīng)商m收到訂單后到建材m運(yùn)至倉(cāng)庫(kù)存在前置時(shí)間lm。倉(cāng)庫(kù)每次向供應(yīng)商下達(dá)訂單的訂貨成本為om。

將建材m置于倉(cāng)庫(kù)中會(huì)產(chǎn)生庫(kù)存成本，每單位建材m在一個(gè)規(guī)劃間隔內(nèi)產(chǎn)生的庫(kù)存成本為hm，倉(cāng)庫(kù)中建材m的初始庫(kù)存為invm00。

卡車在運(yùn)輸過(guò)程中有裝載容量限制，能裝載的最大建材體積為Ctmax?？ㄜ嚹軌蜓b載多位客戶的建材，逐個(gè)送到客戶施工現(xiàn)場(chǎng)?？ㄜ噺牡攸c(diǎn)i運(yùn)至地點(diǎn)j(i,j為0,1,…,n，其中0代表倉(cāng)庫(kù))所產(chǎn)生的運(yùn)輸成本為cij。建材在每個(gè)規(guī)劃期的開(kāi)始時(shí)送至客戶處，沒(méi)有運(yùn)輸時(shí)間。

本研究描述的供應(yīng)鏈優(yōu)化問(wèn)題與通常庫(kù)存路徑問(wèn)題的區(qū)別在于考慮建材補(bǔ)給情況，此外存儲(chǔ)在客戶施工現(xiàn)場(chǎng)的建材不會(huì)產(chǎn)生庫(kù)存成本。

2.2 理論模型

根據(jù)前述問(wèn)題描述，我們可以建立一個(gè)混合整數(shù)線性規(guī)劃模型進(jìn)行求解。

s.t.

?l=1，…，L,n=0，…，N,t=1，…，T

(2)

rliit=0 ?l=1，…，L,i=0，…，N,t=1，…，T

(3)

?l=1，…，L,n=1，…，N,t=1，…，T

(4)

?l=1，…，L,t=1，…，T

(5)

?l=1，…，L,t=1，…，T

(6)

?m=1，…，M,t=1，…，lm

(7)

?m=1，…，M,t=lm+1，…，T

(8)

?m=1，…，M,n=1，…，N,t=1，…，T

(9)

?n=1，…，N,t=1，…，T

(10)

invm0t≥Sm?m=1，…，M,t=1，…，T

(11)

0≤invmnt

?m=1，…，M,n=1，…，N,t=1，…，T

(12)

xmt≥Qminm·ymt

?m=1，…，M,t=1，…，T

(13)

xmt≤Z·ymt?m=1，…，M,t=1，…，T

(14)

模型中決策變量意義如下：

xmtt時(shí)刻倉(cāng)庫(kù)向供應(yīng)商m發(fā)出的訂貨數(shù)量；

ymt如果t時(shí)刻倉(cāng)庫(kù)向供應(yīng)商m發(fā)出訂單，那么為1，否則為0；

qlmntt時(shí)刻卡車l向客戶n運(yùn)送建材m的數(shù)量；

rlijt如果t時(shí)刻卡車l從地點(diǎn)i駛向地點(diǎn)j，那么為1，否則為0。

方程(1)是混合整數(shù)線性規(guī)劃模型的目標(biāo)函數(shù)，表示該模型的優(yōu)化目標(biāo)是使總運(yùn)營(yíng)成本最小化?？傔\(yùn)營(yíng)成本由三個(gè)求和函數(shù)加總構(gòu)成，分別代表訂貨成本、庫(kù)存成本和運(yùn)輸成本。限制條件(2)使得單位卡車在任意規(guī)劃日內(nèi)對(duì)某個(gè)地點(diǎn)的訪問(wèn)次數(shù)和離開(kāi)次數(shù)保持一致且最多訪問(wèn)一次；限制條件(3)保證了卡車相鄰的兩個(gè)訪問(wèn)地點(diǎn)不相同；限制條件(4)保證了卡車向客戶配送建材的時(shí)候其行駛路徑通過(guò)該客戶；限制條件(5)使得卡車在有配送任務(wù)時(shí)必定從倉(cāng)庫(kù)出發(fā)；限制條件(6)導(dǎo)入了車輛最大裝載體積限制，卡車裝載的建材總體積不超過(guò)卡車的最大裝載體積；限制條件(7)是規(guī)劃時(shí)刻小于建材前置時(shí)間時(shí)倉(cāng)庫(kù)建材數(shù)量變化的遞歸關(guān)系；限制條件(8)是規(guī)劃時(shí)刻大于建材前置時(shí)間時(shí)倉(cāng)庫(kù)建材數(shù)量變化的遞歸關(guān)系；限制條件(9)是客戶施工現(xiàn)場(chǎng)建材數(shù)量變化的遞歸關(guān)系；限制條件(10)導(dǎo)入了施工現(xiàn)場(chǎng)的最大建材體積限制，保證了施工現(xiàn)場(chǎng)所堆積的建材總體積不會(huì)超過(guò)客戶施工現(xiàn)場(chǎng)所能容納的最大體積；限制條件(11)導(dǎo)入了倉(cāng)庫(kù)建材的安全庫(kù)存限制，在任意時(shí)刻建材在倉(cāng)庫(kù)的存量不會(huì)小于其安全庫(kù)存；限制條件(12)保證了客戶施工現(xiàn)場(chǎng)積累的建材能夠滿足當(dāng)日的裝修需求；限制條件(13)和(14)導(dǎo)入了最小訂貨量限制，保證了倉(cāng)庫(kù)發(fā)出的訂單數(shù)量超過(guò)供應(yīng)商所要求的最低訂貨數(shù)量。

顯然，這樣建立的混合整數(shù)線性規(guī)劃模型不會(huì)存在一個(gè)多項(xiàng)式時(shí)間算法能夠準(zhǔn)確地計(jì)算出該問(wèn)題的最優(yōu)解，需要通過(guò)其他途徑獲得問(wèn)題的可行解。

3 近似算法

簡(jiǎn)單的供應(yīng)鏈優(yōu)化問(wèn)題如經(jīng)濟(jì)批量訂貨問(wèn)題、最短路徑問(wèn)題均有多項(xiàng)式時(shí)間內(nèi)的最優(yōu)算法可以求解，但是大多數(shù)問(wèn)題往往都是NP困難的，難以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出最優(yōu)解，缺乏理想的解決方案。本文構(gòu)建的供應(yīng)鏈優(yōu)化問(wèn)題就屬于這一類。對(duì)于該供應(yīng)鏈優(yōu)化問(wèn)題，建材配送、存儲(chǔ)和補(bǔ)充有很多種可能的組合方式。如果采用數(shù)學(xué)規(guī)劃的方法將每個(gè)規(guī)劃期內(nèi)的訂單情況、配送數(shù)量以及行駛路徑確定下來(lái)，將是一項(xiàng)極為復(fù)雜的工作，通常只在案例參數(shù)都比較小的情況下可行。隨著建材種類M、客戶數(shù)量N和規(guī)劃周期T的增大，供應(yīng)鏈優(yōu)化問(wèn)題的計(jì)算復(fù)雜度將呈幾何倍數(shù)增長(zhǎng)。

對(duì)于NP困難問(wèn)題，可以通過(guò)設(shè)計(jì)近似算法，在較短的時(shí)間內(nèi)得到一個(gè)非常逼近原問(wèn)題最優(yōu)解的可行解。本文采用禁忌搜索算法作為近似算法，用以獲取前述供應(yīng)鏈優(yōu)化問(wèn)題最優(yōu)解的近似解。禁忌搜索算法是鄰域搜索算法中的一種典型方法，通過(guò)在現(xiàn)有解的鄰域進(jìn)行搜索，評(píng)價(jià)鄰域內(nèi)的可行解，按照給定的接受-拒絕規(guī)則選擇一個(gè)候選解作為下一次迭代的初始解。在經(jīng)過(guò)反復(fù)的迭代過(guò)程后，所得的解就可以作為禁忌搜索算法得到的近似解。下面將對(duì)本文采用的禁忌搜索算法進(jìn)行詳細(xì)說(shuō)明。

3.1 初始解的構(gòu)建

初始解將作為禁忌搜索算法迭代過(guò)程的初始序列， 反復(fù)迭代逐步進(jìn)化為問(wèn)題的近似解。本問(wèn)題初始解的構(gòu)建將分為訂單數(shù)量確定、規(guī)劃日配送數(shù)量確定、車輛行駛路徑確定三部分實(shí)現(xiàn)。

訂單數(shù)量確定：初始解的訂單在規(guī)劃周期開(kāi)始時(shí)發(fā)出，訂貨數(shù)量涵蓋整個(gè)規(guī)劃期內(nèi)所有客戶的建材需求，規(guī)劃期間將不再向供應(yīng)商發(fā)出訂單。初始解具體特征如下：

?m=1，…，M

xmt=0

?m=1，…，M,t=2，…，T

規(guī)劃日配送數(shù)量確定：倉(cāng)庫(kù)每天都會(huì)向客戶配送其當(dāng)天所需求數(shù)量的建材，且配送數(shù)量?jī)H覆蓋當(dāng)天需求。每輛卡車僅向一位客戶配送建材，如果客戶當(dāng)天的建材需求總量超過(guò)一輛卡車的最大裝載體積，則分配多輛卡車進(jìn)行配送。初始解具體特征如下：

?l=1，…，L,t=1，…，T

車輛行駛路徑確定：由于每輛卡車僅向一位客戶配送建材，初始解下卡車配送路徑非常簡(jiǎn)單，從倉(cāng)庫(kù)出發(fā)后僅路過(guò)其配送客戶的裝修現(xiàn)場(chǎng)然后返回倉(cāng)庫(kù)。

3.2 候選集合的構(gòu)建

在初始序列產(chǎn)生后，需要在初始序列的鄰域空間中選取數(shù)個(gè)可行序列構(gòu)建候選序列集合。在禁忌搜索算法中，候選集合的構(gòu)建是至關(guān)重要的，候選集合的好壞直接影響算法近似解與理論最優(yōu)解的誤差范圍及計(jì)算時(shí)間。

本研究中，候選序列集合從初始序列的鄰域中隨機(jī)抓取產(chǎn)生，抓取方法包括訂單時(shí)間變更、訂單數(shù)量增減、訂單合并、訂單拆分、配送時(shí)間變更、配送數(shù)量增減、卡車配送合并、卡車配送置換、卡車路線變更，等等。迭代過(guò)程中，候選序列集合的可行序列數(shù)量通常多達(dá)數(shù)十個(gè)。

3.3 禁忌變換表

在禁忌搜索算法的每一次迭代過(guò)程中，會(huì)保持一個(gè)變動(dòng)的禁忌變換表，任何位于該表中的變換方式是不允許進(jìn)行的。禁忌變換表有一個(gè)固定的長(zhǎng)度，通常是5～10個(gè)變換方式。每次迭代過(guò)程最后，新生成的序列會(huì)替代現(xiàn)有序列作為下一次迭代的初始序列，反向變換將被加入禁忌變換表的頂部，并剔除禁忌變換表中最后一個(gè)元素。這是為了防止在經(jīng)過(guò)禁忌變換表長(zhǎng)度次數(shù)的變換內(nèi)，回到原先已經(jīng)產(chǎn)生過(guò)的一個(gè)局部最優(yōu)序列，招致循環(huán)。

禁忌變換表長(zhǎng)度的設(shè)置需要嚴(yán)格控制，若長(zhǎng)度偏小往往難以發(fā)揮作用，偏大則會(huì)加重設(shè)備計(jì)算負(fù)擔(dān)，本研究采用的禁忌變換表長(zhǎng)度為10。

3.4 回溯機(jī)制的設(shè)置

在禁忌搜索算法的迭代過(guò)程中，某個(gè)迭代初始序列的領(lǐng)域變換序列可能都在禁忌變換表中，導(dǎo)致迭代的可行候選序列集合可能是空集。這種情況下，本輪迭代將返回初始序列，進(jìn)而導(dǎo)致無(wú)限循環(huán)，禁忌搜索算法將陷入局部最優(yōu)解中，無(wú)法在整個(gè)搜索域內(nèi)獲取其他可行解。

為了解決該問(wèn)題，研究中引入了回溯機(jī)制，在記錄鄰域內(nèi)最優(yōu)解s1的同時(shí)保留鄰域內(nèi)的次優(yōu)解s2、s3、…、sm。當(dāng)s1、s2、…、sj-1的可行候選序列集合為空集時(shí)，sj將作為初始序列進(jìn)行下一次迭代。次優(yōu)解記錄范圍m值的大小對(duì)算法的有效性有較大影響，m值偏小將會(huì)使回溯機(jī)制失效，偏大則會(huì)增加處理設(shè)備的計(jì)算負(fù)擔(dān)，本研究中采用的m值為3。

3.5 強(qiáng)化機(jī)制的設(shè)置

在最壞的情況下，回溯機(jī)制仍可能無(wú)法幫助算法跳出局部最優(yōu)解。算法需要在最優(yōu)序列長(zhǎng)期未得到改進(jìn)的情況下，重新產(chǎn)生初始序列進(jìn)行迭代。本研究通過(guò)強(qiáng)化機(jī)制來(lái)實(shí)現(xiàn)這個(gè)過(guò)程。

在強(qiáng)化機(jī)制下，當(dāng)?shù)^(guò)程未能優(yōu)化最優(yōu)序列這一事件連續(xù)觸發(fā)且達(dá)到某一預(yù)先設(shè)定的閾值時(shí)，當(dāng)前已得到的最優(yōu)序列將作為初始序列進(jìn)行下一次迭代。強(qiáng)化機(jī)制可以使算法跳出當(dāng)前局部最優(yōu)，并且顯著減少隨后的迭代次數(shù)。強(qiáng)化機(jī)制在一次算法中通常只能觸發(fā)一至兩次。

3.6 算法的具體實(shí)現(xiàn)

下面對(duì)所使用的禁忌搜索算法進(jìn)行詳細(xì)的說(shuō)明：

步驟一令k=1，找到一個(gè)可行解作為初始序列S1，定義最優(yōu)序列S0=S1。

步驟二從Sk的鄰域中產(chǎn)生候選序列集合S。

步驟三如果候選序列集合非空，則在候選序列集合中選取總運(yùn)營(yíng)成本最低的候選序列Sc1，令Sk+1=Sc1，并記錄次優(yōu)序列Sc2，Sc3。

如果候選序列集合為空集，則觸發(fā)回溯機(jī)制，定義前次迭代的次有序列作為Sk+1，轉(zhuǎn)到步驟七。

步驟四將初始序列Sk置于禁忌變換表的頂部，并刪除禁忌變換表的最后一個(gè)元素。

步驟五如果候選序列Sc1的總運(yùn)營(yíng)成本小于最優(yōu)序列S0的總運(yùn)營(yíng)成本，那么令S0=Sc1。

步驟六如果達(dá)到預(yù)設(shè)閾值，則觸發(fā)強(qiáng)化機(jī)制，令Sk+1=S0。

步驟七如果k=N，那么已達(dá)到迭代循環(huán)上限，停止迭代，返回最優(yōu)序列S0；否則，將k值增加1，轉(zhuǎn)到步驟二。

4 計(jì)算實(shí)驗(yàn)

提出該優(yōu)化問(wèn)題的近似算法后，我們需要對(duì)該算法的有效性進(jìn)行評(píng)估。這是因?yàn)榻扑惴ㄇ蟮玫目尚薪馀c最優(yōu)解的偏差往往不可預(yù)料，需要多次檢驗(yàn)以保證誤差在可接受范圍內(nèi)，若偏差較大，需要對(duì)算法進(jìn)行修正以滿足誤差要求。

計(jì)算實(shí)驗(yàn)可以模擬互聯(lián)網(wǎng)家裝企業(yè)在一定規(guī)劃期內(nèi)建材的配送、存儲(chǔ)以及補(bǔ)給情況。樣例的各種參數(shù)信息(客戶需求、建材規(guī)格、各項(xiàng)成本等)可通過(guò)隨機(jī)數(shù)生成器隨機(jī)產(chǎn)生。供應(yīng)鏈優(yōu)化問(wèn)題的最優(yōu)解可以通過(guò)前述混合整數(shù)線性規(guī)劃模型借助軟件求得。近似算法的近似解則可以通過(guò)程序設(shè)計(jì)，按照前述算法步驟反復(fù)迭代獲得。通過(guò)比較最優(yōu)解與近似解的總運(yùn)營(yíng)成本，可以評(píng)估近似算法的效果。

4.1 樣例生成

在本次計(jì)算實(shí)驗(yàn)中，模擬了互聯(lián)網(wǎng)家裝企業(yè)12個(gè)規(guī)劃日內(nèi)的建材配送、存儲(chǔ)以及補(bǔ)給過(guò)程，每組樣例中涉及2類建材和3位客戶。每組樣例包括以下信息：卡車最大裝載容量、施工現(xiàn)場(chǎng)最大建材容量、建材體積、單次訂貨成本、前置時(shí)間、單位庫(kù)存成本、倉(cāng)庫(kù)初始庫(kù)存、安全庫(kù)存、單次最低訂貨量、客戶位置，以及各個(gè)規(guī)劃日客戶的建材需求等。

建材、客戶以及規(guī)劃周期跨度的數(shù)量設(shè)置是出于計(jì)算機(jī)處理方面的考量。如果參數(shù)設(shè)置過(guò)少，通過(guò)窮舉法就可能直接得到表現(xiàn)不錯(cuò)的近似序列，甚至得到最優(yōu)序列，近似算法的實(shí)際意義就沒(méi)有得到凸顯；如果參數(shù)設(shè)置過(guò)多，會(huì)導(dǎo)致計(jì)算機(jī)軟件在求解最優(yōu)解上消耗過(guò)長(zhǎng)時(shí)間，滯緩研究進(jìn)度。

本研究根據(jù)實(shí)際情況預(yù)先設(shè)定了部分樣例參數(shù)(卡車最大裝載容量、建材規(guī)格、安全庫(kù)存、最低訂貨量等)，不同樣例間的參數(shù)差異主要體現(xiàn)在客戶位置以及各個(gè)規(guī)劃日客戶的建材需求上。每個(gè)客戶的位置參數(shù)由其與倉(cāng)庫(kù)的距離以及弧度確定，距離和弧度通過(guò)隨機(jī)數(shù)生成器產(chǎn)生，以確?？蛻艟鶆蚍稚⒃趥}(cāng)庫(kù)周圍。在生成每個(gè)客戶的距離及弧度參數(shù)后，兩個(gè)客戶間的距離可通過(guò)余弦定理求得?？蛻粼诟鱾€(gè)規(guī)劃日的建材需求假定為一定區(qū)間內(nèi)的均勻分布，利用隨機(jī)數(shù)生成器產(chǎn)生，以符合實(shí)際施工現(xiàn)場(chǎng)建材以穩(wěn)定速率被消耗的事實(shí)。

4.2 算法效果評(píng)估

在樣例數(shù)據(jù)生成完畢后，我們將求解混合整數(shù)線性規(guī)劃模型得到的最優(yōu)序列與近似算法得到的近似序列總運(yùn)營(yíng)成本進(jìn)行比較，數(shù)據(jù)如表1所示。為顯示近似算法中初始序列的優(yōu)化效果，筆者將初始序列總運(yùn)營(yíng)成本也納入表格中進(jìn)行比較。本研究中，混合整數(shù)線性規(guī)劃模型最優(yōu)解采用Cplex軟件求解，供應(yīng)鏈優(yōu)化問(wèn)題的近似解按前述近似算法利用Python語(yǔ)言編譯實(shí)現(xiàn)，迭代次數(shù)設(shè)置為10 000次。

表1 近似算法效果評(píng)估

由表1可以看出相對(duì)于初始序列，近似算法得到的近似序列在總運(yùn)營(yíng)成本上的優(yōu)化效果非常顯著，近似序列總運(yùn)營(yíng)成本相對(duì)初始序列降低了70%以上。近似序列與最優(yōu)序列總運(yùn)營(yíng)成本相當(dāng)接近，兩者的比值接近于1，兩者間的誤差在可接受范圍內(nèi)。因此，能夠得出結(jié)論，在數(shù)據(jù)樣本較大的實(shí)際案例中，用近似算法得到的近似序列來(lái)近似供應(yīng)鏈優(yōu)化問(wèn)題的最優(yōu)解是可行的。

此外，在計(jì)算時(shí)間方面，最優(yōu)序列單個(gè)樣例求解耗時(shí)在五分鐘左右，近似算法單個(gè)樣例的平均處理時(shí)間在五分鐘內(nèi)，兩者相差不大。但考慮到隨著客戶、建材等參數(shù)數(shù)量的增長(zhǎng)，最優(yōu)算法計(jì)算時(shí)間隨變量以及限制條件的幾何倍數(shù)增長(zhǎng)將同樣呈現(xiàn)幾何倍數(shù)增長(zhǎng)，而近似算法由于迭代次數(shù)的固定計(jì)算時(shí)間幾乎保持不變。可以看出，近似算法在時(shí)間消耗方面是要遠(yuǎn)遠(yuǎn)優(yōu)于模型求解最優(yōu)解的。

5 研究結(jié)論

本研究針對(duì)時(shí)下正熱的互聯(lián)網(wǎng)家裝行業(yè)面臨的線下供應(yīng)鏈優(yōu)化問(wèn)題構(gòu)建了混合整數(shù)線性規(guī)劃模型，并設(shè)計(jì)近似算法求解其近似解。計(jì)算實(shí)驗(yàn)結(jié)果顯示，迭代10 000次后得到的近似序列和最優(yōu)序列的總運(yùn)營(yíng)成本差值在1%以內(nèi)，近似算法誤差在可接受范圍內(nèi)。

近似算法的優(yōu)勢(shì)在于處理時(shí)間。隨著案例數(shù)據(jù)量的增大，問(wèn)題最優(yōu)解的計(jì)算時(shí)間將以幾何倍數(shù)增長(zhǎng)，而近似算法能夠在計(jì)算時(shí)間幾乎不變的情況下得到高精度的近似解，此時(shí)用近似算法代替最優(yōu)算法求解更為可取。

實(shí)際生活中，互聯(lián)網(wǎng)家裝企業(yè)通常對(duì)接數(shù)十個(gè)一級(jí)供應(yīng)商，其下游的客戶更是數(shù)以萬(wàn)計(jì)，采用窮舉法或是分支定界法獲取倉(cāng)庫(kù)日常配送、存儲(chǔ)和補(bǔ)貨方案顯然是不可取的，近似算法的實(shí)用價(jià)值不言而喻。此外，本文設(shè)計(jì)的近似算法適用范圍并不局限于互聯(lián)網(wǎng)家裝行業(yè)，所有直接對(duì)接供應(yīng)商和客戶的供應(yīng)鏈一體化行業(yè)都適用該近似算法。