張　奕，傅少川

（北京交通大學(xué)　經(jīng)濟(jì)管理學(xué)院，北京　100044）

一種多周期易腐品庫(kù)存路徑問(wèn)題模型及其求解算法

張奕，傅少川

（北京交通大學(xué)經(jīng)濟(jì)管理學(xué)院，北京100044）

通過(guò)分析一個(gè)供應(yīng)商用多個(gè)相同車(chē)輛向多個(gè)客戶(hù)配送一種易腐品，在隨機(jī)需求下，滿(mǎn)足多個(gè)周期中客戶(hù)的服務(wù)水平、決策計(jì)劃期內(nèi)的配送路線(xiàn)和配送量，以庫(kù)存持有成本、貨損成本、運(yùn)輸成本最小化為目標(biāo)，建立隨機(jī)需求的多周期易腐品庫(kù)存路徑問(wèn)題模型，將庫(kù)存控制和運(yùn)輸問(wèn)題整合優(yōu)化。還針對(duì)該模型設(shè)計(jì)了一種改進(jìn)的遺傳算法，能夠保證初始種群以及變異、交叉后的種群的多樣性和優(yōu)越性，有足夠搜索全局最優(yōu)解的能力。

庫(kù)存路徑問(wèn)題；多周期；易腐品；遺傳算法

1　引言

庫(kù)存和運(yùn)輸是物流系統(tǒng)中實(shí)現(xiàn)“空間效用”和“時(shí)間效用”的兩大重要功能要素，是現(xiàn)代物流最重要的兩個(gè)環(huán)節(jié)，二者的消耗約占物流總成本的三分之二。

庫(kù)存問(wèn)題主要是研究庫(kù)存控制，或稱(chēng)為庫(kù)存分配，即多長(zhǎng)時(shí)間補(bǔ)充一次庫(kù)存以及每次的補(bǔ)充量是多少。運(yùn)輸問(wèn)題主要是研究運(yùn)輸路徑，特別是配送運(yùn)輸。庫(kù)存問(wèn)題和運(yùn)輸問(wèn)題都是物流領(lǐng)域的經(jīng)典問(wèn)題，由于實(shí)際生產(chǎn)經(jīng)營(yíng)中，庫(kù)存和運(yùn)輸一般由不同部門(mén)負(fù)責(zé)，因而對(duì)二者的研究和優(yōu)化也往往局限在各自的領(lǐng)域內(nèi)。但是，從供應(yīng)鏈整體考察，因?yàn)閹?kù)存和運(yùn)輸存在“效益背反”關(guān)系，單獨(dú)的庫(kù)存控制或運(yùn)輸優(yōu)化不利于從供應(yīng)鏈整體上降低物流成本，特別是在VMI模式下，決策者需要從整體上考慮庫(kù)存策略和運(yùn)輸方案，努力充分利用現(xiàn)有資源并控制系統(tǒng)總成本。因此，庫(kù)存控制和運(yùn)輸問(wèn)題的整合優(yōu)化成為VMI模式進(jìn)一步優(yōu)化必須解決的問(wèn)題之一。這類(lèi)庫(kù)存和運(yùn)輸整合優(yōu)化的問(wèn)題統(tǒng)稱(chēng)為庫(kù)存路徑問(wèn)題（Inventory Routing Problem，IRP）。

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

國(guó)內(nèi)學(xué)者對(duì)車(chē)輛路徑問(wèn)題的研究，雖然起步較晚，但發(fā)展較快，近幾年出現(xiàn)了大量研究成果。劉立輝、葉春明［4-5］、段鳳華［6］給出了庫(kù)存路徑問(wèn)題的定義和問(wèn)題的基本描述，闡述了其研究意義，并將庫(kù)存路徑問(wèn)題按照不同的特點(diǎn)進(jìn)行了分類(lèi)，介紹了近年文獻(xiàn)中出現(xiàn)的幾個(gè)庫(kù)存路徑問(wèn)題模型及其求解算法，分析了該領(lǐng)域現(xiàn)有研究的不足和未來(lái)發(fā)展方向。李富昌等［7］建立了基于價(jià)格、配送頻率和需求分配比例的三階段非合作動(dòng)態(tài)決策模型和庫(kù)存路徑問(wèn)題優(yōu)化模型，分析了4PL主導(dǎo)的業(yè)務(wù)外包和3PL之間的競(jìng)爭(zhēng)。

