何 彤

（廣東技術(shù)師范大學 管理學院，廣東 廣州 510665）

由于貨車租賃市場及其相關(guān)物流信息技術(shù)的迅猛發(fā)展，從外部市場租賃貨車來補充企業(yè)自有車隊運力的不足，已經(jīng)極為便利并可降低固定資產(chǎn)投入和運輸成本.故此，目前貨運行業(yè)已經(jīng)普遍采取自有與租賃車輛相結(jié)合的貨運車隊組合策略，其運營優(yōu)化的主要方式是車隊組合構(gòu)成優(yōu)化及運輸線路優(yōu)化[1].目前國內(nèi)外對后者的研究較多而對前者的研究很少，有必要做更為深入的探討.

車隊構(gòu)成優(yōu)化的難點就是自有車隊應該購置多少輛車和配置哪些車型，以及如何判斷在何種情況下應從租車市場租用貨車？由于具體到某一天的運輸需求量一般都是隨機的，相應的運輸車輛需求數(shù)量也就隨機變化.對于車隊而言，自有車輛多而運輸需求量少時，會出現(xiàn)車輛閑置；而在自有車輛少而運輸需求量多時，就需要從外部企業(yè)租賃車輛來滿足需求，但租賃車輛的變動成本更高，其服務水平也往往低于自有車輛.當需求集中在少數(shù)幾個客戶點時，為使可變成本最小化，企業(yè)傾向于使用大型車輛來運輸，因為在可變成本方面大型車比小型車更有效率，諸如燃油和司機工資等方面；而如果同樣數(shù)量的需求被均勻地分布到大量的客戶站點上，則傾向于使用眾多小型車輛來運輸.所以，如何確定自有車隊最優(yōu)規(guī)模和構(gòu)成，使其在借助車輛租賃市場的情況下，既滿足客戶需求又盡量降低車隊運營成本，就成了貨運企業(yè)經(jīng)營管理所必須面對的問題.

為了幫助貨運企業(yè)解決這一問題，本文提出了一個優(yōu)化模型，其目標是在滿足需求的前提下，在自有車輛的固定成本與租賃車輛的較高可變成本之間取得最優(yōu)配置，并以成本最低作為評價標準，來判定和優(yōu)化車隊的構(gòu)成.模型中對某一天的需求以要交付的總貨物量和要訪問的總客戶站點數(shù)量來進行描述，由于需求空間簡化為二維，就能夠直接用數(shù)值積分來計算所需的梯度，并易于對每個積分域計算出相應的最優(yōu)對偶向量以及最優(yōu)基矩陣的逆.據(jù)此，本文構(gòu)建了一個基于該二維特性需求的兩級補償線性規(guī)劃，并提出一種利用標準梯度法進行連續(xù)優(yōu)化的該模型的有效求解算法.

1 模型的建立與分析

本文模型參考了Eberly和Van Mieghem的研究結(jié)果[2]，但他們的模型中對于所涉及的多種資源中哪些車型應納入車隊的決策周期只有一個；而且本文模型的最優(yōu)控制策略(即每種車型的最優(yōu)數(shù)量)可以根據(jù)預期利潤函數(shù)的梯度來定義，采用的補償規(guī)劃是一個所有系數(shù)都假定為正的、具有正分數(shù)覆蓋約束的最小化問題.

設(shè)O為包含n1種車型的企業(yè)自有車型集合，設(shè)H為包含n2種車型的可租賃車型集合，總車型數(shù)量n=n1+n2.注意：如果某種特定型號貨車既可從自有車隊調(diào)用也可從外部租車公司租賃，由于其獲取的成本不同，本文視其為兩種不同的“車型”.用非負變量Q和S分別表示要交付貨物總量和要訪問的各客戶站點的總數(shù)量，則規(guī)劃周期內(nèi)隨機選取的某個工作日的貨運需求D=(Q,S).

