航空公司機上周轉品多基地庫存優化模型

宋江海，池 宏，高敏剛

(1.中國科學院科技戰略咨詢研究院，北京 100190；2.中國科學院大學，北京 100049)

1 引言

隨著高鐵的普及、電子商務的飛速發展，使得航空公司的競爭日益激烈，成本控制成為航空公司增強市場競爭力的關鍵，加強對各項運營成本的控制顯得尤為重要。

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

目前民航領域關于機上周轉品的研究相對較少，并且缺乏定量的模型分析。趙桂紅和馬志剛[1]針對機供品的組成、特點以及在成本控制方面存在的問題，提出了不同類型的機供品成本控制的解決方案。谷偉強[2]以某航空公司自主開發的“機供品管理平臺”為例，分析了機供品管理信息系統的設計與實現的全過程。

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

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

以上研究主要考慮在庫存系統中遇到的各種不確定性因素，去解決回收再利用過程中的一次性調度問題；或針對備件或消耗品在不同特征下的多點庫存系統，研究其補貨或調運策略。而本文考慮的是航空公司機上周轉品的多基地庫存系統，研究其在一個訂貨周期內的動態補貨問題，決策期初的訂貨方案以及周期內的調運方案，實現庫存共享和降低成本。構建了一個庫存優化模型，分析了最優解的性質，并設計了相應的算法進行求解，通過算例驗證了方法的有效性。

2 問題與模型構建

2.1 問題描述

某航空公司擁有多個基地，每個基地設有一個存儲倉庫和一個回收倉庫，負責機上周轉品的采購、倉儲、配備及清洗。各基地的存儲倉庫設有一定的安全庫存來應對未來一段時間內的需求，并且機上周轉品在回收倉庫經過一段時間(清洗周期)后可以返回存儲倉庫再次使用。各基地之間每天都有往返航班，當某個基地的庫存量低于安全庫存量時，可通過航班由其它基地進行調運。在期初，航空公司根據整個庫存系統的需求統一訂貨，然后再根據各個基地的需求進行分配。已知每個基地的需求量、回收量和安全庫存量，求各個基地在期初的訂貨量以及每天的調運量，使得整個系統在一個訂貨周期內所產生的總成本(訂貨成本、存儲成本、調運成本及回收處理成本)最小。

2.2 基本假設與參數說明

基本假設：

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

2)各基地的運輸能力足夠大，并且可以在當天完成。

3)各基地的倉庫容量足夠大。

4)機上周轉品在每個基地的回收周期和損耗比例為常數。

參數設置：

基本參數

N：基地集合

T：訂貨周期

Si0：基地i的初始庫存量，i∈N

sit：基地i第t天的安全庫存量，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調運到基地j的機上周轉品數量，i≠j，i,j∈N，t∈T

過程變量

Iit：基地i第t天的庫存量

整個系統在訂貨周期內產生的總成本包括總訂貨成本、總存儲成本、總調運成本以及總回收處理成本，即：

(1)

其中，ci為基地i的單位訂貨成本，hi為基地i存儲倉庫的單位存儲成本，pij為從基地i到基地j的單位調運成本，qi為基地i回收倉庫的單位回收處理成本。

由于各基地的回收量已知，那么整個系統總回收處理成本為確定值，故不將此項成本計入目標函數中。

