一種多周期易腐品庫存路徑問題模型及其求解算法

張　奕，傅少川

（北京交通大學　經濟管理學院，北京　100044）

一種多周期易腐品庫存路徑問題模型及其求解算法

張奕，傅少川

（北京交通大學經濟管理學院，北京100044）

通過分析一個供應商用多個相同車輛向多個客戶配送一種易腐品，在隨機需求下，滿足多個周期中客戶的服務水平、決策計劃期內的配送路線和配送量，以庫存持有成本、貨損成本、運輸成本最小化為目標，建立隨機需求的多周期易腐品庫存路徑問題模型，將庫存控制和運輸問題整合優化。還針對該模型設計了一種改進的遺傳算法，能夠保證初始種群以及變異、交叉后的種群的多樣性和優越性，有足夠搜索全局最優解的能力。

庫存路徑問題；多周期；易腐品；遺傳算法

1　引言

庫存和運輸是物流系統中實現“空間效用”和“時間效用”的兩大重要功能要素，是現代物流最重要的兩個環節，二者的消耗約占物流總成本的三分之二。

庫存問題主要是研究庫存控制，或稱為庫存分配，即多長時間補充一次庫存以及每次的補充量是多少。運輸問題主要是研究運輸路徑，特別是配送運輸。庫存問題和運輸問題都是物流領域的經典問題，由于實際生產經營中，庫存和運輸一般由不同部門負責，因而對二者的研究和優化也往往局限在各自的領域內。但是，從供應鏈整體考察，因為庫存和運輸存在“效益背反”關系，單獨的庫存控制或運輸優化不利于從供應鏈整體上降低物流成本，特別是在VMI模式下，決策者需要從整體上考慮庫存策略和運輸方案，努力充分利用現有資源并控制系統總成本。因此，庫存控制和運輸問題的整合優化成為VMI模式進一步優化必須解決的問題之一。這類庫存和運輸整合優化的問題統稱為庫存路徑問題（Inventory Routing Problem，IRP）。

早在1985年，M.DROR［1］就提出了IRP的思想，他認為IRP問題是計劃期為一天的庫存路徑問題，他意識到庫存和運輸應共同考慮，從IRP問題的兩階段性考慮，分別為庫存問題和運輸問題建立了優化模型，但并不能保證最后結果是最優的。由于信息技術的限制，IRP問題直到21世紀才引起廣泛的重視。2003年，Scott J.Mason［2］研究了信息系統對于減少裝卸貨等待時間、減少處理成本、提高客戶滿意度的IRP問題的作用。Samira Mirzaei和Abbas Seifi［3］重點關注了IRP問題中的庫存損失，假定庫存損失隨時間呈線性增長，通過建模平衡了運輸成本、庫存持有成本和庫存損失，并利用遺傳算法和禁忌搜索算法求解。

國內學者對車輛路徑問題的研究，雖然起步較晚，但發展較快，近幾年出現了大量研究成果。劉立輝、葉春明［4-5］、段鳳華［6］給出了庫存路徑問題的定義和問題的基本描述，闡述了其研究意義，并將庫存路徑問題按照不同的特點進行了分類，介紹了近年文獻中出現的幾個庫存路徑問題模型及其求解算法，分析了該領域現有研究的不足和未來發展方向。李富昌等［7］建立了基于價格、配送頻率和需求分配比例的三階段非合作動態決策模型和庫存路徑問題優化模型，分析了4PL主導的業務外包和3PL之間的競爭。

從供應鏈管理的角度來看，對庫存路徑問題的研究，不僅有助于解決運輸與庫存的“效益背反”問題，降低供應鏈內耗，增強其競爭力，還有助于供應鏈管理特別是VMI的流程優化，尤其是在確定最優庫存水平、最佳補貨頻率及補貨時刻、配送所需車輛數量及配送區域以及運輸路徑方面至關重要。對庫存與運輸兩部門利益的平衡，能夠促進供應鏈的協調發展，增強供應鏈的軟實力。

