FAN(David)Wei,MACHEMEHL Randy,GEMAR Mason,BROWN Leonard

(1.北卡羅來納大學(xué) 夏洛特分校土木與環(huán)境工程系，夏洛特28223，美國；2.德克薩斯大學(xué)奧斯汀分校 交通研究中心，奧斯汀78712，美國；3.德克薩斯大學(xué) 泰勒分校計算機(jī)學(xué)院，泰勒75799，美國)

不確定性條件下的設(shè)備替換優(yōu)化的隨機(jī)動態(tài)規(guī)劃方法

FAN(David)Wei*1,MACHEMEHL Randy2,GEMAR Mason2,BROWN Leonard3

(1.北卡羅來納大學(xué) 夏洛特分校土木與環(huán)境工程系，夏洛特28223，美國；2.德克薩斯大學(xué)奧斯汀分校 交通研究中心，奧斯汀78712，美國；3.德克薩斯大學(xué) 泰勒分校計算機(jī)學(xué)院，泰勒75799，美國)

本文提出了一種解決設(shè)備更新?lián)Q代優(yōu)化（ERO）問題的隨機(jī)動態(tài)規(guī)劃（SDP）模型，用以明確地解釋在車輛利用中的不確定性，并采用Bellman算法解決ERO SDP問題.針對SDP狀態(tài)空間的增長，提出了特殊簡化算法，以解決動態(tài)規(guī)劃方法中固有的“維數(shù)災(zāi)”問題，確保所需的內(nèi)存和計算時間不會隨著時間范圍的增加而成倍增長.并對SDP軟件的實現(xiàn)技術(shù)、功能和圖形用戶界面（GUI）進(jìn)行了討論，開發(fā)了基于SDP的ERO軟件，并使用美國得克薩斯交通局（TxDOT）現(xiàn)有車輛數(shù)據(jù)進(jìn)行驗證.對統(tǒng)計結(jié)果、軟件計算時間和求解效果進(jìn)行綜合分析，結(jié)果顯示，使用該ERO軟件，估計大量成本可以節(jié)省.

系統(tǒng)工程；動態(tài)規(guī)劃；設(shè)備更換；交通運輸

1 引 言

擁有相關(guān)車輛和專用設(shè)備的政府部門和私營機(jī)構(gòu)必須定期決定何時更換和維修自己車隊的車輛.其原因很簡單：隨著車齡的增長，這些車輛會普遍老化，導(dǎo)致運營和維護(hù)（O＆M）成本的上升，以及殘余價值的減少.新的更有效和更保值的車輛可能出現(xiàn)在市場中并能用于更換.車輛的老化和技術(shù)的更新，經(jīng)常需要好的設(shè)備更新決策[1].此外，決策通常是基于一個目標(biāo)，也就是在有限的或無限的使用時間內(nèi)盡量減少包括收購，運營和維護(hù)成本，以及殘值的使用維修成本.

許多關(guān)于設(shè)備更新?lián)Q代優(yōu)化（ERO）的研究已經(jīng)在開展中，包括美國得克薩斯交通局（TxDOT）正在進(jìn)行的設(shè)備替換優(yōu)化的研究.關(guān)于目前已在全球商業(yè)車隊管理系統(tǒng)的先進(jìn)系統(tǒng)，先進(jìn)的研究方法和實際應(yīng)用的詳細(xì)文獻(xiàn)和回顧，讀者可以在一個單獨的研究報告里詳細(xì)了解到[1].總之，對于目前的設(shè)備更新?lián)Q代優(yōu)化相關(guān)研究工作，可以從算法求解的角度來劃分為三類：

（1）最小等效年度成本（EAC）方法.

它采用的假設(shè)是沒有技術(shù)變革，而成本是一直固定的（例如，一個新的車輛可以用相同的成本來購買替換舊的車輛）.這種EAC的做法會通過權(quán)衡高的更換成本和隨著時間的推移越來越多的O＆M成本，來決定最優(yōu)的設(shè)備更換年齡，以利于使用維修成本的最小化.一旦確定，則該車輛應(yīng)連續(xù)在達(dá)到這個更換年齡時以固定的成本被重復(fù)取代[1].

