趙 達, 李 軍, 馬丹祥, 李妍峰

(1. 海南大學經(jīng)濟與管理學院, ?？?570228; 2. 華南理工大學工商管理學院, 廣州 510641; 3. 西南交通大學經(jīng)濟管理學院, 成都 610031; 4. 華北理工大學建筑工程學院, 唐山 063009)

?

固定分區(qū)下隨機需求IRP問題最優(yōu)策略及算法①

趙 達1, 2, 李 軍3, 馬丹祥4, 李妍峰3

(1. 海南大學經(jīng)濟與管理學院, ?？?570228; 2. 華南理工大學工商管理學院, 廣州 510641; 3. 西南交通大學經(jīng)濟管理學院, 成都 610031; 4. 華北理工大學建筑工程學院, 唐山 063009)

隨機需求庫存-路徑問題(stochastic demand inventory routing problem, SDIRP)是典型的NP難題，考慮隨機需求環(huán)境下供應鏈中庫存與配送問題的協(xié)調(diào)優(yōu)化，是實施供應商管理庫存策略的關(guān)鍵所在.文章的研究基于固定分區(qū)策略(fixed partition policy，F(xiàn)PP)，在FPP下客戶被分為若干個服務區(qū)域，在同一區(qū)域中的所有客戶均被同時配送.根據(jù)分區(qū)策略對配送以及庫存成本的影響提出了基于修正C-W節(jié)約算法的客戶分區(qū)算法，證明了各區(qū)域的最優(yōu)庫存策略為(s,S)形式，分區(qū)內(nèi)各客戶的庫存策略為order-up-to形式，進而設(shè)計了求解FPP下SDIRP最優(yōu)策略的算法.最后，通過數(shù)值算例驗證了該算法的有效性以及FPP的適用性.

隨機需求庫存-路徑問題； 固定分區(qū)策略； (s,S)策略； order-up-to策略； 修正C-W節(jié)約算法

0 引 言

通常意義下庫存-路徑問題(inventory routing problem, IRP)是指在供應商管理庫存(vendor managed inventory, VMI)模式下，在無限(較長)計劃期內(nèi)，由1個供應商(配送中心)向多個客戶提供補貨配送服務，在滿足一定約束條件(客戶庫存能力、配送車輛數(shù)量及能力等)時，確定各決策階段的庫存策略，即配送對象及其配送數(shù)量，以及相應的配送策略，即配送路徑，使系統(tǒng)平均(折扣)運行成本，包括：庫存持有成本、缺貨損成本、配送成本等最小[1]，其實質(zhì)就是研究庫存補充和配送之間的協(xié)調(diào)問題[2].由此可見，有效解決IRP是實施VMI，削弱牛鞭效應、降低供應鏈運行成本的關(guān)鍵所在.同時，IRP還是典型的NP-hard問題[3]，在客戶數(shù)量較多、需求不確定的情況下求解難度更大.因此，對于IRP的研究具有很強的現(xiàn)實意義和理論價值.

由于IRP的復雜性，使其最優(yōu)策略的求解十分困難，即使最優(yōu)策略存在往往也十分復雜，不具備穩(wěn)定的配送間隔、路線或配送數(shù)量，導致其實施難度較大[4-5]，而隨機需求IRP(stochastic demand inventory routing problem, SDIRP)的最優(yōu)策略更是只在一些特殊情形下存在.因此，研究更有實施效率的近優(yōu)平穩(wěn)策略*所謂平穩(wěn)策略是指策略的形式、參數(shù)不隨決策階段、歷史以及當前狀態(tài)等因素的變化而改變的一類策略[6].具有重要的實際意義.在對確定需求IRP的研究中，很多學者提出了一類基于固定分區(qū)策略(fixed partition policy, FPP)的平穩(wěn)策略，在FPP下把客戶劃分為若干個服務區(qū)域，不同區(qū)域中的客戶相互獨立地接受配送中心的服務，且同一區(qū)域中所有客戶均由同一車輛提供配送服務，即當區(qū)域中存在需要配送的客戶時，配送車輛則同時服務該區(qū)域中的所有客戶[4-5，7-11].采用FPP后各客戶分區(qū)之間的決策相互獨立，因此，IRP可根據(jù)分區(qū)情況被分解為若干個相互獨立的子問題進行處理，從而有效地降低了求解的難度，同時也增加了優(yōu)化策略的可實施性.