易腐品指容易腐敗、退化、變質、揮發的產品，廣泛地存在于日常生活中，且數量或質量易受到運輸與庫存決策的極大影響，典型的易腐品包括奶制品、水果、蔬菜、鮮花、海鮮等產品。對易腐品的庫存路徑問題進行研究，是最近研究領域的熱點問題。一般易腐品具有易變質或已過時的特性。以生鮮產品為例，生鮮產品在生產、儲存、運輸等物流環節的損耗高達20%，尤其是在城市末端配送環節的損失更為驚人。隨著便利商店、連鎖超市、大型商場等新型商業零售模式的持續發展以及傳統擺攤設點零售模式由于不夠衛生、影響市容等原因逐步淘汰，眾多商家把生鮮產品視為重要的經營項目，不斷擴大生鮮產品的經營種類，加大采購和銷售力度。因此，對易腐品的儲存、運輸等環節加以控制，有效減少損耗，具有重要的理論和現實意義。

2　模型建立

2.1模型描述與參數說明

該物流系統可以看作一個閉合的圖G=｛V，A｝，其中V=｛0，…，||V｝為所有的點，A=｛（i，j）:i，j∈V，i≠j｝為所有的邊。點0表示配送中心，點集V′=V｛0｝表示所有的客戶。兩點Vi，Vj之間的距離記為aij，配送中心擁有||K輛完全相同、最高載重量為c的貨車，構成集合K=｛1，2，…，||K｝。車輛運輸過程中，每公里的成本為r。為保證工作效率，在一個計劃期內，一輛車最多經過同一路線一次?？蛻鬷∈V′在計劃期t∈T=｛1，2，…，的需求為 di，t，且服從均值為 μi，t、標準差為σi，t，?i∈V′，t∈T的正態分布。貨物的保質期為m，保質期內貨物不會變質或損壞，當儲存時間超過保質期時，每個計劃期末都有固定百分比p的貨物變質?？蛻舻膯挝粠齑娉钟谐杀緸閔i。滿足需求的客戶百分比不得低于α，且當期未被滿足的需求必須在下一個計劃期得到配送。

模型涉及的其他符號定義如下：

E［?］：期望算子；

P（?）：概率算子；

Qi，k，t：在計劃期t∈T初，由車輛k∈K配送至客戶i∈V′的庫存量，單位kg；

Ii，t：客戶i∈V′在計劃期t∈T?｛0｝末的庫存水平，單位kg，Ii，0=0，?i∈V′；

Wi，t：計劃期t∈T末時，客戶i∈V′的庫存水平，單位kg；

Fi，j，k，t：車輛 k∈K在計劃期 t∈T從點i∈V向點j∈V行駛時的負載量，單位kg。

2.2成本分析

本文研究內容為多周期易腐品庫存路徑問題，主要考慮三項成本：庫存持有成本、貨損成本、運輸成本，得到目標函數如下：

式（1）中第一項為庫存持有成本，第二項為貨損成本，第三項為運輸成本。

2.3約束分析

約束（2）-（5）保證了各個計劃期的客戶服務水平。式（2）由期初在途庫存減去當期需求和貨物損失，得出各個客戶在各個計劃期末的庫存的期望。式（3）為式（2）的補充說明。式（4）定義了用來計算庫存持有成本的變量約束（5）、（6）計算了各計劃期末客戶的貨物損失量。式（7）限制在每個計劃期，缺貨的概率均不高于1-α，保證了服務水平。

約束（8）保證了在任一計劃期，各個客戶處到達和出發的車輛數守恒。約束（9）保證在任一計劃期內，一輛車不會兩次或多次經過同一路徑。約束（10）確保每輛車的載貨能力都得到充分利用。約束（11）保證每輛車的負載量都是單調遞減的，因此系統中沒有不含配送中心的子回路。

約束（12）-（15）為決策變量的限制條件。

3　遺傳算法設計

