基于改進遺傳算法的庫存與配送系統聯合優化研究

邵偉杰

摘 要：庫存與配送聯合優化可以提高物流運作效率，有效降低成本，本文基于供應商管理庫存構建了一個但供應商對多零售商配送模型，并結合C-W算法，對遺傳算法進行改進運用于構建的模型求解，實例驗證說明了改進算法對庫存-配送問題求解的有效性。

關鍵詞：庫存配送系統；聯合優化；遺傳算法；C-W算法

一、庫存與配送系統聯合優化研究分類

1.聯合優化思路。在庫存與配送聯合優化研究提出之前，大多學者都是單獨對企業庫存與配送進行研究的，比如考慮輸入輸出對動態庫存進行研究，單獨進行配送線路規劃，動態庫存管理研究中輸入輸出是已知的，沒有考慮輸入輸出受企業采購過程中供應商配送的影響，而單獨的運輸線路規劃問題則沒有考慮庫存內部動態管理，因此，對庫存與配送系統聯合優化研究很有必要，目前該類研究大致可以分為以下類型：

一類研究基于供應鏈整體成本，構建模型求得整體的訂貨量與配送策略。此類研究綜合考慮了供應鏈各節點企業的三大成本“庫存、采購與運輸”，基于各方需求統一確定，互相了解需求，并且不允許缺貨情況的發生，運輸服務統一由第三方提供，構建的目標優化模型以生產商的生產成本、零售商的采購、庫存成本，以及運輸服務提供方的運輸成本，以此求得最優解。但是該類研究沒有考慮供應鏈參與各方的合作情況，各方對于利益的分配、成本的分攤機制沒有考慮，容易造成分配不均而產生摩擦。

另外一類研究則是是由供應商主導庫存配送，考慮一個供應商對多個零售商的庫存-配送進行管理，構建模型對各獨立零售商的庫存進行管理，基于各地庫存對時間、數量的需求，以自身成本最小為目標，進行路線規劃，及時給零售商補貨。供應商管理庫存與前一類研究不同，兩類研究均從總體成本最優角度出發，但是前一類研究沒有厘清供應鏈中各企業角色，及相應的職責，此類研究確定了供應商管理庫存，則明確了研究的類型，對于成本分配問題有了較好的解決。通過建立合理的數學算法可以對基于庫存考慮的線路規劃問題求得最優解，通過供應鏈各節點的協同配合促進運作效率，各方均獲得最大收益，為實際供應鏈運作提供參考。

2.算法研究分類。庫存-配送系統可以視為庫存-路徑問題的升級版，但是本質考慮的重點仍然是供應鏈各方庫存保有量、采購量、采購周期，與運輸路徑選擇之間的合理調節。對于庫存-路徑問題的算法研究較多，我們可以借鑒其相關算法應用于庫存-配送系統研究。

（1）啟發式算法。運用啟發式算法對庫存-路徑問題進行求解的研究比較普遍，如蟻群算法、鄰域搜索算法、禁忌搜索算法、模擬退火算法、遺傳算法及人工神經網絡等智能算法都或多或少有應用于庫存-路徑研究領域，其中遺傳算法有較好的收斂性，能較快地達到全局最優解，并且有優勝劣汰的算法規則，最多地被運用或改進后運用于庫存-路徑求解。

（2）C-W節約算法。C-W算法是解決旅行商提出的，基于節約的理念，適用于物流單元間流量較為穩定，變化不大的問題，是一種較為簡潔實用的算法。由供應商主導庫存，為多個零售商供貨可以解決信息不對稱造成的庫存過度配置，配送次數多配送量過大的情形，可以達到配送次數最少，配送量最經濟（供應商、零售商采用最佳采購量）的效果，此時配送路線上配送較為穩定，配送變化不會太大，不會因為市場需求變動過大而引起配送問題，因為供應商對零售商的庫存需求情況十分了解。因此C-W算法比較適合研究庫存-路徑問題，多數學者采用遺傳算法或其他優化算法是都會結合C-W算法特點進行研究。

（3）其他算法。除運籌學領域優化算法、智能算法與C-W算法這幾類典型的庫存-路徑求解算法之外，一些學者還采用概率論領域的馬爾科夫決策過程研究隨機需求下的庫存-路徑算法，也有學者采用分散決策算法（DDA decentralized decision algorithm）以求解分散決策情形下的庫存與運輸問題）。