2.3機上周轉品多基地庫存優化模型(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的庫存量等于其初始庫存量與訂貨量之和；約束(1.3)表示基地i第t天的庫存平衡關系式；約束(1.4)表示基地i第t天的庫存量必須大于或等于其安全庫存量；約束(1.5)表示變量約束，都為非負整數。

3 模型求解與算法

令Iit=sit+zit且si0=Si0，那么模型R1中的目標函數(1.1)可以表示成：

(2)

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

(2.1)

s.t.xi=zi0

(2.2)

(2.3)

xi,zit,yijt∈Ν

(2.4)

該模型是一個線性整數規劃模型，并且變量較多，直接求解非常困難。本文將在模型最優解分析的基礎上，給出一個多項式求解算法，求得問題的最優解。

3.1 最優解分析

令

X1=

X2=

證明：見附錄，下同。

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

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

因此，當模型R2的參數滿足條件(C1)-(C3)時，模型R2的最優解等價于求解如下模型(R3)的最優解：

(3.1)

s.t.xi=zi0

(3.2)

(3.3)

(3.4)

xi,zit,yijt∈Ν

(3.5)

為此，將模型R3轉化為最小費用最大流問題進行求解。剩下的問題就是如何去構造網絡，以及如何得到最小費用最大流。

3.2 網絡流求解算法及最優性

針對模型R3，構造一個多基地動態補貨網絡，記為D(0)=(V,A,C,B)，對于每一條弧(vi,vj)∈A上，都對應有一個容量和單位費用對(cij,bij)，如圖1所示。

圖1 多基地動態補貨網絡

其中，節點s為發點，節點t為收點，節點0為訂貨點，節點1、2為虛擬點，節點(i,j)為基地i的所有庫存點(i=1,2,…,N，j=1,2,…,T)，M為一個很大的數；并稱節點0到節點(i,1)的弧為訂貨弧(i=1,2,…,N)，節點(i,j)到節點(i,j+1)的弧為庫存弧(i=1,2,…,N，j=1,2,…,T-1)，節點(i,j)到節點(k,j)的弧為調運弧(i≠k，i,k=1,2,…,N，j=1,2,…,T)，節點1到節點(i,j)的弧為回收弧(i=1,2,…,N，j=1,2,…,T)，節點(i,j)到節點2的弧為需求弧(i=1,2,…,N，j=1,2,…,T)。

令節點s到節點0的弧、回收弧和需求弧的集合為τ，那么多基地動態補貨網絡流模型，如下所示：

(4.1)

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

(4.2)

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

(4.3)

fij∈Ν(vi,vj)∈A

(4.4)

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

步驟1：取f(0)=0，為初始流。令k=0，在網絡D(1)中構造賦權有向圖W(f(k))；

步驟2：在W(f(k))中，尋求從發點vs到收點vt的最短路，若不存在最短路(即最短路權是+)，則f(k)就是最小費用流，算法結束；若存在最短路，則在原網絡中得到相應的增廣鏈μ，在增廣鏈μ上對f(k)進行調整。調整量為：令

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

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

定理2在含有回收的動態補貨網絡流模型中采用最小費用流求解算法得到的流f*，其訂貨弧、調運弧、庫存弧上的流量即為模型R3的最優解。

由于求解期初最優訂貨總量的算法時間復雜度為Ο(N*T)，而在網絡中尋找從發點到收點的最短路的算法平均時間復雜度約為O(|V|2)=O((N*T+5)2)，增廣次數最壞情況下為X1，因此，整個算法的時間復雜度約為O(X1*(N*T)2)。

3.3 啟發式求解算法

這說明原問題最優的總訂貨量也一定落在區間M上，其中，M=[X1,X2]。

為此，我們結合上述的網絡流求解算法，針對原問題即模型R2設計一個啟發式算法，具體算法步驟如下：

步驟1：調整網絡D(0)的容量和單位費用對，將節點0到節點(i,1)的弧(即訂貨弧)上的費用調整為ci，節點(i,j)到節點(i,j+1)的弧(即庫存弧)上的費用調整為hi，調整后的網絡記為D(2)。

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

4 算例

本文以國內某大型航空公司為例，分析某一種機上周轉品(沙拉碗)在一個訂貨周期內的補貨策略。該公司在全國擁有八個基地，各基地位置及調運網絡如圖所示。

圖2 各基地位置及調運網絡圖

假設訂貨周期T=7(天)，各基地的參數設置如下：機上周轉品的單位訂貨成本為10(元/個)，單位存儲成本為0.1(元/個*天)，單位調運成本為0.01(元/個*天)，初始庫存量、日需求量、日回收量及日安全庫存量見表1～4。

由于上述參數滿足定理1的條件，因此通過定理1的計算公式可以得到期初最優的訂貨總量為：x*=3571。

表1 各基地的初始庫存量

表2 各基地的日需求量

表3 各基地的日回收量

表4 各基地的日安全庫存量

通過最小費用流求解算法進行求解，最終得到各基地最優的期初訂貨量和每日最優的調運量，見表5～6：

表5 各基地期初最優的訂貨方案

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

表6 各基地間最優的調運方案

表7 各基地期初最優的訂貨方案

表8 各基地間最優的調運方案

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

接下來分析當各基地的單位訂貨成本和單位存儲成本不相同的情形。通過引理2的分析，得到各基地的期初缺貨量(見表9)。

表9 各基地的期初缺貨量

因此，原問題的期初最優訂貨總量所處的區間為[3571，4151]。

假設基地A的單位訂貨成本為5(元/個)，而其它參數不變。令Q=10，ε=10-3，通過啟發式算法得到一個較優的訂貨和調運方案如下：

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

表11 各基地間的調運方案

假設基地A的單位存儲成本為0.5(元/個*天)，而其它參數不變。令Q=10，ε=10-3，同樣通過啟發式算法得到一個較優的訂貨和調運方案如下：

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

表13 各基地間的調運方案

通過上述兩個例子，可以得出期初的訂貨方案和每天的調運方案同樣也會受到單位訂貨成本以及單位存儲成本的影響。

通過該啟發式算法只能得到眾多可行解中的一個較優的訂貨和調運方案，而通過對3.1節最優解的分析，當不滿足條件(C1)-(C3)下，目標函數的單調性無法確定，進而模型的最優解很難得到，故而該啟發式算法的精度也不能確定；當滿足條件(C1)-(C3)下，因為啟發式算法的可行解中包含最優訂貨量(X1)，故最終得到的解相同。

接下來分析不同單位成本參數對整個系統總庫存成本的影響情況(見圖3～5)。

圖3 基地A的單位庫存成本的變化對整個系統總庫存成本的影響

圖4 基地之間的單位調運成本的變化對系統總庫存成本的影響

圖5 基地A的單位訂貨成本的變化對系統總庫存成本的影響

由此可見，各基地的單位訂貨成本、單位存儲成本以及各基地之間的調運成本會影響整個系統的總庫存成本，進而影響到整個系統的訂貨和調運方案。

5 結語

本文研究航空公司機上周轉品多基地庫存優化問題，構建了一個單周期的動態補貨模型。該模型在已知每個基地的每日需求量、回收量及安全庫存量下，對期初的訂貨量以及每日的調入調出量進行決策，使得整個系統的庫存總成本(包括訂貨成本、存儲成本、調運成本、回收成本)最小化。并對該模型的最優解進行了分析，參考網絡流算法，給出了一個在成本參數滿足一定條件下的多項式求解算法；此外，設計了一個求解原問題的啟發式算法。最終結合實際的例子，驗證了算法的有效性。但本文所提出的問題還有待深入研究的地方，比如考慮隨機需求、擴展到多周期的補貨問題等。

附錄：

(1)引理1的證明

(2)引理2的證明

(3)引理3的證明

當條件(C1)(C2)成立時，將約束條件(2.2)-(2.4)代入模型R2的目標函數G(xi,zit,yijt)并化簡可得：

(4)定理1的證明

(5)定理2的證明

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

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

并且由約束(4.4)可知，xi,zit,yijt∈Ν，因此含有回收的網絡流模型中所有的可行流上訂貨、庫存和調運弧的流量皆為模型R3的可行解，并且目標函數都一致。

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