航空公司機(jī)上周轉(zhuǎn)品多基地庫(kù)存優(yōu)化模型

宋江海，池 宏，高敏剛

(1.中國(guó)科學(xué)院科技戰(zhàn)略咨詢研究院，北京 100190；2.中國(guó)科學(xué)院大學(xué)，北京 100049)

1 引言

隨著高鐵的普及、電子商務(wù)的飛速發(fā)展，使得航空公司的競(jìng)爭(zhēng)日益激烈，成本控制成為航空公司增強(qiáng)市場(chǎng)競(jìng)爭(zhēng)力的關(guān)鍵，加強(qiáng)對(duì)各項(xiàng)運(yùn)營(yíng)成本的控制顯得尤為重要。

機(jī)上周轉(zhuǎn)品是航空公司為旅客提供的且能進(jìn)行反復(fù)清洗回收使用的餐食用品及用具、盥洗用品及用具，如瓷器、玻璃制品、餐車、毛巾等。大型的航空公司為保障生產(chǎn)運(yùn)營(yíng)，一般在多個(gè)重要機(jī)場(chǎng)設(shè)有基地(或分公司)。由于往返航班配備的機(jī)上周轉(zhuǎn)品數(shù)量不同，容易導(dǎo)致一些基地倉(cāng)庫(kù)出現(xiàn)積壓而另一些基地倉(cāng)庫(kù)產(chǎn)生短缺；加之，對(duì)整個(gè)機(jī)上周轉(zhuǎn)品的庫(kù)存系統(tǒng)缺乏有效的信息共享及調(diào)運(yùn)機(jī)制，使得機(jī)上周轉(zhuǎn)品的訂貨成本一直居高不下。

目前民航領(lǐng)域關(guān)于機(jī)上周轉(zhuǎn)品的研究相對(duì)較少，并且缺乏定量的模型分析。趙桂紅和馬志剛[1]針對(duì)機(jī)供品的組成、特點(diǎn)以及在成本控制方面存在的問(wèn)題，提出了不同類型的機(jī)供品成本控制的解決方案。谷偉強(qiáng)[2]以某航空公司自主開(kāi)發(fā)的“機(jī)供品管理平臺(tái)”為例，分析了機(jī)供品管理信息系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)的全過(guò)程。

與機(jī)上周轉(zhuǎn)品類似的物品有托盤(pán)、集裝箱等，那么關(guān)于此類物品的研究大多集中在如何進(jìn)行調(diào)度方面。有些專家很早就提出建立共用系統(tǒng)來(lái)解決托盤(pán)回收再利用問(wèn)題[3-4]，但對(duì)于托盤(pán)共用系統(tǒng)中如何合理地進(jìn)行回收、調(diào)度等研究還有待深入。任建華和章雪巖[5-7]針對(duì)托盤(pán)共用系統(tǒng)的回收問(wèn)題，分別考慮到供給、需求、運(yùn)輸和裝卸能力等因素的隨機(jī)不確定性，提出了幾個(gè)托盤(pán)共用隨機(jī)規(guī)劃模型，并采用機(jī)會(huì)約束規(guī)劃方法對(duì)其進(jìn)行求解。而對(duì)于托盤(pán)共用系統(tǒng)調(diào)度的全過(guò)程(購(gòu)買(mǎi)或租借、分派、再分派、回收)，任建華等[8]綜合考慮損壞率、整車運(yùn)輸?shù)缺姸鄻O端不確定性因素，構(gòu)建了一個(gè)混合型號(hào)托盤(pán)的托盤(pán)共用系統(tǒng)調(diào)度多情景規(guī)劃模型，該模型能夠幫助托盤(pán)共用系統(tǒng)管理者在沒(méi)有充足歷史數(shù)據(jù)情況下制定有效的托盤(pán)調(diào)度方案。吉清凱等[9]從管理層次、運(yùn)輸方式及研究方法等多角度對(duì)國(guó)內(nèi)外關(guān)于集裝箱的空箱調(diào)度研究進(jìn)行了綜述，并提到復(fù)雜空箱物流中的庫(kù)存控制策略將是未來(lái)的發(fā)展方向之一。Li等[10]將多港口的空箱調(diào)度問(wèn)題看作成具有正負(fù)需求的多階段庫(kù)存問(wèn)題，提出了一種臨界策略，并用啟發(fā)式算法進(jìn)行了求解。施欣[11]通過(guò)對(duì)海運(yùn)集裝箱空箱流轉(zhuǎn)過(guò)程的分析，建立了空箱調(diào)運(yùn)模型，并通過(guò)數(shù)字仿真分析了成本參數(shù)及載運(yùn)能力對(duì)空箱調(diào)運(yùn)策略的影響。計(jì)明軍等[12]針對(duì)沿海港口間的空箱調(diào)運(yùn)問(wèn)題，提出了一種不確定目的港的空箱調(diào)運(yùn)策略，建立了以總調(diào)運(yùn)費(fèi)用最小為目標(biāo)的規(guī)劃模型，采用遺傳算法進(jìn)行求解。卜祥智等[13]基于收益管理的思想，考慮海運(yùn)集裝箱需求的隨機(jī)性，分別建立了考慮和不考慮空箱調(diào)運(yùn)的集裝箱艙位分配隨機(jī)規(guī)劃模型，并采用穩(wěn)健優(yōu)化的方法轉(zhuǎn)化為確定性整數(shù)規(guī)劃模型進(jìn)行求解。