（2）基于經(jīng)驗/規(guī)則的方法.

美國許多州的交通局使用這種基于經(jīng)驗/規(guī)則的方法，來作出保持/更換決定，特別是在ERO相關(guān)研究的早期階段，這種方法很常用[1].例如，Tx-DOT使用年齡，設(shè)備累計利用率，以及設(shè)備維修累計費用值作為輸入，用于設(shè)備更新決策[1,2].這方面的基于經(jīng)驗/規(guī)則的方法在某些情況下可以很好地加以利用來解決ERO問題.然而，這種方法很大程度上取決于車隊經(jīng)理的判斷，以及在ERO相關(guān)領(lǐng)域的工作經(jīng)驗.

（3）動態(tài)規(guī)劃.

還有就是對有限車輛使用時間范圍內(nèi)的ERO問題的確定動態(tài)規(guī)劃（DDP）的研究[3-9].通過在一個給定的決策時間范圍內(nèi)，DDP可以在每個階段內(nèi)（通常每年一次）作出是否更換或保留的決定.這個決策通常是基于預(yù)期的購買成本，每年的運營和維護(hù)成本，和殘值所決定的使用維修成本的最小化.兩個典型的動態(tài)規(guī)劃（DP）的方法，包括Bellman’s[4,5]或Wagner’s[6]，都可以用來求解ERO問題.一些有據(jù)可查的案例顯示[3,7]，DDP可以顯著節(jié)約成本.

如前所述，用DDP來優(yōu)化求解ERO設(shè)備替換決策的決定是基于在一個在給定的決策時段內(nèi)對預(yù)期的購買成本，每年的O＆M成本和殘值的綜合考慮.然而，這種方法存在一個明顯的缺點.例如，無論是車輛使用，還是每年的O＆M成本，DDP都假定它們?yōu)椴蛔兓蚩梢灶A(yù)定.但由于在實際操作中的隨機(jī)性，這些設(shè)備預(yù)計利用率通常不會在實踐中真正實現(xiàn)，因此決定了設(shè)備替換優(yōu)化決策在某些時候無效，（使DDP決定非最優(yōu)），甚至?xí)懿睿ㄔ谀承O端情況下）.在這種情況下，隨機(jī)動態(tài)規(guī)劃（SDP），它可以明確地考慮車輛利用率的不確定性，以及相應(yīng)的每年O＆M成本，無疑將被作為首選的方法來用以解決ERO問題.Meyer[10]是其中的極少數(shù)研究不確定性條件下的ERO問題的作者，這可能是由于計算能力的限制.隨著計算技術(shù)的進(jìn)步，很多研究工作已經(jīng)在過去十年中研究開展了不確定性下的ERO問題，這可以通過很多Hartman的研究工作[11]中看出.然而，這些以前的研究工作中沒有一個真正使用實際中的車輛設(shè)備成本/設(shè)備使用數(shù)據(jù).所有這些以前的案例研究都是有限的，并都基于小例子.因此，這些給出的結(jié)果是否有說服力，它們是否可以隱含/擴(kuò)展到現(xiàn)實世界的應(yīng)用中，都很值得懷疑.因此，ERO SDP問題的許多基本特性仍有待進(jìn)一步探討和確定.據(jù)我們所知，本文是第一個針對現(xiàn)實世界應(yīng)用的ERO SDP方法（使用的是TxDOT目前的車隊數(shù)據(jù)），該方法可以明確地考慮車輛利用率的不確定性，以及相應(yīng)于每年的O＆M成本[12].作者認(rèn)為，這個先行的以SDP為基礎(chǔ)的工作是很廣泛通用的，做了許多關(guān)于ERO的非常廣泛的敘述，并可以作為一個例子來演示SDP是很有前途的.當(dāng)收集有足夠多的成本/設(shè)備使用里程數(shù)據(jù)，這個SDP的優(yōu)化解決方案，就可以立即投入使用，在未來很多年內(nèi)都會在全球車隊管理業(yè)中產(chǎn)生可觀的成本節(jié)約.