3.1編碼及解碼

遺傳算法的編碼方式由實際問題決定，本文研究的多周期易腐品庫存路徑問題，有行駛路徑、配送量兩個決策變量，簡單的遺傳算法無法準確描述該問題的數據。本文采用整數編碼方式，其中奇數項編碼對應配送路徑上的客戶，偶數項編碼對應對該客戶的配送量。每一個客戶的編號和配送量由2位基因構成，若有N個客戶，T個計劃期，則每條染色體由2TN個基因構成。在解碼時，將配送量編碼從左到右逐個求和，當配送總量等于單車最大裝載量，或所?？臻g不足以負載下一個客戶的配送量時，車輛返回配送中心；當所?？臻g能夠負載下一個客戶的配送量時，車輛負責下一個客戶的配送。當車輛負責完本計劃期最后一個客戶的配送任務時，不論其剩余裝載能力為多少，都返回配送中心。

令φi表示第i代種群，則初始種群可以表示為：

其中奇數項為配送路徑編碼，偶數項為配送量編碼。

3.2初始群體的產生

遺傳算法對初始種群的產生方式具有一定的依賴性，一般情況下，對求解過程、求解結果有利的初始種群應當滿足以下兩個條件：一是種群多樣性，多樣的種群使算法獲得更廣闊的搜索空間；二是初始種群的優越性，當初始種群存在較多與最優解接近的基因時，求得最優解的可能性就越大。

傳統遺傳算法使用完全隨機的方式產生一定規模的個體作為初始種群。完全隨機的產生方式可以很好地保證種群的多樣性，但卻不能保證其優越性。本文分別針對路徑問題和配送量控制，引入了兩種機制，把握最優解可能存在的分布區域，然后在此區域內設定初始群體。

3.2.1產生路徑編碼。對于初始種群的路徑編碼部分，根據“空間聚類”思想產生一部分個體。由于運輸成本的限制，在實際生活中，最優配送路徑往往是一輛車負責一個區域的客戶配送任務，各輛車的路徑沒有交叉或交叉較少，因此在產生初始種群時，根據“空間聚類”思想，將空間上相鄰的客戶做簡單聚類。

具體步驟如下：

Step1：隨機產生一個客戶編號i；

Step2：將客戶編號i加入路徑中；

Step3：重復Step1，判斷路徑中是否已經存在該客戶編號i，如果不存在，執行下一步，如果存在則放棄該編號，繼續重復Step1；

Step4：在路徑中存在的客戶中找到與當前客戶距離最近的客戶；

Step5：產生一個可能值為0或1的隨機數，如果該數為1，將當前客戶插入路徑中與之距離最短的客戶右側，否則插入左側；

Step6：重復Step3到Step5，直到所有客戶都被加入到路徑中；

Step7：重復Step1到Step6，直到每個計劃期都有一條路徑。如果有N個客戶，T個計劃期，則每條染色體現在有TN個基因。

通過該方法產生的路徑編碼，由于經過簡單的聚類操作，可以保證基因的優越性。另一方面由于在路徑中插入客戶時使用了兩次隨機數，即哪個客戶先被插入路徑是隨機的、插入到與之最近的客戶的左側還是右側是隨機的，因此保證了基因的多樣性。

3.2.2產生配送量編碼。根據實際經驗可知，一方面為了保證客戶需求，配送量不能過少；一方面為了減少庫存積壓、降低貨損成本，配送量不能過多。因此最優解的配送量應該是接近客戶需求量的?？梢援a生一系列隨機數φi，t，φi，t服從正態分布N（μi，t，10σ），該隨機數與客戶的需求服從均值相同的正態分布，但變化較大，有較大可能覆蓋最優解的區間。然后將這些隨機數依次插入對應計劃期的配送客戶編碼右側，最終形成長度為2TN的染色體編碼。

3.3適應度計算