而對(duì)于物流網(wǎng)絡(luò)中同級(jí)節(jié)點(diǎn)(比如庫(kù)存節(jié)點(diǎn)、銷售節(jié)點(diǎn)等)間的相互調(diào)貨在研究中被稱作庫(kù)存共享或橫向轉(zhuǎn)運(yùn)。這種策略可以降低整個(gè)系統(tǒng)的缺貨成本和庫(kù)存成本，同時(shí)提高系統(tǒng)的服務(wù)水平(降低缺貨率)，關(guān)于此類問(wèn)題的綜述性文獻(xiàn)可見(jiàn)Paterson等[14]。針對(duì)不同倉(cāng)儲(chǔ)物品的特性，學(xué)者們的研究主要集中在備件的庫(kù)存共享與消耗品的庫(kù)存共享。最早關(guān)于備件的庫(kù)存共享研究是Sherbrooke提出的METRIC模型[15]，該模型針對(duì)航空領(lǐng)域可修復(fù)件，假設(shè)需求服從泊松分布，基于(S-1,S)的補(bǔ)貨策略求得最佳的庫(kù)存水平。Seidscher和Minner[16]針對(duì)備件的多點(diǎn)庫(kù)存系統(tǒng)，基于one-for-one訂貨策略和需求服從泊松分布下，提出了一個(gè)半馬爾科夫決策模型，并分別采用主動(dòng)轉(zhuǎn)運(yùn)和被動(dòng)轉(zhuǎn)運(yùn)策略進(jìn)行分析。戢守峰等[17]針對(duì)三級(jí)備件分銷網(wǎng)絡(luò)，構(gòu)建了考慮庫(kù)存共享和服務(wù)水平限制下的橫向轉(zhuǎn)運(yùn)模型，并針對(duì)模型具有非線性和復(fù)雜性的特點(diǎn)設(shè)計(jì)了貪婪算法進(jìn)行了求解。Archibald[18]假設(shè)備件需求滿足二項(xiàng)分布，構(gòu)建了一個(gè)基于周期性檢查補(bǔ)貨策略的多點(diǎn)庫(kù)存模型，分析了最優(yōu)訂貨和調(diào)運(yùn)策略的特點(diǎn)，并設(shè)計(jì)了三種簡(jiǎn)便的啟發(fā)式調(diào)運(yùn)策略。Wong等[19]考慮橫向轉(zhuǎn)運(yùn)時(shí)間限制及延遲情形，構(gòu)建了一個(gè)可完全共享的多點(diǎn)可修復(fù)庫(kù)存模型，并轉(zhuǎn)化成一個(gè)多維的馬爾科夫模型進(jìn)行求解。而最早關(guān)于消耗品的庫(kù)存共享問(wèn)題研究是Allen提出的[20]，他考慮了一個(gè)在多個(gè)庫(kù)存點(diǎn)之間的庫(kù)存分配問(wèn)題，各庫(kù)存點(diǎn)的需求是獨(dú)立隨機(jī)的，在某一時(shí)點(diǎn)通過(guò)運(yùn)輸對(duì)各庫(kù)存點(diǎn)的庫(kù)存量進(jìn)行重新分配，使得總的運(yùn)輸及未來(lái)缺貨成本最小。Herer和Michal[21-22]針對(duì)消耗品，研究其在多個(gè)基地間的動(dòng)態(tài)調(diào)運(yùn)問(wèn)題，在已知總訂貨量等于總需求量下，分別考慮固定訂貨成本、固定運(yùn)輸成本等限制條件，構(gòu)建了多周期的動(dòng)態(tài)調(diào)運(yùn)模型，并借鑒Wagner和Whitin動(dòng)態(tài)優(yōu)化方法[23]，設(shè)計(jì)了一個(gè)最優(yōu)的求解算法對(duì)每個(gè)階段的訂貨量和調(diào)運(yùn)量進(jìn)行求解。?zdemir等[24]研究了一個(gè)消耗品的多點(diǎn)庫(kù)存系統(tǒng)，在已知各點(diǎn)的隨機(jī)需求，考慮供應(yīng)商生產(chǎn)能力限制，構(gòu)建了一個(gè)隨機(jī)型的多周期的調(diào)運(yùn)模型，并采用樣本均值逼近方法(SAA)進(jìn)行了求解。以上研究都是基于多點(diǎn)間可以相互調(diào)運(yùn)的情形，而對(duì)于單向的橫向調(diào)運(yùn)問(wèn)題，Axs?ter、Olsson等學(xué)者也進(jìn)行了深入的研究[25-26]。還有些學(xué)者從不同的角度對(duì)多基地的庫(kù)存共享問(wèn)題進(jìn)行了研究。陳敬賢和孟慶峰[27]針對(duì)兩個(gè)銷售商的庫(kù)存系統(tǒng)，構(gòu)建了一個(gè)應(yīng)對(duì)突發(fā)事件的非合作博弈模型，證明了其納什均衡解的唯一存在性，并設(shè)計(jì)了一個(gè)啟發(fā)式的求解算法。