本文的其余部分安排如下：第2節(jié)介紹了ERO SDP問題的模型建立.第3節(jié)介紹了基于SDP解決方案的算法.應(yīng)用了Bellman方法來解決ERO SDP問題.特別注意了SDP狀態(tài)空間的增長和特殊算法簡化方法的詳細(xì)介紹.第4節(jié)介紹的案例研究中，基于了對現(xiàn)實世界使用兩個典型車輛類別（classcodes）作為例子的TxDOT車輛數(shù)據(jù)系統(tǒng)全面的數(shù)值分析，給出了很多結(jié)果.最后，第5節(jié)總結(jié)了未來的研究方向，并討論總結(jié)全文.

2 模型構(gòu)建

求解程序被分成三個具體步驟：①合適的階段和狀態(tài)的定義；②最優(yōu)值函數(shù)的定義；③一個有遞歸運算關(guān)系的構(gòu)建[13-16].

2.1 階段和狀態(tài)

由于TxDOT車隊經(jīng)理在每年年初會做是否保留或更新車輛的決定，很自然的，我們要把每年作為考慮的一個階段.因此，我們指的是年數(shù)（或指數(shù)）為階段變量和在每年年初的車輛年齡和累計利用水平（即行駛里程）作為狀態(tài)變量.為了演示的方便，我們先介紹以下數(shù)學(xué)符號：

設(shè)置/指數(shù)/輸入變量

i0——設(shè)備單元在起始階段的年齡；

j0——設(shè)備單元在起始階段的累計利用水平（表示為行駛里程數(shù)）；

Y——設(shè)備單元在起始階段的正在等待保持/更新決策的本年度值；

N——用戶指定的要考慮保持/更新決策的最大規(guī)劃時限；

nk——年k內(nèi)所有可能的設(shè)備利用水平數(shù), k=Y,Y+1,…,Y+N-1；

mtk——年k內(nèi)每個離散度指標(biāo) tk的車輛的平均車輛利用率（表示為行駛里程數(shù)）, tk=1,2,…,nk,k=Y,Y+1,…,Y+N-1；

lk——年k內(nèi)用來表示實際的平均車輛利用率實現(xiàn)里程水平mtk,k=Y,Y+1,…,Y+N-1；——在水平lk的設(shè)備單元的使用（表示為行駛里程數(shù)）（在年初已經(jīng)累計利用 j)，并在今年的決定年 k結(jié)束時該設(shè)備轉(zhuǎn) i-歲, i=i0+1,i0+2,…,i0+N；

p(Ui+1,j+lk,lk+1|Ui,j,lk)——在今年的決定年k+1，設(shè)備單元被利用在水平lk+1的概率，在今年結(jié)束該設(shè)備轉(zhuǎn) (i+1)-歲；給定在決定年k，設(shè)備單元被利用在水平lk的概率，在年結(jié)束該設(shè)備轉(zhuǎn) i-歲；

Pk——設(shè)備的于年k內(nèi)新單位的采購成本, k=Y,Y+1,…,Y+N-1；

上面的符號表示設(shè)備的購買成本(Pk)是與年度相關(guān)的.每年的運營和維護(hù)成本(Ci,j,lk)和設(shè)備單元的使用情況(Ui,j,lk)也均是以年齡為基礎(chǔ)的.而每年車輛利用水平的概率分布也與累積到?jīng)Q定年的總里程數(shù)相關(guān).殘值(Si,Y0,j,lk)不僅取決于車型年及設(shè)備的年齡，而且還取決于其在出售時的累積里程.正如在另一篇文章中論述[1]，所有的成本/行駛里程數(shù)據(jù)及其可能相關(guān)概率分布，都來自基于SAS Macro的數(shù)據(jù)清潔和分析儀，并將作為輸入到基于SDP的優(yōu)化引擎.此外，應(yīng)該指出的是，作為一個標(biāo)準(zhǔn)做法，在DP模型和求解過程中，我們已經(jīng)對在每一個階段的所有成本（如每年的O＆M成本，包括所有的維修，定期維修和停機(jī)時間/懲罰成本，殘值，以及采購成本新車型年）都已使用了通貨膨脹率來完成從裝備車型年（設(shè)備購置成本）和/或日歷年（每年的O＆M成本及殘值）到基準(zhǔn)年的轉(zhuǎn)換.

2.2 最優(yōu)值函數(shù)