貨運需求量還未明確時，車隊一般都考慮優(yōu)先使用自有車輛來滿足貨運需求，本文稱之為事先決策；而把明確了某天的需求后，如何最好地利用自有和租賃車輛(運力補償)來滿足這天的需求稱之為工作決策.設(shè)車隊構(gòu)成向量表示自有車隊所擁有各種車型的車輛數(shù)量，則選擇K就是事先決策；利用向量表示每種車型中要利用的車輛數(shù)量，即工作決策.在給定車隊構(gòu)成K和已知需求D=(Q,S)時，工作決策的最優(yōu)成本為：

式中v'，q'，s'是對變量v、q、s的微分計算.

本文假設(shè)可從外部租賃的車輛數(shù)是無限的.

工作決策的預期成本是關(guān)于二元概率分布的整數(shù)集Z(K):=E[z(K,D)].這樣可得到K≥0條件下的事先決策公式為：.在需求不確定的情況下，或者需求已知而且其變化符合二元概率分布，上述公式可將規(guī)劃周期內(nèi)的車隊成本減至最低.

設(shè)t為規(guī)劃周期中工作日的索引指標，T為規(guī)劃周期內(nèi)的工作日總數(shù)，P(t)=T-1表示第t天被選中的概率.隨機向量D的分布表示規(guī)劃周期中隨機抽取的某個工作日需求，即Dt是第t天的需求量.這樣，在規(guī)劃周期中發(fā)生的預期總成本為向量K的函數(shù)：通過線性期望，即將上述函數(shù)乘以正常數(shù)T-1來最小化函數(shù)，可得：再通過運用總期望定律，它可歸納為本文模型的目標函數(shù)

2 模型的求解算法

在本節(jié)中，2.1小節(jié)先申明模型的前提假設(shè)條件，本文的確定性等價規(guī)劃因此被保證為一個凸規(guī)劃，并在可行集內(nèi)部各處定義的梯度.2.2小節(jié)中參照帶兩個附加變量的補償規(guī)劃迭代公式，定義了補償規(guī)劃的基，并在可能需求范圍內(nèi)定義了基的可行域，以及與最優(yōu)基對應的最優(yōu)對偶向量.定義了補償規(guī)劃的“權(quán)威”基集合的概念，并闡明了該集合在一個標準梯度搜索算法中的作用.在2.3小節(jié)中，給出了生成補償規(guī)劃的一組權(quán)威基集合的算法過程，并對其正確性和多項式復雜度進行了論證.

2.1 前提假設(shè)

為簡化對模型有效性的評估，本文假設(shè)下述前提條件成立：

假設(shè)2：非負隨機變量D = (Q,S)具有有限二階矩聯(lián)合概率密度函數(shù).

假設(shè)3：整個規(guī)劃周期內(nèi)，自有和租賃車型的單位使用成本和能力參數(shù)均為恒量，并且獨立于車隊構(gòu)成和利用決策.

假設(shè)4：貨運需求獨立于車隊構(gòu)成和利用決策.

在假設(shè)1成立條件下，本文隨機規(guī)劃模型具有相對完整的補償.優(yōu)化模型（在K≥0條件下的可視為確定性等價規(guī)劃，使得Z(K)內(nèi)的隨機性符合條件，對于任何可能的需求向量，不需要在K上添加約束來確保工作決策有一個最優(yōu)解.在假設(shè)1和2成立的前提下，Birge和Louveaux已證明確定性等價規(guī)劃是一個凸規(guī)劃，且對可行集內(nèi)的所有K都存在梯度[4].

2.2 “權(quán)威”的基集合

2.2.1 專用于補償規(guī)劃的基集合及其可行域和最優(yōu)對偶向量