從供應(yīng)鏈管理的角度來(lái)看，對(duì)庫(kù)存路徑問(wèn)題的研究，不僅有助于解決運(yùn)輸與庫(kù)存的“效益背反”問(wèn)題，降低供應(yīng)鏈內(nèi)耗，增強(qiáng)其競(jìng)爭(zhēng)力，還有助于供應(yīng)鏈管理特別是VMI的流程優(yōu)化，尤其是在確定最優(yōu)庫(kù)存水平、最佳補(bǔ)貨頻率及補(bǔ)貨時(shí)刻、配送所需車(chē)輛數(shù)量及配送區(qū)域以及運(yùn)輸路徑方面至關(guān)重要。對(duì)庫(kù)存與運(yùn)輸兩部門(mén)利益的平衡，能夠促進(jìn)供應(yīng)鏈的協(xié)調(diào)發(fā)展，增強(qiáng)供應(yīng)鏈的軟實(shí)力。

易腐品指容易腐敗、退化、變質(zhì)、揮發(fā)的產(chǎn)品，廣泛地存在于日常生活中，且數(shù)量或質(zhì)量易受到運(yùn)輸與庫(kù)存決策的極大影響，典型的易腐品包括奶制品、水果、蔬菜、鮮花、海鮮等產(chǎn)品。對(duì)易腐品的庫(kù)存路徑問(wèn)題進(jìn)行研究，是最近研究領(lǐng)域的熱點(diǎn)問(wèn)題。一般易腐品具有易變質(zhì)或已過(guò)時(shí)的特性。以生鮮產(chǎn)品為例，生鮮產(chǎn)品在生產(chǎn)、儲(chǔ)存、運(yùn)輸?shù)任锪鳝h(huán)節(jié)的損耗高達(dá)20%，尤其是在城市末端配送環(huán)節(jié)的損失更為驚人。隨著便利商店、連鎖超市、大型商場(chǎng)等新型商業(yè)零售模式的持續(xù)發(fā)展以及傳統(tǒng)擺攤設(shè)點(diǎn)零售模式由于不夠衛(wèi)生、影響市容等原因逐步淘汰，眾多商家把生鮮產(chǎn)品視為重要的經(jīng)營(yíng)項(xiàng)目，不斷擴(kuò)大生鮮產(chǎn)品的經(jīng)營(yíng)種類(lèi)，加大采購(gòu)和銷(xiāo)售力度。因此，對(duì)易腐品的儲(chǔ)存、運(yùn)輸?shù)拳h(huán)節(jié)加以控制，有效減少損耗，具有重要的理論和現(xiàn)實(shí)意義。

2　模型建立

2.1模型描述與參數(shù)說(shuō)明