以上研究主要考慮在庫(kù)存系統(tǒng)中遇到的各種不確定性因素，去解決回收再利用過(guò)程中的一次性調(diào)度問(wèn)題；或針對(duì)備件或消耗品在不同特征下的多點(diǎn)庫(kù)存系統(tǒng)，研究其補(bǔ)貨或調(diào)運(yùn)策略。而本文考慮的是航空公司機(jī)上周轉(zhuǎn)品的多基地庫(kù)存系統(tǒng)，研究其在一個(gè)訂貨周期內(nèi)的動(dòng)態(tài)補(bǔ)貨問(wèn)題，決策期初的訂貨方案以及周期內(nèi)的調(diào)運(yùn)方案，實(shí)現(xiàn)庫(kù)存共享和降低成本。構(gòu)建了一個(gè)庫(kù)存優(yōu)化模型，分析了最優(yōu)解的性質(zhì)，并設(shè)計(jì)了相應(yīng)的算法進(jìn)行求解，通過(guò)算例驗(yàn)證了方法的有效性。

2 問(wèn)題與模型構(gòu)建

2.1 問(wèn)題描述

某航空公司擁有多個(gè)基地，每個(gè)基地設(shè)有一個(gè)存儲(chǔ)倉(cāng)庫(kù)和一個(gè)回收倉(cāng)庫(kù)，負(fù)責(zé)機(jī)上周轉(zhuǎn)品的采購(gòu)、倉(cāng)儲(chǔ)、配備及清洗。各基地的存儲(chǔ)倉(cāng)庫(kù)設(shè)有一定的安全庫(kù)存來(lái)應(yīng)對(duì)未來(lái)一段時(shí)間內(nèi)的需求，并且機(jī)上周轉(zhuǎn)品在回收倉(cāng)庫(kù)經(jīng)過(guò)一段時(shí)間(清洗周期)后可以返回存儲(chǔ)倉(cāng)庫(kù)再次使用。各基地之間每天都有往返航班，當(dāng)某個(gè)基地的庫(kù)存量低于安全庫(kù)存量時(shí)，可通過(guò)航班由其它基地進(jìn)行調(diào)運(yùn)。在期初，航空公司根據(jù)整個(gè)庫(kù)存系統(tǒng)的需求統(tǒng)一訂貨，然后再根據(jù)各個(gè)基地的需求進(jìn)行分配。已知每個(gè)基地的需求量、回收量和安全庫(kù)存量，求各個(gè)基地在期初的訂貨量以及每天的調(diào)運(yùn)量，使得整個(gè)系統(tǒng)在一個(gè)訂貨周期內(nèi)所產(chǎn)生的總成本(訂貨成本、存儲(chǔ)成本、調(diào)運(yùn)成本及回收處理成本)最小。