遺傳算法尋找最優解的過程，就是染色體的進化過程，也就是“優勝劣汰，適者生存”的過程。為了判斷染色體的優劣程度，作為遺傳算法進行遺傳操作的依據，需要構建適應度函數。適應度高的個體，在選擇交叉時被選中的幾率更大，即個體的生存能力更強。適應度是遺傳算法的內在驅動力，種群的每一次改變都是通過控制適應度來完成的。

通常適應度與遺傳算法的目標函數直接映射，本文中庫存成本和運輸成本的總成本為目標函數，因此認為總成本越低則適應度越高，反之適應度越低。因此第i條染色體的適應度函數：

適應度函數計算步驟如下：

Step6：計算系統總成本和染色體的適應度。

3.4選擇算子

輪盤賭選擇法是遺傳算法最常用的一種染色體選擇方法，由于其簡單、直觀、有效的特點而深受歡迎。輪盤賭選擇法的基本思路是，設種群染色體數量為m，其中第i條染色體的適應度為 fi，則種群適應度的總和為每個個體被選擇的概率為

輪盤賭選擇法實現步驟如下：

Step1：設第i條染色體的適應度為 fi，計算該染色體被選中的概率

Step2：從第1條染色體開始，依次計算第1條到第i條染色體的累積選中概率

Step3：產生一個服從均勻分布U［0，1］的隨機數χ，若χ滿足則第i+1條染色體被選中。

盡管輪盤賭選擇法簡單直觀，普遍適用，但該方法也存在諸多不足：在遺傳進化初始階段，可能存在適應度較高的個體，在反復使用輪盤賭選擇法進行選擇時，會復制出大量該染色體的子代，雖然能保證優越性，卻會使種群多樣性迅速喪失。

本文采用一種改進的輪盤賭選擇法：

Step1：設第i條染色體的適應度為 fi，計算該染色體被選中的概率若 pi＞30% ，則令pi=30%；

通過對輪盤賭選擇法的改進，降低了適應度高的染色體被選中的概率，有效防止局部過快收斂。

3.5交叉算子

圖1　染色體交叉算子示意圖

遺傳算法通過交叉算子產生新的解空間，交叉算子將改進的輪盤賭選擇出來的兩個染色體的各個個體通過一定的交叉方法隨機的交換染色體的某些基因，進而產生新染色體的個體。交叉算子不僅能不斷產生種群的新個體，還能有效保證種群的多樣性。

由于本文的染色體編碼以兩個基因為一組，且同一個計劃期的路徑編碼不應有重復的出現，因此將代表1個客戶和其配送量的2個基因作為一個整體進行交叉。本文采用整段交換、刪除重復法來對染色體編碼做交叉操作，具體步驟如下：

Step1：假設染色體編碼有2tn位，產生一個［1，tn）之間的隨機整數χ；

Step2：把第1條被選擇染色體A1的第1至2χ個基因位接到第2條的染色體B1前面，同時把第2條被選擇染色體B1的第1至2χ個基因位接到第1條染色體A1前面。

Step3：刪除染色體A1上同一計劃期重復的路徑編碼基因及其對應的配送量編碼基因，得到染色體A2；刪除染色體B1上同一計劃期重復的路徑編碼基因及其對應的配送量編碼基因，得到染色體B2。至此染色體基因交叉完成。

整段交換、刪除重復法示意圖如圖1所示。

3.6變異算子

變異算子可以使遺傳算法跳出原來的搜索區域，避免局部最優解，獲得更廣闊的搜索空間來尋找全局最優解。本文先對代表1個客戶和其配送量的2個基因進行整體換位變異，然后對配送量編碼進行變異。

3.6.1路徑編碼變異算子。對于代表1個客戶和其配送量的2個基因，本文采用整體換位變異算子方法。具體操作步驟如下：

Step1：設染色體的變異概率為p∈（0，1）；

Step2：隨機產生一個服從均勻分布U［0，1］的隨機數χ，當χ＜p時，隨機產生兩個［1，tn］間的整數χ1，χ2；