該物流系統(tǒng)可以看作一個(gè)閉合的圖G=｛V，A｝，其中V=｛0，…，||V｝為所有的點(diǎn)，A=｛（i，j）:i，j∈V，i≠j｝為所有的邊。點(diǎn)0表示配送中心，點(diǎn)集V′=V｛0｝表示所有的客戶(hù)。兩點(diǎn)Vi，Vj之間的距離記為aij，配送中心擁有||K輛完全相同、最高載重量為c的貨車(chē)，構(gòu)成集合K=｛1，2，…，||K｝。車(chē)輛運(yùn)輸過(guò)程中，每公里的成本為r。為保證工作效率，在一個(gè)計(jì)劃期內(nèi)，一輛車(chē)最多經(jīng)過(guò)同一路線(xiàn)一次?？蛻?hù)i∈V′在計(jì)劃期t∈T=｛1，2，…，的需求為 di，t，且服從均值為 μi，t、標(biāo)準(zhǔn)差為σi，t，?i∈V′，t∈T的正態(tài)分布。貨物的保質(zhì)期為m，保質(zhì)期內(nèi)貨物不會(huì)變質(zhì)或損壞，當(dāng)儲(chǔ)存時(shí)間超過(guò)保質(zhì)期時(shí)，每個(gè)計(jì)劃期末都有固定百分比p的貨物變質(zhì)。客戶(hù)的單位庫(kù)存持有成本為hi。滿(mǎn)足需求的客戶(hù)百分比不得低于α，且當(dāng)期未被滿(mǎn)足的需求必須在下一個(gè)計(jì)劃期得到配送。

模型涉及的其他符號(hào)定義如下：

E［?］：期望算子；

P（?）：概率算子；

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

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

Wi，t：計(jì)劃期t∈T末時(shí)，客戶(hù)i∈V′的庫(kù)存水平，單位kg；

Fi，j，k，t：車(chē)輛 k∈K在計(jì)劃期 t∈T從點(diǎn)i∈V向點(diǎn)j∈V行駛時(shí)的負(fù)載量，單位kg。

2.2成本分析

本文研究?jī)?nèi)容為多周期易腐品庫(kù)存路徑問(wèn)題，主要考慮三項(xiàng)成本：庫(kù)存持有成本、貨損成本、運(yùn)輸成本，得到目標(biāo)函數(shù)如下：

式（1）中第一項(xiàng)為庫(kù)存持有成本，第二項(xiàng)為貨損成本，第三項(xiàng)為運(yùn)輸成本。

2.3約束分析

約束（2）-（5）保證了各個(gè)計(jì)劃期的客戶(hù)服務(wù)水平。式（2）由期初在途庫(kù)存減去當(dāng)期需求和貨物損失，得出各個(gè)客戶(hù)在各個(gè)計(jì)劃期末的庫(kù)存的期望。式（3）為式（2）的補(bǔ)充說(shuō)明。式（4）定義了用來(lái)計(jì)算庫(kù)存持有成本的變量約束（5）、（6）計(jì)算了各計(jì)劃期末客戶(hù)的貨物損失量。式（7）限制在每個(gè)計(jì)劃期，缺貨的概率均不高于1-α，保證了服務(wù)水平。

約束（8）保證了在任一計(jì)劃期，各個(gè)客戶(hù)處到達(dá)和出發(fā)的車(chē)輛數(shù)守恒。約束（9）保證在任一計(jì)劃期內(nèi)，一輛車(chē)不會(huì)兩次或多次經(jīng)過(guò)同一路徑。約束（10）確保每輛車(chē)的載貨能力都得到充分利用。約束（11）保證每輛車(chē)的負(fù)載量都是單調(diào)遞減的，因此系統(tǒng)中沒(méi)有不含配送中心的子回路。

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

3　遺傳算法設(shè)計(jì)

3.1編碼及解碼