2.2 基本假設(shè)與參數(shù)說(shuō)明

基本假設(shè)：

1)不考慮訂貨提前期，即供貨方的生產(chǎn)能力足夠大；

2)各基地的運(yùn)輸能力足夠大，并且可以在當(dāng)天完成。

3)各基地的倉(cāng)庫(kù)容量足夠大。

4)機(jī)上周轉(zhuǎn)品在每個(gè)基地的回收周期和損耗比例為常數(shù)。

參數(shù)設(shè)置：

基本參數(shù)

N：基地集合

T：訂貨周期

Si0：基地i的初始庫(kù)存量，i∈N

sit：基地i第t天的安全庫(kù)存量，i∈N，t∈T

dit：基地i第t天的需求量，i∈N，t∈T

rit：基地i第t天的回收量，i∈N，t∈T

決策變量

xi：基地i期初的訂貨量，i∈N

yijt：第t天基地i調(diào)運(yùn)到基地j的機(jī)上周轉(zhuǎn)品數(shù)量，i≠j，i,j∈N，t∈T

過(guò)程變量

Iit：基地i第t天的庫(kù)存量

整個(gè)系統(tǒng)在訂貨周期內(nèi)產(chǎn)生的總成本包括總訂貨成本、總存儲(chǔ)成本、總調(diào)運(yùn)成本以及總回收處理成本，即：

(1)

其中，ci為基地i的單位訂貨成本，hi為基地i存儲(chǔ)倉(cāng)庫(kù)的單位存儲(chǔ)成本，pij為從基地i到基地j的單位調(diào)運(yùn)成本，qi為基地i回收倉(cāng)庫(kù)的單位回收處理成本。

由于各基地的回收量已知，那么整個(gè)系統(tǒng)總回收處理成本為確定值，故不將此項(xiàng)成本計(jì)入目標(biāo)函數(shù)中。

2.3機(jī)上周轉(zhuǎn)品多基地庫(kù)存優(yōu)化模型(R1)

(1.1)

s.t.Ii0=Si0+xi

(1.2)

(1.3)

Iit≥sit

(1.4)

xi,Iit,yijt∈Ν

(1.5)

約束(1.2)表示第0天基地i的庫(kù)存量等于其初始庫(kù)存量與訂貨量之和；約束(1.3)表示基地i第t天的庫(kù)存平衡關(guān)系式；約束(1.4)表示基地i第t天的庫(kù)存量必須大于或等于其安全庫(kù)存量；約束(1.5)表示變量約束，都為非負(fù)整數(shù)。

3 模型求解與算法

令I(lǐng)it=sit+zit且si0=Si0，那么模型R1中的目標(biāo)函數(shù)(1.1)可以表示成：

(2)

由于各基地的安全庫(kù)存量已知，因此等式(2)右邊第三項(xiàng)為確定值，亦可以不計(jì)入模型目標(biāo)函數(shù)中。那么，模型R1等價(jià)于如下模型(R2)：

(2.1)

s.t.xi=zi0

(2.2)

(2.3)

xi,zit,yijt∈Ν

(2.4)

該模型是一個(gè)線性整數(shù)規(guī)劃模型，并且變量較多，直接求解非常困難。本文將在模型最優(yōu)解分析的基礎(chǔ)上，給出一個(gè)多項(xiàng)式求解算法，求得問(wèn)題的最優(yōu)解。