二、庫存與配送系統聯合優化模型構建

庫存與配送系統聯合優化是促進供應鏈一體化的有效手段，本文基于供應商統一管理庫存構建一個供應商對多個零售商配送的簡單兩級供應鏈模型。

1.模型假設。（1）各零售商需求確定，且均與供應商形成直接連接網絡；（2）零售商不允許缺貨，不考慮提前期；（3）運輸費用與距離成正比；（4）一個運輸車輛一天只做一次配送，在不超過運輸車輛的滿載負荷前提下可以為多個零售商配送；（5）多個零售商的不同貨物可以拼車運貨，這一點由供應商統一管理庫存，統一配送可以比較好地解決。

2.符號表示。本文考慮的是由供應商管理庫存，由單供應商與多個零售商構成的一對多的簡單二級供應鏈，用數字序號下標表示供應商與零售商，i∈（0，1，2，...，N），0表示供應商，1至N表示零售商。貨物由供應商負責配送，共有M輛運輸車，每輛車的載重相等為Q，供應商的補貨周期為T，eij表示供應商及各零售商之間的距離，di表示零售商的需求率，A0，Ai表示供應商與零售商的補貨成本，h0與hi表示供應商與零售商的庫存成本，C表示車輛的運輸成本，在供應商的補貨周期內，ni表示零售商的訂貨次數，ti表示零售商的訂貨周期，則T=niti，令Xijkt表示車輛k在時間t從點i開往j進行配送，是則值為1，否則為0，令Qjkr表示車輛k在時間r為點j配送的貨物量。

3.數學模型。本文將采用遺傳算法，較好地控制庫存，并利用C-W算法來尋找車輛調度，路徑選擇方案，通過這些手段要達到一個統一的目的，那就是我們所要設定的目標函數，本文以成本最小為目標，更細化為單位時間的供應商庫存、運輸成本，零售商的庫存成本，同時還需要獲得供應商與零售的采購周期，配送路徑方案作為輸出，以（T，ti，ni，Xijkt）為決策變量構建如下目標函數：

（1）

其中大括號內為整個供應商補貨周期配送系統總成本，

包括車輛運輸成本，供應商庫存成本，補貨固定成本，零售商庫存成本。

（2）

上式表示零售商不能缺貨，是缺貨限制條件，如果供應商配送與供應鏈中任何一個零售的需求之差小于零，則會造成缺貨，缺貨會帶來缺貨成本對供應商與零售商雙方都有不利因素，因此制定此約束條件做缺貨限制。

（3）

本條件是一個基礎條件，運輸車輛不能超負荷作業，任何兩點之間單趟運輸量都不能超過運輸車輛的運輸上限。

（4）

此項條件為避免回路，一個車輛對零售商進行配送后必須前往下一個零售商，即必須要有下一個不同的出口，或者配送完畢直接返回供應商點，而不能原路返回上一個零售商處。

（5）

此項約束條件規定一天內配送車輛數不能超過總車輛數。

以上為庫存-配送系統數學模型，是庫存管理與運輸路徑規劃模型的結合，對此類問題的求解必須采用啟發式算法，逐步求得最優解。

三、基于改進遺傳算法的求解算法設計

從前述章節對庫存-配送系統問題的求解算法介紹中我們可以了解到遺傳算法具有較好的全局搜索能力，其優勝劣汰法則適用于庫存控制，而C-W算法適用于路徑求解，將兩種方法結合，對遺傳算法進行改造可以獲得一個更優的求解算法。本文以單位時間總成本最小為目標，以零售商的采購周期的倍數對問題進行分區，提高求解速率，縮短運行時間。算法分為主算法、遺傳函數、適應度函數與C-W算法三部分，循環嵌套，具體如下：

1.主算法。（1）令T'為供應商補貨的最長期限，將T'平均分割成S個部分（S為T'的約數），那么整個補貨周期可以分別表示為[1，T'/S]，[T'/S+1，2T'/S]，……，[（S-1）T'/S+1，T']。

（2）設定S+1個處理單元，對于處理單元i，對T∈[（I-1）T'/S+1，iT'/S]進行遍歷搜索，調用遺傳算法函數Gen（T）對目標函數進行求解，獲得單位時間成本最小時供應商與零售商的采購周期，運輸路徑。