在現(xiàn)有的相關(guān)文獻中，Anily和Federgruen[4]研究了客戶需求可分割條件下基于分區(qū)策略的確定需求IRP，即先將客戶按照標準的需求單位分為若干個需求點，而后再將需求點進行分區(qū)的策略.文章給出了在上述策略下IRP成本的上、下界，證明了該上、下界具有漸進優(yōu)化性，并以此為基礎(chǔ)設(shè)計了相應的求解算法.文獻[4]是IRP研究領(lǐng)域較早引入分區(qū)思想的文獻，其中考慮的分區(qū)策略將客戶分為多個需求點，但上述處理方式使得1個客戶由多輛車提供服務，既提高了實際操作的難度也增加了運作管理的成本.Bramel和Simchi-Levi[7]以及Chan等[8]改進了文獻[4]中分區(qū)策略的不足，要求客戶只能屬于唯一分區(qū)，即FPP策略，在此基礎(chǔ)上將客戶的分區(qū)問題轉(zhuǎn)化為求解較為成熟的約束集線器選址問題(capacitated concentrator location problem, CCLP)，而后通過最近鄰插入法確定不同區(qū)域內(nèi)的路徑安排，從而得到確定需求IRP的解，并且證明了上述結(jié)果在一定條件下具有漸進優(yōu)化性.此外，Anily和Bramel[5]給出了FPP下確定需求IRP的98.5%有效的成本下界，從而為評估不同F(xiàn)PP對IRP的優(yōu)化效果提供了依據(jù).

在近期研究中，Zhao等[9-10]分別考慮了同時采用FPP以及二次冪庫存策略的2層(配送中心和客戶)以及3層(外部供應商、配送中心和客戶)供應鏈系統(tǒng)中的確定需求IRP，并分別提出了對應的表搜索以及可變大規(guī)模鄰域搜索算法.Li等[11]考慮了允許外部供應商直接對客戶進行配送服務的3層供應鏈確定需求IRP，基于FPP將上述問題分解為外部供應商對客戶、配送中心對客戶以及外部供應商對配送中心進行服務3個子問題，并設(shè)計了相應的遺傳算法對其進行求解.Michel和Vanderbeck[12]采用列生成技術(shù)在戰(zhàn)術(shù)層面上求解了FPP下確定需求的揀貨型IRP.通過上述分析，不難看出現(xiàn)有文獻著重對于FPP有效性以及FPP下不同結(jié)構(gòu)IRP的優(yōu)化算法這兩類問題進行了研究.但上述研究均是在客戶需求確定的假設(shè)下進行的，而將FPP應用到解決更貼近實際的SDIRP，并討論其最優(yōu)策略形式的文獻卻十分罕見.但是，F(xiàn)PP可以有效降低優(yōu)化策略求解難度和實施難度[13]的特點對于SDIRP更具意義.因此，F(xiàn)PP下SDIRP的相關(guān)研究具有很強的理論和現(xiàn)實必要性.

與確定需求IRP的兩階段求解過程不同，本文將FPP下SDIRP的求解過程分為3個階段，除了客戶分區(qū)階段以及路線安排階段之外[4-5，7-12]，由于客戶所面對需求的隨機性，還需加入確定客戶庫存策略階段.與文獻[7]、文獻[8]將客戶分區(qū)問題轉(zhuǎn)化為CCLP加以解決的方法不同，本文首先根據(jù)客戶需求隨機的特性以及分區(qū)對配送及庫存成本的影響，提出了基于修正C-W法的客戶分區(qū)算法；證明了各分區(qū)的最優(yōu)庫存策略為(s,S)形式，分區(qū)內(nèi)各客戶的最優(yōu)庫存策略為order-up-to形式，并設(shè)計了相應的最優(yōu)策略求解算法；進而通過求解旅行商問題(traveling salesman problem, TSP)以確定各分區(qū)的配送路徑.最后，通過數(shù)值算例驗證了上述算法的有效性，并討論了FPP在求解SDIRP中的適用性以及不同分區(qū)方法對算法的影響.

1 問題描述

1.1 問題的基本描述