遺傳算法的編碼方式由實(shí)際問(wèn)題決定，本文研究的多周期易腐品庫(kù)存路徑問(wèn)題，有行駛路徑、配送量?jī)蓚€(gè)決策變量，簡(jiǎn)單的遺傳算法無(wú)法準(zhǔn)確描述該問(wèn)題的數(shù)據(jù)。本文采用整數(shù)編碼方式，其中奇數(shù)項(xiàng)編碼對(duì)應(yīng)配送路徑上的客戶(hù)，偶數(shù)項(xiàng)編碼對(duì)應(yīng)對(duì)該客戶(hù)的配送量。每一個(gè)客戶(hù)的編號(hào)和配送量由2位基因構(gòu)成，若有N個(gè)客戶(hù)，T個(gè)計(jì)劃期，則每條染色體由2TN個(gè)基因構(gòu)成。在解碼時(shí)，將配送量編碼從左到右逐個(gè)求和，當(dāng)配送總量等于單車(chē)最大裝載量，或所?？臻g不足以負(fù)載下一個(gè)客戶(hù)的配送量時(shí)，車(chē)輛返回配送中心；當(dāng)所?？臻g能夠負(fù)載下一個(gè)客戶(hù)的配送量時(shí)，車(chē)輛負(fù)責(zé)下一個(gè)客戶(hù)的配送。當(dāng)車(chē)輛負(fù)責(zé)完本計(jì)劃期最后一個(gè)客戶(hù)的配送任務(wù)時(shí)，不論其剩余裝載能力為多少，都返回配送中心。

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

其中奇數(shù)項(xiàng)為配送路徑編碼，偶數(shù)項(xiàng)為配送量編碼。

3.2初始群體的產(chǎn)生

遺傳算法對(duì)初始種群的產(chǎn)生方式具有一定的依賴(lài)性，一般情況下，對(duì)求解過(guò)程、求解結(jié)果有利的初始種群應(yīng)當(dāng)滿(mǎn)足以下兩個(gè)條件：一是種群多樣性，多樣的種群使算法獲得更廣闊的搜索空間；二是初始種群的優(yōu)越性，當(dāng)初始種群存在較多與最優(yōu)解接近的基因時(shí)，求得最優(yōu)解的可能性就越大。

傳統(tǒng)遺傳算法使用完全隨機(jī)的方式產(chǎn)生一定規(guī)模的個(gè)體作為初始種群。完全隨機(jī)的產(chǎn)生方式可以很好地保證種群的多樣性，但卻不能保證其優(yōu)越性。本文分別針對(duì)路徑問(wèn)題和配送量控制，引入了兩種機(jī)制，把握最優(yōu)解可能存在的分布區(qū)域，然后在此區(qū)域內(nèi)設(shè)定初始群體。

3.2.1產(chǎn)生路徑編碼。對(duì)于初始種群的路徑編碼部分，根據(jù)“空間聚類(lèi)”思想產(chǎn)生一部分個(gè)體。由于運(yùn)輸成本的限制，在實(shí)際生活中，最優(yōu)配送路徑往往是一輛車(chē)負(fù)責(zé)一個(gè)區(qū)域的客戶(hù)配送任務(wù)，各輛車(chē)的路徑?jīng)]有交叉或交叉較少，因此在產(chǎn)生初始種群時(shí)，根據(jù)“空間聚類(lèi)”思想，將空間上相鄰的客戶(hù)做簡(jiǎn)單聚類(lèi)。

具體步驟如下：

Step1：隨機(jī)產(chǎn)生一個(gè)客戶(hù)編號(hào)i；

Step2：將客戶(hù)編號(hào)i加入路徑中；

Step3：重復(fù)Step1，判斷路徑中是否已經(jīng)存在該客戶(hù)編號(hào)i，如果不存在，執(zhí)行下一步，如果存在則放棄該編號(hào)，繼續(xù)重復(fù)Step1；

Step4：在路徑中存在的客戶(hù)中找到與當(dāng)前客戶(hù)距離最近的客戶(hù)；

Step5：產(chǎn)生一個(gè)可能值為0或1的隨機(jī)數(shù)，如果該數(shù)為1，將當(dāng)前客戶(hù)插入路徑中與之距離最短的客戶(hù)右側(cè)，否則插入左側(cè)；

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

Step7：重復(fù)Step1到Step6，直到每個(gè)計(jì)劃期都有一條路徑。如果有N個(gè)客戶(hù)，T個(gè)計(jì)劃期，則每條染色體現(xiàn)在有TN個(gè)基因。