Bertsimas和Tsitsiklis論證了可使用具有上下界的變量來定義一個基[5]，本文依據(jù)其理論來構(gòu)造一組用于補償?shù)膶Ｓ没?用兩個附加變量xq和xs重構(gòu)以產(chǎn)生等式約束，通過將決策變量劃分為三個集合來識別確定一個基：包含兩個基礎(chǔ)指標的集合B、從O中選取的保持在其上界的變量指標集合U、保持在其下界的變量指標集合L.本文還定義差額成本為，式中B-1是由前述最優(yōu)成本等式系統(tǒng)的兩個基本列所構(gòu)成的方矩陣的逆，Ai是該系統(tǒng)中選定的非基本列.則一個最優(yōu)基應滿足的條件有兩個：首先是其相關(guān)解是可行的，即基本變量都是非負的，在適用情況下，分別是的上界；其次對于每個i∈L是非負的，而對于每個i∈U是非正的.對于每一個基b，在可能需求范圍內(nèi)定義其相關(guān)可行域為：

對于Ωb中某些點的最優(yōu)基b也是該域中每個點的最優(yōu).補償問題的對偶性可表示如下：

如果b是Ωb的最優(yōu)解，則在整個Ωb內(nèi)部可獲得唯一最優(yōu)對偶向量.每當?shù)牡趇分量可被視為對Ωb(K)內(nèi)需求點處的最優(yōu)成本的右偏導數(shù).

2.2.2 “權(quán)威”基集合的定義及其梯度公式的應用

本文把滿足以下三個關(guān)鍵條件的基集合B稱為具有足夠代表性的“權(quán)威”基集合：1）全面覆蓋：對于每個K≥0都滿足2）最優(yōu)性：每一個基b∈B均是Ωb的最優(yōu)解；3）不相交：對于每個K≥0和基對b1, b2∈B，Ωb1(K)和Ωb2(K)內(nèi)部不相交.

而當B是一組權(quán)威基集合，且在假設(shè)1和2成立的前提下，對于每一個K≥0時必然有預期工作決策成本的梯度公式成立：

有了生成補償問題的權(quán)威基集合的算法，就可以采用標準的梯度投影算法來進行優(yōu)化了.而模型的目標函數(shù)及其梯度的計算也可以簡化如下：在開始搜索算法之前，先使用本文算法生成一個權(quán)威集合B，并對于每個基b∈B，連同界定集合B、L、U一起存儲相應基的逆矩陣B-1和向量；假設(shè)在梯度搜索算法中得到K≥0以及目標函數(shù)的梯度.且對于每個基b∈B，通過適當域密度函數(shù)的數(shù)值積分來獲得P(Ωb(K))，則所期望梯度為；最后，在K≥0條件下求搜索算法的目標函數(shù)值.為達此目的，通過對需求空間進行數(shù)值積分來計算關(guān)于密度函數(shù)的期望值.在這一過程中，使用集合B、L、U和D∈Ωb(K)時相應于基b∈B的存儲矩陣B-1，來評估在給定點D=(Q,S)的工作決策成本z(K,D).依次執(zhí)行對域Ωb(K)的積分，就能立即知道哪些基參數(shù)適用于當前域的給定需求點.

注意：為了便于數(shù)值積分的目的，依據(jù)Birge和Louveaux的研究結(jié)果，可把理論上無邊界的需求空間縮小到一個大的有界域，如此依然可以捕獲幾乎所有的概率質(zhì)量[4].而鑒于決策的策略性和參數(shù)空間的低維性，也不需要采用復雜的數(shù)值積分方法.

2.3 為本文模型有效地生成“權(quán)威”集合的算法

下面說明生成權(quán)威集合B的算法.該算法可以自由地從公式中舍棄某些不需要出現(xiàn)在車隊最優(yōu)構(gòu)成中的車輛類型，并用效率向量來表示某種車型的可變成本效率.根據(jù)假設(shè)1，這些向量的每一個都定義明確且兩個分量均為正數(shù).

2.3.1 算法過程：

步驟1排除明顯不經(jīng)濟或不必要的車輛類型：

對于每種車型i1，判斷是否有第二種車型i2滿 足 條 件和.如果是，則排除車型i1.（理由在于用車型i2取代i1來滿足需求時，其成本會更低.）這一步驟完成后，可確保沒有兩個向量φi1和φi2是完全相同的.假定在所有排除工作完成后仍有n1＞0，否則，本文模型的技術(shù)經(jīng)濟研究就不適用了.