對于任何給定的階段和狀態(tài)，最優(yōu)值函數(shù)被定義為一個函數(shù)，返回從該點到規(guī)劃期結(jié)束最小的總成本.特別是對于本文中的ERO問題，最優(yōu)值函數(shù)的定義如下：

2.3 遞歸計算關(guān)系

本文中的ERO SDP問題可以表示如下：對于一個在年初k已經(jīng) i-歲與項目累計利用j的設(shè)備,車隊經(jīng)理有兩種決策可能：要么保留或替換.再次注意，無論決定是“保持”或“替換”，該設(shè)備單元仍將會在整個這一年k中使用的.因此，這年中擁有相同的概率分布的年度營運及維護(hù)成本，并將會被包括在不同決策方案中來并成為所有成本中的一部分.下面呈現(xiàn)兩種可能的情況.

案例一：假設(shè)選擇的決策是保持i-歲設(shè)備累計利用 j.然后，即這階段的成本是 Ci,j,lk及概率p(Ui+1,j+lk,lk+1|Ui,j,lk),lk=m1,m2,…,mtk.因為作為此操作的結(jié)果是下一個階段和狀態(tài)為k+1和i+1與累積利用率j+lk,從該處到?jīng)Q策結(jié)束時的最小總成本，根據(jù)定義，為1(i +1,j+lk).因此，自然能得到的是，與保持動作相關(guān)的最好的總成本由下式給出：

案例二：假設(shè)所選擇的決策是更換i-歲設(shè)備累計利用j.然后，即這階段成本的總和：Pk(年k內(nèi)一個新單位設(shè)備的購買價格),-Si+1,Y0,j+lk,lk+1(負(fù)殘值，在今年決定年末時 (i+1)-歲設(shè)備累計利用 j+lk，在決定年年初k時i歲設(shè)備累積利用率 j),和 Ci,j,lk及概率p(Ui+1,j+lk,lk+1|Ui,j,lk),lk=m1,m2,…mtk

(在該決定年訂購一個新的設(shè)備單位時，現(xiàn)在(i+1)-歲設(shè)備累計利用 j+lk的年運營和維護(hù)成本）.因為下一個階段和狀態(tài)作為此操作的結(jié)果是k+1和年齡0行駛里程為0,從該處到?jīng)Q策結(jié)束時的最小總成本，根據(jù)定義，為(0 ,0).因此，由此可見，與替換動作相關(guān)聯(lián)的可能的最佳總成本由下式給出:

由于ERO問題的目標(biāo)是最小化總成本，遞歸

3 SDP解決方案方法

圖1顯示了一個完整的“保持或替換”Bellman方法的例子，其中在每年年初的決定可以是保留或取代.另外請注意，這個ERO SDP問題開始于一個全新的設(shè)備單元，并是個對車輛利用率不確定性條件下SDP-2級方法已經(jīng)進(jìn)行了場景簡化處理.在圖1，方形節(jié)點表示決定保留或更換設(shè)備單元.圓形節(jié)點表示機(jī)會節(jié)點，作為設(shè)備的利用率水平是不確定的，從節(jié)點所采取的路徑?jīng)Q定了在下一階段中的設(shè)備累積利用率.從圓形節(jié)點所采取的路徑被定義為u1和u2，這代表了兩種可行的（即高，低）設(shè)備利用率水平.此外，在時間N的所有節(jié)點都連接到一個在時間N+1的虛擬節(jié)點，這表示最終階段之后設(shè)備單元的殘值.應(yīng)該還指出，總成本包括采購成本，預(yù)計每年的O＆M成本和如上文所敘的殘值.

4 實例應(yīng)用