（3）輸出最小成本值及供應商、零售商的采購周期，配送路徑。

2.遺傳算法Gen（T）函數。（1）首先需要選取初始化種群，取T的S個約數，隨機選取其中約數作為染色體基因，由此生成長度n的染色體，多次操作獲得初始種群規模為U，代數上限為G。

（2）求解種群中各染色體的適應度值，適應度值通過適應度函數f（·）求解。

（3）根據個體的適應度值進行排序，選擇其中前h個個體。

（4）將被選擇的個體以某一特定概率進行隨機交叉操作，以獲得新個體。

（5）再以一定概率對選中個體進行基因變異操作。

（6）重復以上操作，到達最大代數為止，輸出結果。

3.遺傳算法適應度函數。（1）令ghj表示第h代中的第j個個體，初始化mit=0，（i=1，...，N，t=0，...，T）。

（2）令配送量設為d，則d=lQ+qi，mit=l+1，l∈{0，1，...，M}。

（3）當mit>1時，先給零售商派送mit-1個車輛進行配送，滿足需求中的車載Q 的整數部分，賦值X0ikl與Xi0kl均為1，令qt，h=qi，代數h增加1；若mit=1，qt，h=d。

（4）使用C-W算法cw（qth[]）計算Xijkt與Qikt，將兩值代入目標函數ts，f（·）=1/ts。

4.C-W算法cw（q[]）

（1）令q[]表示需求點集，即零售商集合，分別將需求點集中點與供應商（以0表示）連接，令Sij=e0，q[i]+e0，q[j]-eq[i]，q[j]。

（2）將Sij進行降序排序，若Sij=0，則結束算法，將所有無回路路徑連接至供應商點，對運輸整數倍車輛負荷之外的車輛Xijkt進行賦值，輸出路徑。否則滿足q[i]與q[j]都在同一路徑或兩分別在兩條路徑的頭和尾則進入下一步。

（3）若在q[i]與q[j]之后的路徑貨運總量q小于車載Q則連接兩點。

（4）初始化Sij=0，重復操作，直到輸出所有路徑。

四、算例

1.實例運行。令零售商個數為15，需求率分別為（17，5，7，5，5，7，3，

4，3，2，5，2，8，14，4），單次補貨成本分別為（100000，50，…，50），第一項為供應商采購成本，后面為零售商成本，車載負荷為40，車輛單位行駛距離成本為90，供應商補貨最大周期為80，需要遍歷6組（有6個處理單元進行處理計算）。遺傳算法初始種群規模50，最大代數5000，交叉與變異概率分別為0.8與0.2，距離矩陣在此不做列示，可以得到如下結果：

2.結果分析。對運行結果進行分析，可以看出：一方面，供應商與零售商的單位庫存成本的上升必然導致總成本的上升，這是合乎常理的；另一方面，隨著單位庫存成本的上升，系統為了獲得低成本降低了采購周期，包括供應商與零售商采購周期均縮短，增加采購次數，以保持較低庫存水平，雖然運輸成本和訂貨費用會有所增加，但會大大減少庫存成本，可以將由庫存成本增加帶來的影響降低。因此，運用改進遺傳算法計算獲得的最優采購周期具有較強的實踐意義，算法具有具備有效性。

五、結語

庫存-配送系統問題的研究是物流領域的一個重點研究問題，對于物流成本的控制有重要作用。在此類問題求解中，一般采用啟發式算法，存在一定的求解時間復雜度問題，當問題的求解復雜度增加時，啟發式算法的求解時間復雜度將呈指數增長，因此借鑒部分學者對C-W算法的研究，本文融合C-W算法對遺傳算法進行改進，使用改進的算法對庫存-配送問題進行求解，求解精度較好，對實際應用有一定的參考價值。

參考文獻：

[1]李仲興， 朱向順， 李錦飛.供應鏈中配送系統聯合優化的數學模型及求解的混合算法[J]. 物流技術， 2005， （9）： 92-94.

[2]曾文飛， 顏玲， 雷軍程.啟發式庫存-路徑問題求解算法[J].計算機應用與軟件， 2013， 30（7）：157-159.