Step3：將染色體的第2χ1-1，2χ1個基因與2χ2-1，2χ2個基因互換位置。至此路徑編碼變異完成。

3.6.2配送量編碼變異算子。為了保證配送量編碼的優越性，采取如下變異步驟：

Step1：設定染色體的變異概率為p∈（0，1）；

Step2：隨機產生一個服從均勻分布U［0，1］的隨機數χ，當χ＜p時，隨機產生一個［1，tn］間的整數χ′；

Step3：隨機產生一個服從正態分布N（0，20σ）的隨機數φ，令染色體的第2χ個基因的值加上隨機數φ。至此配送量編碼變異完成。

3.7終止變化規則

遺傳算法是一種隨機搜索算法，求解過程是循環演變的過程，必須通過設定終止進化規則來讓遺傳算法的迭代過程停止。本文通過控制遺傳算法的最大迭代次數來判斷是否終止進化，即設定一個算法的最大迭代次數N，當算法迭代次數達到N次，結束運算，輸出結果。

4　結論

本文在基本庫存路徑問題的基礎上，深化研究內容，考慮隨機需求的多周期易腐品庫存路徑問題，在一定服務水平、路徑較優的約束下，綜合分析庫存持有成本、貨損成本、運輸成本，決策供應鏈的配送路線、配送量。本文還針對隨機需求的多周期易腐品庫存路徑問題模型，設計了一種改進的遺傳算法。該模型可用于水果、蔬菜、生鮮等易隨時間推移而變質或損壞的易腐品的供應鏈決策。

［1］M Dror M B.Inventory/routing:Reduction from an annual to a shortperiod problem［J］.Naval Research Logistics Quarterly，1987，34:891-905.

［2］Mason S J，Mauricio Ribera P，Farris J A，et al.Integrating the warehousing and transportation functions of the supply chain［J］. Transportation Research Part E:Logistics and Transportation Review，2003，39（2）:141-159.

［3］Mirzaei S，Seifi A.Considering lost sale in inventory routing problems for perishable goods［J］.Computers&Industrial Engineering，2015，87:213-227.

［4］劉立輝，葉春明.庫存路徑問題的3種策略［J］.公路交通科技，2009，（12）:137-141.

［5］劉立輝，葉春明.庫存路徑問題的研究綜述［J］.工業工程，2009，（3）:1-6.

［6］段鳳華，符卓.帶碳排放約束的異型車輛路徑問題及其禁忌搜索算法［J］.鐵道科學與工程學報，2015，（4）:941-948.

［7］李富昌，王勇，張戰峰.考慮第三方物流競爭的第四方物流運輸與庫存外包決策［J］.中國管理科學，2010，（6）:71-81.

Model and Algorithm to Solve a Class of Multi-cycle Perishable Inventory Routing Problem

Zhang Yi，Fu Shaochuan
（School of Economics&Management，Beijing Jiaotong University，Beijing 100044，China）

In this paper，through analyzing the system where a supplier delivered one perishable goods to multiple customers using multiple vehicles of the same kind，we satisfied the service level requirement of the customers in different cycles under stochastic demand，obtained the distribution route and volume，and then established the multi-cyclic perishable goods inventory routing model under stochastic demand aiming at minimizing the inventory holding cost，cargo loss cost，and transportation cost.Then we designed a modified genetic algorithm to solve the model so as to ensure the diversity and superiority of the initial and the post-mutation population and the ability to reach global optimization.

inventory routing problem；multi-cyclic；perishable goods；genetic algorithm

U16；F253.4

A

1005-152X（2016）04-0091-06

10.3969/j.issn.1005-152X.2016.04.023

2016-03-07

張奕（1991-），男，河北石家莊人，北京交通大學經濟管理學院物流工程碩士研究生，研究方向：企業物流運作與規劃；傅少川（1964-），男，山東濰坊人，北京交通大學經濟管理學院教授，博士生導師，研究方向：供應鏈管理、物流系統規劃等。