步驟2生成容許站點能力過剩的基：

步驟3生成容許運力能力過剩的基：

這里產(chǎn)生的任何給定基所關(guān)聯(lián)的最優(yōu)對偶向量，對于所有i∈OU，有=0；對所有的

步驟4生成具有兩種基本車型的基：

對于每一對車型{i1,i2}執(zhí)行下述操作：如果，繼續(xù)計算下一對車型.否則，計算使直線在內(nèi)同時相交于和的和值.確定時向量φi的集合V使得，或使得凸組合.如果V∩H不為空，則繼續(xù)計算所考慮的下一對車型.否則，依據(jù)B={i1,i2}、U=V，以及包含所有剩余指標(包括q和s)的L來生成基.

這里生成的任何給定基所關(guān)聯(lián)的最優(yōu)對偶向量，對于所有i∈OU有；對所有的i∈U有 λi=vi-qiμ1-siμ2.

2.3.2 算法的有效性證明

在本小節(jié)中，將論證本文算法所生成的基，能完全滿足前述權(quán)威基集合的三個關(guān)鍵條件，以及評估其計算復雜度.

1）假設(shè)1成立時，由本文算法生成的基必然滿足最優(yōu)性條件.

由于設(shè)每個qi和si都為正，則Ωb(1)的內(nèi)部非空.從Ωb(1)內(nèi)部選取點(Q,S)，如果其所對應的基本解滿足互補松弛條件是非退化的，就表示這個解也是最優(yōu)的.

證明如下：當b是在步驟2中生成，那么對于一些車型il有B={il,s}，并構(gòu)建對偶解：對于所有的i∈OU 有μ1=vil/cil，μ2=0，λi=0，而對于所有i∈U 有λi=vi-qiμ1.這個對偶解是可行的，并且與基b對應的原解滿足互補松弛條件，從而建立最優(yōu)性[6].當在步驟3中生成b，則與步驟2生成b類似情況地可建立最優(yōu)性；在這里，對一些車型il有B={q,il}，對偶解對所有i∈OU，有μ1=0，μ2=vil/sil，λi=0；和 對 于 所 有i∈U 有λi=vi-siμ2.最后，如果b生成于步驟4中，那么對于某些車型i1和i2有B={i1,i2}.設(shè)是應用本文算法對該對車型計算出的值；對于所有i∈OU設(shè)λi=0和對 于 所 有i∈U 則 有λi=vi-qiμ1-siμ2.可 見 該 對 偶解是可行的，并且互補松弛條件成立.所以，由本文算法生成的基必然滿足最優(yōu)性條件.

2）假設(shè)1成立時，本文算法生成的基必然滿足覆蓋條件.

證明：由于n1、n2、qi和si均為正，工作決策規(guī)劃是可行的，并且對于每個存在一個最優(yōu)基本解.依據(jù)線性規(guī)劃理論，本文補償問題的基本解最多有兩個不在其邊界上的變量.由于設(shè)v為正，一個最優(yōu)基本解永遠不會有離開其邊界的xq和xs.對于一些車型il，如果在xs和xil遠離其邊界時，卻存在(Q,S,K)最優(yōu)基本解，那么互補松弛性使μ1=vil/cil，具有的車型i必須是滿足xi=Ki的自有車型，而符合的車型i必有xi=0.當有多種車型具有=vi/qi時，通過參照使用指定基的最后車型所使用站點可變成本效率的遞減順序去運用它們，則最優(yōu)性得以保持；通過確保每個車型i滿足Ki=0，且 如 果則i∈U而 如 果則i∈L，也保持最優(yōu)性并最后得到步驟2中生成的基.可以類似地證明，對于某些車型il當xq和離開其邊界且存在(Q,S,K)是最優(yōu)基本解時，步驟3中生成的一些基是最優(yōu)的.最后，在相應于車型對i1和i2的離開其邊界時，如果存在(Q,S,K)這樣一個最優(yōu)基本解，那么互補松弛性規(guī)定這一基本對的μ1和μ2應計算如步驟4中所示，φi超過此線時的車型i必須是滿足xi=Ki的自有車型，φi完全低于此線時的車型i必須滿足xi=0.當有兩種以上車型的φi在此線之上時，通過按部就班地減少“最外層”車型的利用，同時增加利用“內(nèi)層”車型，可得到一個基對并與第4步相應的最優(yōu)利用率一致；通過確保滿足Ki=0的每種車型i在φi高于此線時i∈U，以及φi低于此線時i∈L，可保持最優(yōu)性并最后得到第4步生成的基.對于每一個K≥0，除一組勒貝格測度之外，上述情形使Ub∈BΩb(K)乘的覆蓋為零.由于這是閉集的有限覆蓋，這個并集實際上覆蓋了需求空間的全部.