考慮一個采用VMI庫存管理模式的物流系統(tǒng)，1個配送中心為n個已知地理位置的客戶提供某種產(chǎn)品，令:N={1,2,…,n}表示客戶集合；dij(i,j∈N∩{0})表示客戶i到客戶j的最短距離，其中0表示配送中心，并假設(shè)不考慮配送中心的供應能力限制及其相應的庫存成本[1-5，7-8，12].客戶每天面對的需求量為一組穩(wěn)定的獨立同分布隨機變量ui(i∈N)，其密度函數(shù)為fi(·)；同時，每個客戶的最大庫存容量為Ci，且假設(shè)車輛的配送能力CV至少可以滿足1個客戶的需求.配送中心首先基于FPP對客戶進行分區(qū)，并在每階段(每天)市場需求到達之前，根據(jù)客戶的歷史需求數(shù)據(jù)及庫存信息對各分區(qū)中的客戶進行服務.

1.2 問題的成本結(jié)構(gòu)

上述物流系統(tǒng)中每階段的運行成本包括：配送成本、庫存持有成本以及由于客戶需求隨機而引起的缺貨損失成本.其中，由于配送中的固定成本，如：車輛購置成本、人員工資等均屬于沉沒成本，因此本文中的配送成本僅考慮與行駛距離有關(guān)的可變成本，并假設(shè)該可變成本是車輛行駛距離的線性函數(shù)，直接用車輛行駛距離表示；同時，假設(shè)客戶每天的庫存持有成本與客戶當天的剩余庫存量成正比，如客戶i的單位持有成本為hi，其配送前的庫存水平為xi，且當天到達的配送量為qi，則該客戶庫存持有成本為hi(max{yi-ui,0})，其中yi=xi+qi；最后，假設(shè)缺貨損失成本與缺貨量成正比，如客戶i的單位缺貨損失成本為pi則其缺貨損失成本為pi(max{ui-yi,0}).此外，由于該系統(tǒng)處于VMI庫存管理模式下，并不存在客戶的訂貨成本.因此，令函數(shù)Gi(yi)表示當客戶i的庫存水平為xi，配送量為qi時，其單階段的期望庫存成本(持有成本與缺貨損失成本之和)，則

(1)

其中為了貼近實際，假設(shè)客戶的基本參數(shù)均可保證無限量訂貨或者無限量缺貨策略是策略集中的絕對劣勢策略，即參數(shù)pi,hi的關(guān)系為0

2 確定客戶分區(qū)

根據(jù)文獻[4]、文獻[7]以及文獻[8]，即使在客戶需求確定條件下，求解客戶最優(yōu)分區(qū)也是一個NP-hard問題，文獻[7]、文獻[8]中將該問題轉(zhuǎn)化為另一類較為成熟的組合優(yōu)化問題CCLP，通過對其進行求解從而確定客戶分區(qū)方案，但在上述方法中由于客戶需求已知，其僅以客戶的地理位置作為分區(qū)的主要依據(jù)，并沒有考慮不同分區(qū)方案對于客戶庫存的影響，而在隨機需求環(huán)境下，上述兩個因素的作用均不能忽略，因此本文同時考慮分區(qū)對庫存以及配送成本的影響，提出了修正的C-W節(jié)約算法，在保證對路徑進行優(yōu)化的前提下，將分區(qū)對于庫存成本的影響也加入其中.

2.1 修正的C-W節(jié)約算法

經(jīng)典的C-W節(jié)約法不但可以對配送路徑進行優(yōu)化，同時也將配送對象進行了分區(qū).該算法的核心在于提出了節(jié)約值Sij概念.根據(jù)文獻[14]，在經(jīng)典的節(jié)約值定義中只考慮了不同的配送(分區(qū))方式對于配送成本的影響，然而在基于FPP的SDIRP中配送(分區(qū))方式不僅對客戶的配送成本同時也會對其庫存成本產(chǎn)生影響，因此有必要對節(jié)約值進行重新定義.

圖1 a) 直接配送的情況

圖1 b) 共同配送的情況

(2)

由于SDIRPDD特殊的配送方式，使得此類問題的配送策略已經(jīng)確定且各客戶的配送成本退化為常量，此時該問題最優(yōu)策略的形式完全由客戶的庫存策略形式?jīng)Q定.同時，在沒有車輛數(shù)約束的條件下該問題中每個客戶之間的決策是相互獨立的，因此可以將該問題以客戶為單位分為n個獨立的子問題，并給出如下引理：