正如DDP[3]，本文開發(fā)的基于SDP解決方案的ERO軟件較為通用，可用于在車輛利用率不確定情況下（如全新車輛或二手車、有或無年度預(yù)算），提供設(shè)備保持或更換決定.換言之，本文提供的解決方案，給設(shè)備保持或更換提供了一個一般性的指南.本節(jié)將例示并討論在不考慮預(yù)算限制的條件下，使用我們開發(fā)的ERO軟件來作出特定車輛類別中的全新車輛的保持/更換決定（即保持多少年，詳見4.3節(jié)）的結(jié)果.此外，需要指出的是，所有的數(shù)值結(jié)果都會或多或少取決于所選擇的特定車輛類別的全新車輛.然而，在進(jìn)行全面的測試后發(fā)現(xiàn)，所有車輛類別的數(shù)值結(jié)果似乎都遵循某種類似的模式，并表現(xiàn)出一些共同的特征.基于這點，下面的章節(jié)將使用真實的TxDOT TERM數(shù)據(jù)（從1999年至2011年），并分別使用和介紹兩個典型的車輛類別（即420010和520020來作為輕型汽車和重型汽車的例子），來描述一些有趣的并有代表性的數(shù)值結(jié)果.

圖1 一個完整的“保持-替換”的在車輛利用率不確定性條件下的ERO SDP問題：SDP-2級場景簡化處理Fig.1 A complete“keep-replace”SDP formulation for the ERO problem with uncertainty in asset utilization:the two-level case after conducting the scenario reduction treatment

4.1 統(tǒng)計分析結(jié)果及其啟示

正如前面所提到的，以前所有的研究工作都僅僅局限于人造的小例子，沒有人使用過實際生活中車隊的成本/使用數(shù)據(jù).可以想象，在這樣的研究情況下，所得到的數(shù)值結(jié)果顯然不能被應(yīng)用并推廣到現(xiàn)實生活中.由于本文使用了Tx-DOT目前車隊的實際數(shù)據(jù)，并開發(fā)了第一個基于SDP解決方案的ERO軟件，得出的許多有關(guān)ERO的結(jié)論都可以被推廣，并將為今后的諸多研究工作提供許多有益的參考.綜合計算結(jié)果表明[1]，隨著車型年的增加，非經(jīng)通脹調(diào)整的原總車輛購買成本也會顯著增加.然而，如果考慮到通貨膨脹率，經(jīng)通脹調(diào)整后的總車輛購買成本似乎會先開始減少，然后會一直逐漸提高，雖然這種模式還不是很清晰可見.這可能是因為隨著技術(shù)的進(jìn)步，車輛通常會變得更加昂貴.因此，基于絕對美元價值的車輛購買成本通常會逐年增加.然而，如果考慮經(jīng)濟(jì)的通脹率，結(jié)果就會更復(fù)雜，并會使得經(jīng)通脹調(diào)整后的總車輛購買成本的預(yù)測變得更不可靠和不可預(yù)知.這種結(jié)果可能表明，我們要先更好地預(yù)測原車輛購買成本，然后對此成本進(jìn)行通脹調(diào)整，而不能直接預(yù)測調(diào)整后的總車輛購買成本.

綜合數(shù)值還顯示了其他一些非常有趣的結(jié)果.例如，隨著車輛年齡的增長，每英里的總的運營和維護(hù)（O＆M）成本（或每小時總的O＆M成本）也會增加.這說明，隨著多年來車輛技術(shù)的進(jìn)步，新的車輛也會變得更省油.另外重要的一點是，由于車輛的老化，無論是車輛利用率還是使用時間（即實際使用情況，以英里或小時計），都會明顯減少.而且，隨著車輛的老化，調(diào)整后的總的O＆M成本會先開始增加，然后減少.停機(jī)時間也表現(xiàn)出相同的模式，也就是說，它最初會增加，然后會隨著車輛的老化而減少.同樣，這兩種現(xiàn)象可解釋為，隨著車輛的老化，車輛的燃油效率會減低和車輛停機(jī)的風(fēng)險會增加.因此，調(diào)整后的總的O＆M成本開始會增加，停機(jī)時間也可能會增加（尤其是當(dāng)車輛使用率近乎相等的情況下）.另一方面，由于車輛的老化，車輛利用率會降低.這兩種效應(yīng)會相互抵消直到一個點，在該點后，由于較低的車輛使用率而導(dǎo)致的O＆M成本的降低將更明顯，因此調(diào)整后的總的O＆M成本將開始逐漸下降.同樣的解釋也適用于車輛停機(jī)時間.車輛利用率的下降會迫使車輛停機(jī)時間，在某一點后逐漸地降低[1].

4.2 解決方案的計算時間