3.1 最優(yōu)解分析

令

X1=

X2=

證明：見(jiàn)附錄，下同。

(C1)c1=c2=…=cN=c；

(C2)h1=h2=…=hN=h；

因此，當(dāng)模型R2的參數(shù)滿足條件(C1)-(C3)時(shí)，模型R2的最優(yōu)解等價(jià)于求解如下模型(R3)的最優(yōu)解：

(3.1)

s.t.xi=zi0

(3.2)

(3.3)

(3.4)

xi,zit,yijt∈Ν

(3.5)

為此，將模型R3轉(zhuǎn)化為最小費(fèi)用最大流問(wèn)題進(jìn)行求解。剩下的問(wèn)題就是如何去構(gòu)造網(wǎng)絡(luò)，以及如何得到最小費(fèi)用最大流。

3.2 網(wǎng)絡(luò)流求解算法及最優(yōu)性

針對(duì)模型R3，構(gòu)造一個(gè)多基地動(dòng)態(tài)補(bǔ)貨網(wǎng)絡(luò)，記為D(0)=(V,A,C,B)，對(duì)于每一條弧(vi,vj)∈A上，都對(duì)應(yīng)有一個(gè)容量和單位費(fèi)用對(duì)(cij,bij)，如圖1所示。

圖1 多基地動(dòng)態(tài)補(bǔ)貨網(wǎng)絡(luò)

其中，節(jié)點(diǎn)s為發(fā)點(diǎn)，節(jié)點(diǎn)t為收點(diǎn)，節(jié)點(diǎn)0為訂貨點(diǎn)，節(jié)點(diǎn)1、2為虛擬點(diǎn)，節(jié)點(diǎn)(i,j)為基地i的所有庫(kù)存點(diǎn)(i=1,2,…,N，j=1,2,…,T)，M為一個(gè)很大的數(shù)；并稱節(jié)點(diǎn)0到節(jié)點(diǎn)(i,1)的弧為訂貨弧(i=1,2,…,N)，節(jié)點(diǎn)(i,j)到節(jié)點(diǎn)(i,j+1)的弧為庫(kù)存弧(i=1,2,…,N，j=1,2,…,T-1)，節(jié)點(diǎn)(i,j)到節(jié)點(diǎn)(k,j)的弧為調(diào)運(yùn)弧(i≠k，i,k=1,2,…,N，j=1,2,…,T)，節(jié)點(diǎn)1到節(jié)點(diǎn)(i,j)的弧為回收弧(i=1,2,…,N，j=1,2,…,T)，節(jié)點(diǎn)(i,j)到節(jié)點(diǎn)2的弧為需求弧(i=1,2,…,N，j=1,2,…,T)。

令節(jié)點(diǎn)s到節(jié)點(diǎn)0的弧、回收弧和需求弧的集合為τ，那么多基地動(dòng)態(tài)補(bǔ)貨網(wǎng)絡(luò)流模型，如下所示：

(4.1)

s.t.fij=cij(vi,vj)∈τ

(4.2)

0≤fij≤cij(vi,vj)∈A-τ

(4.3)

fij∈Ν(vi,vj)∈A

(4.4)

考慮到網(wǎng)絡(luò)D(0)=(V,A,C,B)中存在雙向的調(diào)運(yùn)弧，借鑒文獻(xiàn)[28]的方法，即若存在兩個(gè)不同的頂點(diǎn)i和j，使得弧aij=(i,j)和aji=(j,i)都存在，那么在弧aij=(i,j)中增加一個(gè)虛擬點(diǎn)x，把弧aij=(i,j)變成兩條弧aix=(i,x)和弧axj=(x,j)，使得c(aix)=c(axj)=cij，b(aix)=b(axj)=0.5bij，直到任意兩個(gè)不同頂點(diǎn)間最多存在一條弧為止，并將此時(shí)的網(wǎng)絡(luò)記為D(1)。那么，將含有回收的動(dòng)態(tài)網(wǎng)絡(luò)流模型的求解算法可以分為三步：

步驟1：取f(0)=0，為初始流。令k=0，在網(wǎng)絡(luò)D(1)中構(gòu)造賦權(quán)有向圖W(f(k))；