引理 在不考慮配送車輛數(shù)和客戶庫存容量約束的條件下，SDIRPDD子問題與有訂貨成本的無限階段隨機需求庫存問題*無限階段隨機需求庫存問題是一類經(jīng)典問題，從Scarf 1960年開始包括Federgruen[15]、Zheng[16]等眾多學者對該問題最優(yōu)策略的形式及其算法進行了研究，其中文獻[16]給出的算法更被認為是求解此類問題的標準算法.等價，最優(yōu)策略形式均為(si,Si),(i=1,2,…,n)結(jié)構(gòu)，且SDIRPDD最優(yōu)策略由上述子問題最優(yōu)策略構(gòu)成，其形式為{(s1,S1),(s2,S2),…,(si,Si),…,(sn,Sn)}*引理的證明詳見文獻[17]..

(3)

其中η表示客戶在1個庫存周期內(nèi)可能的需求量；更新方程Mi(·)、mi(·)的表達式為

(4)

(5)

(6)

(7)

(8)

其中式(3)、式(7)以及式(8)中各客戶相應的最優(yōu)s、S參數(shù)值均可通過文獻[16]中的算法得到.

3 確定最優(yōu)庫存策略

客戶分區(qū)確定后，在確定需求IRP中各客戶每階段需要的配送量也隨即確定[5-7，12]，但由于SDIRP中客戶需求的隨機性使得確定各客戶在不同階段中的配送量也十分困難.因此，確定每個客戶的庫存策略就成為解決SDIRP的關(guān)鍵.此外，由于使用FPP，使得每個分區(qū)的庫存策略成為確定獨立客戶庫存策略的基礎(chǔ)，因此，本文首先對FPP下SDIRP中各分區(qū)的最優(yōu)庫存策略進行討論.

3.1 分區(qū)的最優(yōu)庫存策略

根據(jù)引理以及FPP下SDIRP各客戶分區(qū)的庫存最優(yōu)平穩(wěn)策略與SDIRPDD最優(yōu)策略之間的對應關(guān)系，不難給出如下命題：

3.2 客戶的最優(yōu)庫存策略

(9)

此時，通過求解如下的非線性規(guī)劃問題即可確定在分區(qū)Sr中各客戶的最優(yōu)配送量

(10)

(11)

采用拉格朗日松弛法求解上述規(guī)劃，令

(12)

整理得到

(13)

(14)

(15)

(16)

(17)

(18)

同理，將式(18)代入約束(11)得到如下關(guān)于λSr的非線性方程

(19)

(20)

根據(jù)式(17)～式(20)即可確定任一分區(qū)內(nèi)任意客戶的最優(yōu)庫存策略.

4 基于FPP的SDIRP最優(yōu)策略及其算法

根據(jù)命題1、命題2，可以給出基于FPP對客戶進行分區(qū)后，SDIRP問題的最優(yōu)策略結(jié)構(gòu)如下.

根據(jù)上述對FPP下SDIRP問題最優(yōu)策略形式的分析，以及本文2、3節(jié)對于客戶分區(qū)算法以及客戶最優(yōu)庫存策略的討論，可以得到求解FPP下SDIRP最優(yōu)策略的啟發(fā)式算法，基本步驟如下：

步驟0 令指標變量α=0；

步驟1 對于?j∈N，為了保證得到的分區(qū)中客戶的配送總量在任意決策階段均滿足配送車輛的容量限制，令客戶的配送量qj為其配送量的上限，即qj=Cj，并采用修正的C-W節(jié)約算法對客戶集合進行分區(qū)，得到客戶分區(qū)方案P(α)；

步驟7 如果P(α+1)≠P(α)，則令α:=α+1并轉(zhuǎn)入步驟2；如果P(α+1)=P(α)，則轉(zhuǎn)入步驟8；

步驟8 在分區(qū)方案P(α)下，根據(jù)文獻[22]、文獻[23]中的算法計算任意分區(qū)Sr的最優(yōu)TSP路徑，算法終止.

5 算例分析

本文中由于客戶需求量相對于車輛配送能力而言較小，根據(jù)文獻[24]的相關(guān)結(jié)論，此時客戶需求假設(shè)服從Poisson分布較為合理，其中Poisson分布的均值μ可以通過客戶需求的到達強度和每個需求的平均需求量得到.因此，本文隨機生成了10個需求服從Poisson分布的客戶需求信息以及每個客戶的地理位置信息(見表1、表2)，同時，假設(shè)車輛的配送能力CV為40.

表1 客戶基礎(chǔ)信息