本文使用基于SDP解決方案的的ERO軟件，并對所有車輛類別的計算時間進(jìn)行了檢查.結(jié)果顯示，SDP2-級方法的計算時間是非常均勻的，ERO軟件需要大約10秒的時間來為每個CLASSCODE提供最佳的車輛保持或更換的優(yōu)化決定，這種運行時間和DDP方法幾乎是相同的[3].因此，它一共需要約32分鐘的時間來優(yōu)化所有（即194）車輛類別的解決方案，并輸出到相關(guān)的Excel文件中.然而，SDP3-級的方法似乎是不太均勻，大部分車輛類別都需要更多的時間來運行，ERO軟件需要大約30秒的時間來為每個車輛類別提供在不確定的車輛利用率條件下，最佳的車輛保持或更換的優(yōu)化決定.因此，ERO軟件需要總共約97分鐘才能優(yōu)化所有（即194）車輛類別并往相關(guān)的Excel文件中輸出所有優(yōu)化的解決方案.其中，ERO軟件中使用的SDP“當(dāng)前趨勢”的方法使用了基于歷史數(shù)據(jù)的車輛利用率的概率分布的預(yù)測.而且，這樣對于每一個和所有車輛類別的SDP方法的結(jié)果，清楚地表明了我們需要對SDP狀態(tài)空間進(jìn)行場景減少處理.結(jié)果也顯示，在執(zhí)行場景減少處理后，計算機(jī)內(nèi)存和解決方案的計算時間呈線性（而不是指數(shù)）的增長，正如我們所需要的那樣.

4.3 解決方案的質(zhì)量比較和分析結(jié)果

利用車輛類別中的420010和520020車輛，本文比較了DDP的解決方案，SDP2-級和SDP3-級的優(yōu)化解決方案，以及現(xiàn)有標(biāo)桿解（目前的TxDOT使用的基準(zhǔn)解決方案）.所有解決方案的解，以及解的質(zhì)量的具體比較，都被詳細(xì)列于表1中.可以看出，相對于兩個車輛類別對應(yīng)的現(xiàn)有標(biāo)桿解，所有優(yōu)化方法的目標(biāo)函數(shù)值（費用$值表示）都更?。ń飧茫?這都是預(yù)料之中的，因為每一種優(yōu)化方法，都可以確保在DP后退求解的過程中，所有的解決方案的路徑（當(dāng)然包括純粹的基于經(jīng)驗的現(xiàn)有標(biāo)桿解解決方案），都會被檢索到.這保證了在一定的決策時間里（由基準(zhǔn)年確定）擁有最低總成本的最佳解決方案都能被找到.

此外，人們可能會注意到，對于DDP，SDP-2級和SDP-3級方法的解和現(xiàn)有標(biāo)桿解解決方案的總成本都不同.這是預(yù)料之中，因為DDP方法使用基于車輛類別預(yù)期成本/行駛里程的預(yù)測來計算未來基準(zhǔn)年數(shù)的決定，而SDP的兩種方法都產(chǎn)生并使用了基于每一個和所有車輛的利用水平，成本和行駛里程（低高2級，或低中高3級）及其相關(guān)概率的預(yù)測，來計算未來基準(zhǔn)年數(shù)的決定.這可能會導(dǎo)致在不同的解決辦法之間，預(yù)期費用/里程數(shù)據(jù)也都會略有不同.

表1 Classcodes420010和520020的 SDP和DDP優(yōu)化的解決方案，與現(xiàn)有標(biāo)桿解的質(zhì)量比較Table1 Solution quality comparisons between the SDP and DDP optimized solutions and the current benchmark solutions for classcodes 420010 and 520020

