張 巍

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

1 文獻綜述

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

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

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

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

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

2 問題描述及模型

2.1 問題描述

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

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

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

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

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

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

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

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

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

2.2 理論模型

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

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時刻倉庫向供應(yīng)商m發(fā)出的訂貨數(shù)量；

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

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

rlijt如果t時刻卡車l從地點i駛向地點j，那么為1，否則為0。

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

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

3 近似算法

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

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

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

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

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

?m=1，…，M

xmt=0

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

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

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

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

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

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

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

3.3 禁忌變換表

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

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

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

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

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

3.5 強化機制的設(shè)置

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

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

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

下面對所使用的禁忌搜索算法進行詳細的說明：

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

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

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

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

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

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

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

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

4 計算實驗

提出該優(yōu)化問題的近似算法后，我們需要對該算法的有效性進行評估。這是因為近似算法求得的可行解與最優(yōu)解的偏差往往不可預(yù)料，需要多次檢驗以保證誤差在可接受范圍內(nèi)，若偏差較大，需要對算法進行修正以滿足誤差要求。

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

4.1 樣例生成

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

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

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

4.2 算法效果評估

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

表1 近似算法效果評估

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

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

5 研究結(jié)論

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

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

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