表2 客戶地理位置信息

5.1 虛擬客戶參數(shù)的估計

命題4 在分區(qū)Sr中客戶i(i∈Sr)的需求均值μi占虛擬客戶r的需求均值μSr的比例越大，其單位庫存持有成本hi(單位缺貨損失成本pi)在虛擬客戶r的相應單位成本中所占的比例則越小(大).

(21)

同時，如采用分區(qū)Sr中各客戶的單位庫存hi(i∈Sr)進行計算，則其表達式為

(22)

通過式(21)、式(22)不難得到，虛擬客戶r的單位庫存持有成本hSr的表達式為

(23)

(24)

此時，令虛擬客戶r的需求uSr固定，客戶i的需求ui變大，即均值μi變大；不難發(fā)現(xiàn)，式(24)中分母不變，分子減小，即客戶i的需求均值μi占虛擬客戶r的需求均值μSr的比例越大，其單位庫存持有成本hi在虛擬客戶r的相應單位成本hSr中所占的比例越小.

同理，可以得到虛擬客戶r的單位缺貨損失成本pSr的表達式為

(25)

(26)

此時，若固定虛擬客戶r的需求uSr，加大客戶i的需求ui.不難發(fā)現(xiàn)，式(26)中的分母不變，分子增大，即客戶i的需求均值μi占虛擬客戶r的需求均值μSr的比例增大，其單位缺貨損失成本pi在虛擬客戶r的相應單位成本pSr中所占的比例也增大，命題得證.

為了驗證通過上述方式給出的虛擬客戶相關(guān)參數(shù)估計方法的效果，將上述方法與簡單平均法進行比較，采用文中算法計算FPP下SDIRP的優(yōu)化策略并進行模擬得到系統(tǒng)運行1年后的日平均成本，具體策略及相應成本如表3所示.

表3 參數(shù)估計方法對算法的影響

根據(jù)表3不難發(fā)現(xiàn)，參數(shù)估計方法對于得到的優(yōu)化策略具有一定影響，在本例中雖然采用不同參數(shù)估計方法得到的客戶分區(qū)沒有變化，但由于最優(yōu)策略不同使得系統(tǒng)平均成本變化在4.5%左右；同時，采用本文方法進行估計時得到的平均成本更低，在一定程度上說明了該方法的有效性.因此，在后續(xù)的算例中均以此方法作為基礎(chǔ)進行討論.

5.2 算法有效性分析

首先，為了說明文中客戶分區(qū)算法的有效性，將本文提出的基于修正C-W節(jié)約法的客戶分區(qū)算法與文獻[7]、文獻[8]中采用的CCLP方法進行比較.其中，采用CCLP方法對客戶進行分區(qū)后，仍按照本文中的結(jié)論計算SDIRP的最優(yōu)策略.同時，將通過上述兩種分區(qū)算法得到的SDIRP最優(yōu)策略進行模擬，得到系統(tǒng)運行1年后的日平均成本，如表4所示.

表4 不同分區(qū)算法的比較

通過表4不難發(fā)現(xiàn)，采用修正C-W節(jié)約算法進行客戶分區(qū)后得到的系統(tǒng)日平均運行成本比CCLP方法降低了5.9%，從而驗證了CCLP用于隨機需求客戶分區(qū)時沒有考慮庫存因素的理論局限性，同時也說明了本文提出的客戶分區(qū)算法在上述方面的改進.

此外，雖然FPP在解決確定需求IRP時被廣泛使用，但該策略在解決SDIRP時的有效性卻沒有相關(guān)的研究，因此有必要對FPP應用在SDIRP上的效果進行驗證.為了對FPP以及文中最優(yōu)策略的有效性進行分析，將本文的求解算法與使用均值確定化處理后根據(jù)文獻[7]得到的FPP下SDIRP的求解算法以及文獻[3]中基于馬爾可夫決策過程(Markov decision process, MDP)的啟發(fā)式算法進行比較.根據(jù)表1、表2中的數(shù)據(jù)，分別采用上述3種算法得到SDIRP的優(yōu)化策略并進行模擬，得到系統(tǒng)運行1年后的日平均成本，如表5所示.

表5 FPP以及算法有效性比較