使用CLASSCODE 420010的“當(dāng)前趨勢”方法為例，可以從表1中看出，基于SDP 2-級解決辦法的結(jié)果最為節(jié)省，該方法建議在20年的窗口內(nèi)更換5次，而現(xiàn)有標(biāo)桿解解決方案建議只在10年和20年進(jìn)行更換.而SDP3-級解決方案和DDP的解決方案提供類似的替代策略，節(jié)省花費的區(qū)別都來自于和每種方法相關(guān)的預(yù)期成本的差異.這些結(jié)果表明，采用本文開發(fā)的基于SDP的ERO軟件可以顯著提高設(shè)備更換過程，并在每年可以節(jié)省大量成本.具體而言，對于車輛類別420010，預(yù)計可節(jié)省約$5 464.40/20=273.22美元（每年每一個單一的車輛設(shè)備）.車輛類別520020在SDP2-級求解建議在6年、13年和20年更換，而且估計的成本節(jié)約是$8 631.65/20=431.58美元（每年），這比DDP或SDP 3-級解決方案大得多.這兩個車輛類別的平均成本節(jié)約為（273.22美元+431.58美元）/ 2=352.40美元（每年）.考慮有使用的TxDOT 194車輛類別和平均每車輛類別包括84件車輛設(shè)備，可以預(yù)料352.40美元×194×84=$5 742 730.77的節(jié)省成本.另外還可以從表1看出，如果采用相同的計算方法來估算，SDP3-級方法可以在總成本上顯著節(jié)省$2 506 389.98.因此，可以預(yù)料使用這種SDP方法能帶來每年數(shù)百萬美元的成本節(jié)省.

5 研究結(jié)論

本文提出了一種隨機(jī)動態(tài)規(guī)劃（SDP）的優(yōu)化模型，應(yīng)用了Bellman算法來實施解決ERO SDP問題，可以明確地解釋在車輛利用率不確定性條件下的優(yōu)化.特別注意到SDP狀態(tài)空間的增長，有效地提出了特殊算法簡化方法，以解決動態(tài)規(guī)劃方法中固有的“維數(shù)災(zāi)”問題，以確保所需的計算機(jī)內(nèi)存和解決方案的計算時間不會隨著時間范圍的增加而成倍增長.對所開發(fā)的基于SDP的ERO軟件進(jìn)行了測試，并使用美國得克薩斯交通局（TxDOT）現(xiàn)有車輛隊列的數(shù)據(jù)進(jìn)行驗證.本文中的開發(fā)基于SDP解決方案的ERO軟件很通用，可用于在車輛利用率不確定性條件下能為全新和和二手車，有和沒有年度預(yù)算，進(jìn)行最佳保持/更換決定的考慮.計算結(jié)果顯示如果使用該ERO軟件，估計大量成本可以節(jié)省.其他特性，比對如統(tǒng)計分析和該軟件計算時間和解決方案的質(zhì)量，也進(jìn)行了描述.所開發(fā)的基于SDP的ERO軟件已經(jīng)顯示出大有希望和令人鼓舞的成果.

因為概率車輛的利用率是明確備考慮的，在制定SDP模型和開發(fā)Bellman解決辦法在理論上合理和實際上切實可行.然而，由于一些車輛類別/設(shè)備單元缺乏足夠大而可靠的數(shù)據(jù)，相比于DDP求解，SDP軟件產(chǎn)生的結(jié)果也許不太可靠.但隨著可以預(yù)期的數(shù)據(jù)收集工作的積累，更可靠的結(jié)果，可以由此來實現(xiàn).未來的研究將導(dǎo)向于進(jìn)一步了解這些目標(biāo)并提供應(yīng)用和解決不確定性下的ERO問題的現(xiàn)實情況.此外，對不確定的未來采購成本，以及停機(jī)時間成本對ERO保持/更換決定造成的影響，目前也正在研究.使用SDP優(yōu)化（即以概率分布的資產(chǎn)利用率更換決策的影響）也會進(jìn)一步研究，并可通過Monte Carlo模擬量化.每個和一切車輛類別的ERO問題更多的計算結(jié)果也有待洞察，隨著此項研究的日趨成熟，將很快到來.

致謝

作者要衷心感謝美國得克薩斯交通局（Tx-DOT）贊助的研究項目0-6412“設(shè)備更新優(yōu)化”.作者也承認(rèn)鄧肯·斯圖爾特，唐·劉易斯，羅恩·哈奎斯特，瓊·穆勒和TxDOT的凱倫·丹尼斯及其工作人員對本研究的發(fā)展過程中的輸入和反饋所提供的經(jīng)驗豐富的貢獻(xiàn).