步驟2：在W(f(k))中，尋求從發(fā)點(diǎn)vs到收點(diǎn)vt的最短路，若不存在最短路(即最短路權(quán)是+)，則f(k)就是最小費(fèi)用流，算法結(jié)束；若存在最短路，則在原網(wǎng)絡(luò)中得到相應(yīng)的增廣鏈μ，在增廣鏈μ上對(duì)f(k)進(jìn)行調(diào)整。調(diào)整量為：令

得到新的流f(k+1)，轉(zhuǎn)步驟3；

步驟3：對(duì)f(k+1)重復(fù)步驟2。

定理2在含有回收的動(dòng)態(tài)補(bǔ)貨網(wǎng)絡(luò)流模型中采用最小費(fèi)用流求解算法得到的流f*，其訂貨弧、調(diào)運(yùn)弧、庫(kù)存弧上的流量即為模型R3的最優(yōu)解。

由于求解期初最優(yōu)訂貨總量的算法時(shí)間復(fù)雜度為Ο(N*T)，而在網(wǎng)絡(luò)中尋找從發(fā)點(diǎn)到收點(diǎn)的最短路的算法平均時(shí)間復(fù)雜度約為O(|V|2)=O((N*T+5)2)，增廣次數(shù)最壞情況下為X1，因此，整個(gè)算法的時(shí)間復(fù)雜度約為O(X1*(N*T)2)。

3.3 啟發(fā)式求解算法

這說(shuō)明原問(wèn)題最優(yōu)的總訂貨量也一定落在區(qū)間M上，其中，M=[X1,X2]。

為此，我們結(jié)合上述的網(wǎng)絡(luò)流求解算法，針對(duì)原問(wèn)題即模型R2設(shè)計(jì)一個(gè)啟發(fā)式算法，具體算法步驟如下：

步驟1：調(diào)整網(wǎng)絡(luò)D(0)的容量和單位費(fèi)用對(duì)，將節(jié)點(diǎn)0到節(jié)點(diǎn)(i,1)的弧(即訂貨弧)上的費(fèi)用調(diào)整為ci，節(jié)點(diǎn)(i,j)到節(jié)點(diǎn)(i,j+1)的弧(即庫(kù)存弧)上的費(fèi)用調(diào)整為hi，調(diào)整后的網(wǎng)絡(luò)記為D(2)。

步驟2：將區(qū)間M=[X1,X2]等分成Q份，其中各端點(diǎn)分別記為Xi=X1+?i(X2-X1)/Q」，其中?*」表示向下取整。

4 算例

本文以國(guó)內(nèi)某大型航空公司為例，分析某一種機(jī)上周轉(zhuǎn)品(沙拉碗)在一個(gè)訂貨周期內(nèi)的補(bǔ)貨策略。該公司在全國(guó)擁有八個(gè)基地，各基地位置及調(diào)運(yùn)網(wǎng)絡(luò)如圖所示。

圖2 各基地位置及調(diào)運(yùn)網(wǎng)絡(luò)圖

假設(shè)訂貨周期T=7(天)，各基地的參數(shù)設(shè)置如下：機(jī)上周轉(zhuǎn)品的單位訂貨成本為10(元/個(gè))，單位存儲(chǔ)成本為0.1(元/個(gè)*天)，單位調(diào)運(yùn)成本為0.01(元/個(gè)*天)，初始庫(kù)存量、日需求量、日回收量及日安全庫(kù)存量見(jiàn)表1～4。

由于上述參數(shù)滿足定理1的條件，因此通過(guò)定理1的計(jì)算公式可以得到期初最優(yōu)的訂貨總量為：x*=3571。

表1 各基地的初始庫(kù)存量

表2 各基地的日需求量

表3 各基地的日回收量

表4 各基地的日安全庫(kù)存量

通過(guò)最小費(fèi)用流求解算法進(jìn)行求解，最終得到各基地最優(yōu)的期初訂貨量和每日最優(yōu)的調(diào)運(yùn)量，見(jiàn)表5～6：

表5 各基地期初最優(yōu)的訂貨方案