通過(guò)該方法產(chǎn)生的路徑編碼，由于經(jīng)過(guò)簡(jiǎn)單的聚類(lèi)操作，可以保證基因的優(yōu)越性。另一方面由于在路徑中插入客戶(hù)時(shí)使用了兩次隨機(jī)數(shù)，即哪個(gè)客戶(hù)先被插入路徑是隨機(jī)的、插入到與之最近的客戶(hù)的左側(cè)還是右側(cè)是隨機(jī)的，因此保證了基因的多樣性。

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

3.3適應(yīng)度計(jì)算

遺傳算法尋找最優(yōu)解的過(guò)程，就是染色體的進(jìn)化過(guò)程，也就是“優(yōu)勝劣汰，適者生存”的過(guò)程。為了判斷染色體的優(yōu)劣程度，作為遺傳算法進(jìn)行遺傳操作的依據(jù)，需要構(gòu)建適應(yīng)度函數(shù)。適應(yīng)度高的個(gè)體，在選擇交叉時(shí)被選中的幾率更大，即個(gè)體的生存能力更強(qiáng)。適應(yīng)度是遺傳算法的內(nèi)在驅(qū)動(dòng)力，種群的每一次改變都是通過(guò)控制適應(yīng)度來(lái)完成的。

通常適應(yīng)度與遺傳算法的目標(biāo)函數(shù)直接映射，本文中庫(kù)存成本和運(yùn)輸成本的總成本為目標(biāo)函數(shù)，因此認(rèn)為總成本越低則適應(yīng)度越高，反之適應(yīng)度越低。因此第i條染色體的適應(yīng)度函數(shù)：

適應(yīng)度函數(shù)計(jì)算步驟如下：

Step6：計(jì)算系統(tǒng)總成本和染色體的適應(yīng)度。

3.4選擇算子

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

輪盤(pán)賭選擇法實(shí)現(xiàn)步驟如下：

Step1：設(shè)第i條染色體的適應(yīng)度為 fi，計(jì)算該染色體被選中的概率

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

Step3：產(chǎn)生一個(gè)服從均勻分布U［0，1］的隨機(jī)數(shù)χ，若χ滿(mǎn)足則第i+1條染色體被選中。

盡管輪盤(pán)賭選擇法簡(jiǎn)單直觀，普遍適用，但該方法也存在諸多不足：在遺傳進(jìn)化初始階段，可能存在適應(yīng)度較高的個(gè)體，在反復(fù)使用輪盤(pán)賭選擇法進(jìn)行選擇時(shí)，會(huì)復(fù)制出大量該染色體的子代，雖然能保證優(yōu)越性，卻會(huì)使種群多樣性迅速喪失。

本文采用一種改進(jìn)的輪盤(pán)賭選擇法：

Step1：設(shè)第i條染色體的適應(yīng)度為 fi，計(jì)算該染色體被選中的概率若 pi＞30% ，則令pi=30%；

通過(guò)對(duì)輪盤(pán)賭選擇法的改進(jìn)，降低了適應(yīng)度高的染色體被選中的概率，有效防止局部過(guò)快收斂。

3.5交叉算子

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

遺傳算法通過(guò)交叉算子產(chǎn)生新的解空間，交叉算子將改進(jìn)的輪盤(pán)賭選擇出來(lái)的兩個(gè)染色體的各個(gè)個(gè)體通過(guò)一定的交叉方法隨機(jī)的交換染色體的某些基因，進(jìn)而產(chǎn)生新染色體的個(gè)體。交叉算子不僅能不斷產(chǎn)生種群的新個(gè)體，還能有效保證種群的多樣性。

由于本文的染色體編碼以?xún)蓚€(gè)基因?yàn)橐唤M，且同一個(gè)計(jì)劃期的路徑編碼不應(yīng)有重復(fù)的出現(xiàn)，因此將代表1個(gè)客戶(hù)和其配送量的2個(gè)基因作為一個(gè)整體進(jìn)行交叉。本文采用整段交換、刪除重復(fù)法來(lái)對(duì)染色體編碼做交叉操作，具體步驟如下：