3）假設(shè)1成立時，本算法生成的基滿足不相交的內(nèi)部條件.

證明：給定K≥0，且設(shè)(Q,S)是算法生成的基b中某些域Ωb(K)的一個內(nèi)部點.如果b在步驟2中生成，對于一些具有B={il,s}車型il，依據(jù)互補松弛性在雙最優(yōu)下必有=0.對于另一些由算法生成的基b*，如果(Q,S)是Ωb*(K)的一個內(nèi)部點，這些獨特的對偶值意味 著b*一 定 有在不失一般性的情況下，假設(shè)在步驟2的處理順序中車型il優(yōu)先于車型il*.但當Ωb*(K)內(nèi)從開始的任意點超過這個運力數(shù)量時，Ωb(K)內(nèi)任意一點會完全小于運力單位.可類似地證明步驟3中生成b的情況，對一些車型il有B={q,il}和唯一地最優(yōu)雙值.最后，來考慮對于一些車型i1和i2當B={i1,i2}時，在步驟4中生成b的情況.這里，互補松弛性意味著μ1和μ2的唯一最優(yōu)雙值是在步驟4中為此基對的計算所得.如果在步驟4中生成的另一個基b*有B={i3,i4}并且Ωb*(K)內(nèi)部點共享的最佳值，則φi1、φi2、φi3和φi4必然是共線的.

4）算法的計算復雜度.假定假設(shè)1成立.在計算O(n3)次以內(nèi)，本文算法將生成不超過個基.

注意，由于補償線性規(guī)劃的排除結(jié)構(gòu)，算法實際上是丟棄了大量不經(jīng)濟車型的基.所以上述生成權(quán)威集算法的計算復雜度在實際應用中并不會過于龐大.

計算次數(shù)：由于只是簡單的逐項對比和排序，故算法步驟1-3的計算次數(shù)少于O(n2)次；步驟4因為要執(zhí)行二次方多線性時序運算，以使得對于向量對φi，可為每一個剩余的向量確定它屬于哪個單一界定域，故其執(zhí)行一次只需要不高于O(n3)次計算.由于n3遠大于n2，所以總的計算次數(shù)可認為是在O(n3)次以內(nèi).

3 結(jié)語

本文介紹了一個相對簡單和快速的解決方案，用于解決運輸公司的車隊構(gòu)成問題.為了支持這一總體目標，引入了一個具有新穎特性參數(shù)的車隊構(gòu)成模型，并對該模型進行了技術(shù)分析以促進模型的求解.

專業(yè)運輸車隊要實現(xiàn)以低成本為多個企業(yè)提供快速準時和安全優(yōu)質(zhì)的運輸服務目標，就應以滿足客戶需求為出發(fā)點，以低成本運營為目標來確定恰當?shù)剀囮犚?guī)模和結(jié)構(gòu).本文的研究旨在為運輸車隊的經(jīng)營管理提供一定的理論依據(jù)和決策方法，期望能對企業(yè)的生產(chǎn)實踐活動產(chǎn)生積極的指導作用.