下面分析各基地單位調(diào)運(yùn)成本不同的情形，假設(shè)基地A與基地C之間的單位調(diào)運(yùn)成本為0.02(元/個(gè)*天)，而其它參數(shù)保持不變。從定理1可知，期初最優(yōu)的訂貨總量依然為3571(個(gè))。而各基地的期初最優(yōu)訂貨方案以及每日的調(diào)運(yùn)方案如下：

表6 各基地間最優(yōu)的調(diào)運(yùn)方案

表7 各基地期初最優(yōu)的訂貨方案

表8 各基地間最優(yōu)的調(diào)運(yùn)方案

由于基地C到基地A的單位調(diào)運(yùn)成本的增加，使得基地C調(diào)出到基地A的量減少，調(diào)出到其它基地(B、E、F、H)的量增加，進(jìn)而使得基地A的期初訂貨量增加，其它基地(B、E、F、H)的期初訂貨量減少。由此可以看出，訂貨和調(diào)運(yùn)方案會(huì)受到各基地之間的單位調(diào)運(yùn)成本的影響。

接下來(lái)分析當(dāng)各基地的單位訂貨成本和單位存儲(chǔ)成本不相同的情形。通過(guò)引理2的分析，得到各基地的期初缺貨量(見(jiàn)表9)。

表9 各基地的期初缺貨量

因此，原問(wèn)題的期初最優(yōu)訂貨總量所處的區(qū)間為[3571，4151]。

假設(shè)基地A的單位訂貨成本為5(元/個(gè))，而其它參數(shù)不變。令Q=10，ε=10-3，通過(guò)啟發(fā)式算法得到一個(gè)較優(yōu)的訂貨和調(diào)運(yùn)方案如下：

表10 各基地期初的訂貨方案

表11 各基地間的調(diào)運(yùn)方案

假設(shè)基地A的單位存儲(chǔ)成本為0.5(元/個(gè)*天)，而其它參數(shù)不變。令Q=10，ε=10-3，同樣通過(guò)啟發(fā)式算法得到一個(gè)較優(yōu)的訂貨和調(diào)運(yùn)方案如下：

表12 各基地期初的訂貨方案

表13 各基地間的調(diào)運(yùn)方案

通過(guò)上述兩個(gè)例子，可以得出期初的訂貨方案和每天的調(diào)運(yùn)方案同樣也會(huì)受到單位訂貨成本以及單位存儲(chǔ)成本的影響。

通過(guò)該啟發(fā)式算法只能得到眾多可行解中的一個(gè)較優(yōu)的訂貨和調(diào)運(yùn)方案，而通過(guò)對(duì)3.1節(jié)最優(yōu)解的分析，當(dāng)不滿足條件(C1)-(C3)下，目標(biāo)函數(shù)的單調(diào)性無(wú)法確定，進(jìn)而模型的最優(yōu)解很難得到，故而該啟發(fā)式算法的精度也不能確定；當(dāng)滿足條件(C1)-(C3)下，因?yàn)閱l(fā)式算法的可行解中包含最優(yōu)訂貨量(X1)，故最終得到的解相同。

接下來(lái)分析不同單位成本參數(shù)對(duì)整個(gè)系統(tǒng)總庫(kù)存成本的影響情況(見(jiàn)圖3～5)。

圖3 基地A的單位庫(kù)存成本的變化對(duì)整個(gè)系統(tǒng)總庫(kù)存成本的影響

圖4 基地之間的單位調(diào)運(yùn)成本的變化對(duì)系統(tǒng)總庫(kù)存成本的影響

圖5 基地A的單位訂貨成本的變化對(duì)系統(tǒng)總庫(kù)存成本的影響

由此可見(jiàn)，各基地的單位訂貨成本、單位存儲(chǔ)成本以及各基地之間的調(diào)運(yùn)成本會(huì)影響整個(gè)系統(tǒng)的總庫(kù)存成本，進(jìn)而影響到整個(gè)系統(tǒng)的訂貨和調(diào)運(yùn)方案。

5 結(jié)語(yǔ)