Step1：假設(shè)染色體編碼有2tn位，產(chǎn)生一個(gè)［1，tn）之間的隨機(jī)整數(shù)χ；

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

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

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

3.6變異算子

變異算子可以使遺傳算法跳出原來(lái)的搜索區(qū)域，避免局部最優(yōu)解，獲得更廣闊的搜索空間來(lái)尋找全局最優(yōu)解。本文先對(duì)代表1個(gè)客戶(hù)和其配送量的2個(gè)基因進(jìn)行整體換位變異，然后對(duì)配送量編碼進(jìn)行變異。

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

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

Step2：隨機(jī)產(chǎn)生一個(gè)服從均勻分布U［0，1］的隨機(jī)數(shù)χ，當(dāng)χ＜p時(shí)，隨機(jī)產(chǎn)生兩個(gè)［1，tn］間的整數(shù)χ1，χ2；

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

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

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

Step2：隨機(jī)產(chǎn)生一個(gè)服從均勻分布U［0，1］的隨機(jī)數(shù)χ，當(dāng)χ＜p時(shí)，隨機(jī)產(chǎn)生一個(gè)［1，tn］間的整數(shù)χ′；

Step3：隨機(jī)產(chǎn)生一個(gè)服從正態(tài)分布N（0，20σ）的隨機(jī)數(shù)φ，令染色體的第2χ個(gè)基因的值加上隨機(jī)數(shù)φ。至此配送量編碼變異完成。

3.7終止變化規(guī)則

遺傳算法是一種隨機(jī)搜索算法，求解過(guò)程是循環(huán)演變的過(guò)程，必須通過(guò)設(shè)定終止進(jìn)化規(guī)則來(lái)讓遺傳算法的迭代過(guò)程停止。本文通過(guò)控制遺傳算法的最大迭代次數(shù)來(lái)判斷是否終止進(jìn)化，即設(shè)定一個(gè)算法的最大迭代次數(shù)N，當(dāng)算法迭代次數(shù)達(dá)到N次，結(jié)束運(yùn)算，輸出結(jié)果。

4　結(jié)論

本文在基本庫(kù)存路徑問(wèn)題的基礎(chǔ)上，深化研究?jī)?nèi)容，考慮隨機(jī)需求的多周期易腐品庫(kù)存路徑問(wèn)題，在一定服務(wù)水平、路徑較優(yōu)的約束下，綜合分析庫(kù)存持有成本、貨損成本、運(yùn)輸成本，決策供應(yīng)鏈的配送路線(xiàn)、配送量。本文還針對(duì)隨機(jī)需求的多周期易腐品庫(kù)存路徑問(wèn)題模型，設(shè)計(jì)了一種改進(jìn)的遺傳算法。該模型可用于水果、蔬菜、生鮮等易隨時(shí)間推移而變質(zhì)或損壞的易腐品的供應(yīng)鏈決策。

［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，F(xiàn)arris 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］劉立輝，葉春明.庫(kù)存路徑問(wèn)題的3種策略［J］.公路交通科技，2009，（12）:137-141.

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

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

［7］李富昌，王勇，張戰(zhàn)峰.考慮第三方物流競(jìng)爭(zhēng)的第四方物流運(yùn)輸與庫(kù)存外包決策［J］.中國(guó)管理科學(xué)，2010，（6）:71-81.

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

Zhang Yi，F(xiàn)u 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-），男，河北石家莊人，北京交通大學(xué)經(jīng)濟(jì)管理學(xué)院物流工程碩士研究生，研究方向：企業(yè)物流運(yùn)作與規(guī)劃；傅少川（1964-），男，山東濰坊人，北京交通大學(xué)經(jīng)濟(jì)管理學(xué)院教授，博士生導(dǎo)師，研究方向：供應(yīng)鏈管理、物流系統(tǒng)規(guī)劃等。