根據(jù)表5可知，通過本文算法得到的FPP下SDIRP的最優(yōu)策略與通過同樣采用FPP的文獻[7]得到的同一問題的策略相比，在基本相同的運算成本下系統(tǒng)平均運行成本降低了20.3%；說明本文給出的最優(yōu)策略及其算法，與同樣采用FPP的文獻相比具有明顯的優(yōu)越性；此外，與通過文獻[3]中算法得到的不采用FPP時同一問題的策略相比，系統(tǒng)平均運行成本提高6.8%.但如果以相同計算環(huán)境下模擬系統(tǒng)平均運行成本所用的CPU時間衡量兩種策略的實施和管理成本，則采用FPP后該項成本顯著降低了78.49%.此外，采用FPP后SDIRP的最優(yōu)策略屬于平穩(wěn)策略類，且文中算法的計算復雜性并不會隨客戶規(guī)模的增加而顯著變化；但文獻[3]中采用MDP模型得到的配送策略并不穩(wěn)定，且其計算復雜性對客戶規(guī)模、客戶的庫存容量等數(shù)據(jù)十分敏感，當系統(tǒng)中的客戶數(shù)量以及客戶庫存容量較大時其算法將很難實現(xiàn).因此，實際SDIRP中FPP的使用可以有效地增加算法的適用范圍，同時保證在滿意的運行成本前提下，顯著降低策略的相關(guān)實施、管理成本.

6 結(jié)束語

[1]Federgruen A, Zipkin P. A combined vehicle routing and inventory allocation problem[J]. Operations Research, 1984, 32(5): 1019-1036.

[2]Qu W W, Bookbinder J H, Iyogun P. An integrated inventory-transportation system with modified periodic policy for multiple products[J]. European Journal of Operational Research, 1999, 115(2): 254-269.

[3]趙 達, 李 軍, 馬丹祥. 求解隨機需求庫存-路徑問題的一種算法[J]. 系統(tǒng)工程, 2006, 24(5): 23-28. Zhao Da, Li Jun, Ma Danxiang. An algorithm for stochastic demand inventory routing problem[J]. Systems Engineering, 2006, 24(5): 23-28.(in Chinese)

[4]Anily S, Federgruen A. One warehouse multiple retailer systems with vehicle routing costs[J]. Management Science, 1990, 36(1): 92-114.

[5]Anily S, Bramel J. An asymptotic 98.5%-effective lower bound on fixed partition policies for the inventory-routing problem[J]. Discrete Applied Mathematics, 2004, 145(1): 22-39.

[6]劉 克. 實用馬爾可夫決策過程[M]. 北京: 清華大學出版社, 2004: 9-11. Liu Ke. Applied Markov Decision Processes[M]. Beijing: Tsinghua University Press, 2004: 9-11. (in Chinese)

[7]Bramel J, Simchi-Levi D. A location based heuristic for general routing problems[J]. Operational Research, 1995, 43(4): 649-660.

[8]Chan L, Federgruen A, Simchi-Levi D. Probabilistic analyses and practical algorithms for inventory-routing models[J]. Operational Research, 1998, 46(1): 96-106.

[9]Zhao Q H, Wang S Y, Lai K K. A partition approach to the inventory/routing problem[J]. European Journal of Operational Research, 2007, 177(2): 786-802.

[10]Zhao Q H, Chen S, Zang C X. Model and algorithm for inventory/routing decision in a three-echelon logistics system[J]. European Journal of Operational Research, 2008, 191(3): 623-635.

[11]Li J X, Chu F, Chen H X. A solution approach to the inventory routing problem in a three-level distribution system[J]. European Journal of Operational Research, 2011, 210(3): 736-744.

[12]Michel S, Vanderbeck F. A column-generation based tactical planning method for inventory routing[J]. Operational Research, 2012, 60(2): 382-397.

[13]陳久梅, 張旭梅, 肖 劍，等. 隨機動態(tài)裝卸混合問題的分區(qū)求解策略[J]. 管理科學學報, 2012， 15(1): 43-53. Chen Jiumei, Zhang Xumei, Xiao Jian, et al. Region partitioning policy for stochastic dynamic pick-up and delivery problem[J]. Journal of Management Sciences in China, 2012， 15(1): 43-53. (in Chinese)

[14]李 軍， 郭耀煌. 物流配送-車輛優(yōu)化調(diào)度理論與方法[M]. 北京: 中國物資出版社, 2001: 78-80. Li Jun，Guo Yaohuang. Logistics-Vehicle Schedule Optimization Theories and Methods[M]. Beijing: China Logistics Publishing House, 2001: 78-80. (in Chinese)