本文研究航空公司機(jī)上周轉(zhuǎn)品多基地庫(kù)存優(yōu)化問(wèn)題，構(gòu)建了一個(gè)單周期的動(dòng)態(tài)補(bǔ)貨模型。該模型在已知每個(gè)基地的每日需求量、回收量及安全庫(kù)存量下，對(duì)期初的訂貨量以及每日的調(diào)入調(diào)出量進(jìn)行決策，使得整個(gè)系統(tǒng)的庫(kù)存總成本(包括訂貨成本、存儲(chǔ)成本、調(diào)運(yùn)成本、回收成本)最小化。并對(duì)該模型的最優(yōu)解進(jìn)行了分析，參考網(wǎng)絡(luò)流算法，給出了一個(gè)在成本參數(shù)滿足一定條件下的多項(xiàng)式求解算法；此外，設(shè)計(jì)了一個(gè)求解原問(wèn)題的啟發(fā)式算法。最終結(jié)合實(shí)際的例子，驗(yàn)證了算法的有效性。但本文所提出的問(wèn)題還有待深入研究的地方，比如考慮隨機(jī)需求、擴(kuò)展到多周期的補(bǔ)貨問(wèn)題等。

附錄：

(1)引理1的證明

(2)引理2的證明

(3)引理3的證明

當(dāng)條件(C1)(C2)成立時(shí)，將約束條件(2.2)-(2.4)代入模型R2的目標(biāo)函數(shù)G(xi,zit,yijt)并化簡(jiǎn)可得：

(4)定理1的證明

(5)定理2的證明

對(duì)于最小費(fèi)用流模型中的任何一個(gè)可行流f，若令節(jié)點(diǎn)0到節(jié)點(diǎn)(i,1)的弧上的流量為xi(i=1,2,…,N)，節(jié)點(diǎn)(i,j)到節(jié)點(diǎn)(i,j+1)的弧上的流量為zij(i=1,2,…,N，j=1,2,…,T-1)，節(jié)點(diǎn)(i,j)到節(jié)點(diǎn)(k,j)的弧上的流量為yikj(i≠k，i,k=1,2,…,N，j=1,2,…,T)，而其他弧上的單位費(fèi)用為零，故由(4.1)可知此流的總輸送費(fèi)用為：

由于f是一個(gè)可行流，因此由約束條件(4.2)可知其節(jié)點(diǎn)s到節(jié)點(diǎn)0的弧、回收弧和需求弧上的流量都等于其容量，并令xi=zi0，那么對(duì)任一個(gè)節(jié)點(diǎn)(i,j)，由出入流量平衡可知，

并且由約束(4.4)可知，xi,zit,yijt∈Ν，因此含有回收的網(wǎng)絡(luò)流模型中所有的可行流上訂貨、庫(kù)存和調(diào)運(yùn)弧的流量皆為模型R3的可行解，并且目標(biāo)函數(shù)都一致。

下證，最小費(fèi)用流算法一定能得到含有回收的網(wǎng)絡(luò)流模型中使得總費(fèi)用最小的可行流。在含有回收的動(dòng)態(tài)補(bǔ)貨網(wǎng)絡(luò)D(0)中，當(dāng)發(fā)點(diǎn)vs到訂貨點(diǎn)v0弧上的流量fs0小于其容量x*時(shí)，對(duì)于任意一個(gè)基地i，一定存在一條從發(fā)點(diǎn)vs到收點(diǎn)vt的路ξ，這條路經(jīng)過(guò)訂貨點(diǎn)v0和基地i的所有庫(kù)存點(diǎn)vit，且權(quán)值為c+Th<+。因此按照最小費(fèi)用流算法可以依次調(diào)整權(quán)小于等于c+Th的從發(fā)點(diǎn)vs到收點(diǎn)vt的路(增廣鏈)上的流量，此時(shí)增廣鏈上一定包含弧集合τ中的一條或多條弧，直到弧集合τ上所有弧的流量都等于其容量，此時(shí)，已找不到從發(fā)點(diǎn)vs到收點(diǎn)vt的最短路，那么最終得到的流f*是最小費(fèi)用流模型的一個(gè)可行流；由最小費(fèi)用最大流問(wèn)題可知，f*是所有流量等于的總費(fèi)用最小的一個(gè)流，故f*是最小費(fèi)用流模型中使得總費(fèi)用最小的可行流。