[1]Fan W,Machemehl R,Kortum K.Equipment replace?ment optimization:Part I.solution methodology,statisti?cal data analysis,and cost forecasting[C]//Transportation Research Record-Journal of Transportation Research Board and Proceedings of the 90 th Annual Transporta?tion Research Board Meeting,2011:88-98.

[2]TxDOT equipment replacement model-TERM,2004[R/ OL].Accessed on January 20,2009,ftp://ftp.dot.state.tx. us/pub/txdot-info/gsd/pdf/txdoterm.pdf

[3]Fan W,Machemehl R,Gemar M.Equipment replace?ment optimization:Part II.dynamic programming-based optimization[C].//Submitted for Publication in 2012 Transportation Research Record and Presentation at the 91stAnnual Meeting of the Transportation Research Board,2012.

[4]Bellman R E.Equipment replacement policy[J].Journal of the Society for the Industrial Applications of Mathe?matics,1995,3:133-136.

[5]Bellman R E.Dynamic programming[M],Dover Publica?tions,2003.

[6]Wagner H M.Principles of operations research[M].Pren?tice-Hall,Englewood Cliffs,NJ,1975.

[7]Waddell R.A model for equipment replacement deci?sions and policies[J].Interfaces,1983,13(4):1-7.

[8]Hartman J C.A note on‘a(chǎn) strategy for optimal equip?ment replacement’[J].Production Planning&Control, 2005,16(7):733-739.

[9]Hartman J C,Murphy A.Finite-horizon equipment re?placement analysis[J].IIE Transactions,2006,38(5): 409-419.

[10]Meyer R A.Equipment replacement under uncertainty [J].Management Science,1971,17(11):750-758.

[11]Hartman J C,Rogers J L.Dynamic programming ap?proaches for equipment replacement problems with con?tinuous and discontinuous technological change[J].IMA Journal of Management Mathematics,2006,17(2):143-158.

[12]Fan W,Machemehl R,Gemar M,et al.A stochastic dy? namic programming approach for the equipment replace?ment optimization with probabilistic vehicle utilization [C].//the Transportation Research Board,National Re?search Council,Washington DC,2012.

[13]Hillier F,Lieberman G.Introduction to operations re?search,8thEdition[M].,Tata McGraw-Hill Education, 2005.

[14]Wolsey L A.Integer programming[M].New York:Wiley, 1998.

[15]Nemhauser G L,Wolsey L A.Integer and combinatorial optimization[M].New York:Wiley,1999.

[16]Bertsekas D P.Dynamic programming and optimal con?trol,2ndedition[M].Belmont,MA:Athena Scientific, 2001.

A Stochastic Dynamic Programming Approach for the Equipment Replacement Optimization under Uncertainty

FAN(David)Wei1,MACHEMEHL Randy2,GEMAR Mason2,BROWN Leonard3
(1 Department of Civil and Environmental Engineering,University of North Carolina at Charlotte,Charlotte 28223,U.S.A；2 Center for Transportation Research,University of Texas atAustin,Austin 78712,U.S.A；3 Department of Computer Science,University of Texas at Tyler,Tyler 75799,U.S.A.)

In this paper,a stochastic dynamic programming(SDP)based optimization model is formulated for the equipment replacement optimization(ERO)problem that can explicitly account for the uncertainty in vehicle utilization.The Bellman approach is developed and implemented to solving the ERO SDP problem. Particular attention is paid to the SDP state-space growth and special scenario reduction techniques are developed to resolve the“curse of dimensionality”issue that is inherent to the dynamic programming method to ensure that the computer memory and solution computational time required will not increase exponentially with the increase in time horizon.SDP software computer implementation techniques,functionalities and the Graphical User Interfaces(GUI)are discussed.The developed SDP-based ERO software is tested and validated using the current Texas Department of Transportation(TxDOT)vehicle fleet data.Comprehensive numerical results,such as statistical analyses,the software computational time and solution quality,are described and substantial cost-savings have been estimated by using this ERO software.

systems engineering；dynamic programming；equipment replacement；transportation

1009-6744（2014）03-0076-09

N94

A

2012-10-10

2013-10-23錄用日期：2014-01-28

FAN(David)Wei(1974-)，男,副教授.*通訊作者：wfan7@uncc.edu