[15]Federgruen A, Zipkin P. An efficient algorithm for computing optimal (s, S) policies[J]. Operational Research, 1984, 32(6): 1268-1285.

[16]Zheng Y S, Federgruen A. Finding optimal (s, S) policies is about as simple as evaluating a single policy[J]. Operations Research, 1991, 39(4): 654-665.

[17]趙 達, 李 軍, 馬丹祥, 等. 隨機需求庫存-路徑問題最優(yōu)策略及其算法[J]. 管理科學學報, 2014, 17(5): 14-24. Zhao Da, Li Jun, Ma Danxiang, et al. Optimal strategy of stochastic demand inventory routing problem and algorithms[J]. Journal of Management Sciences in China , 2014, 17(5): 14-24. (in Chinese)

[18]Federgruen A, Zipkin P. An inventory model with limited production capacity and uncertain demands I. The average-cost criterion[J]. Mathematics of Operations Research, 1986, 11(2): 193-207.

[19]Chen S X, Lambrecht M. X-Y band and modified (s, S) policy[J]. Operations Research, 1996, 44(6): 1013-1019.

[20]Ross M. Introduction to Probability Models (Tenth Edition )[M]. Academic Press, 2010: 455-457.

[21]Brent R. An algorithm with guaranteed convergence for finding a zero of a function[J]. The Computer Journal, 1971, 14(4): 422-425.

[22]李 峰. 基于偏好信息的多目標旅行商問題Pareto優(yōu)化求解[J]. 系統(tǒng)工程學報, 2011, 26(5): 592-598. Li Feng. Preference-based Pareto optimization of multi-objective traveling salesman problems[J]. Journal of Systems Engineering, 2011, 26(5): 592-598. (in Chinese)

[23]李妍峰, 李 軍, 高自友. 大規(guī)模鄰域搜索算法求解時變車輛調(diào)度問題[J]. 管理科學學報, 2012 15(1): 23-32. Li Yanfeng, Li Jun, Gao Ziyou. Very large scale neighborhood search algorithm for solving time dependent vehicle routing problem[J]. Journal of Management Sciences in China, 2012, 15(1): 23-32. (in Chinese)

[24]Axsater S. 庫存控制[M]. 北京: 清華大學出版社, 2007: 77. Axsater S. Inventory Control[M]. Beijing: Tsinghua University Press, 2007: 77. (in Chinese)

Optimal strategy and algorithm of stochastic demand inventory routing problem under fixed partition policy

ZHAODa1, 2,LIJun3,MADan-xiang4,LIYan-feng3

1. School of Economics and Management, Hainan University, Haikou 570228, China;2. School of Business Administration, South China University of Technology, Guangzhou 510641, China;3. School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China;4. College of Civil and Architectural Engineering, North China University of Science and Technology, Tangshan 063009, China

The stochastic demand inventory routing problem (SDIRP) is a typical NP-hard problem. It is alsothe key to implementing vendor managed inventory (VMI) strategy, that is, to coordinate the inventory problem and distribution problem in a stochastic demand environment. This paper studies the SDIRP based on the Fixed Partition Policy (FPP). Under this policy, customers are partitioned according to the service regions they are in, and customers who are in the same service region are served simultaneously. In this paper, a modified C-W saving algorithm is designed to partition customers, taking into account the impact of partition policy on inventory costs and distribution costs. It is shown that the optimal inventory policy for individual service region is a (s,S) policy, whereas the inventory policy for customers in each service region is an order-up-to policy. Furthermore, this paper proposes an algorithm to solve SDIRP based on FPP. Finally, a numerical example is presented to confirm the efficiency and applicability of the proposed algorithm.

SDIRP; FPP; (s,S) policy; order-up-to policy; modified C-W saving algorithm

2012-08-09；

2016-08-10.

國家自然科學基金資助項目(71361006； 71271178； 71131003)； 中西部綜合能力提升計劃資助項目(海南大學， ZXBJH-XK022)； 中國博士后科學基金資助項目(2014M552205)； 教育部人文社會科學研究一般資助項目(12YJA630057)； 海南省自然科學基金資助項目(714257； 20157263).

趙 達(1980—)， 男， 河北易縣人， 博士， 副教授， 碩士生導師. Email： zhaoda2002@vip.sina.com

F253.4

A

1007-9807(2016)12-0025-11