單車型動態(tài)車隊調(diào)度問題的時空分解模型構(gòu)造

李 冰

(鄭州大學 管理工程系 河南 鄭州 450001)

單車型動態(tài)車隊調(diào)度問題的時空分解模型構(gòu)造

李 冰

(鄭州大學 管理工程系 河南 鄭州 450001)

構(gòu)造了問題的動態(tài)規(guī)劃模型，詳細地研究了模型中總收益函數(shù)的凹函數(shù)特性，進而設計線性逼近函數(shù)，構(gòu)造問題的時空分解模型，從而達到將問題時空分解為多個單時段單節(jié)點問題的目的.

動態(tài)車隊調(diào)度； 收益函數(shù)； 時空分解

0 引言

單車型動態(tài)車隊調(diào)度問題描述[1-3]如下：服務周期T被等分為H個時段，運輸網(wǎng)絡中各節(jié)點處分別在這H個時段產(chǎn)生新的運輸任務l，任務l的產(chǎn)生地i，目的地j和服務時間窗均為已知，如果任務l在其時間窗內(nèi)沒有被分配到車輛，則該任務自動消失；現(xiàn)有Q輛同一型號的貨運車輛，且這Q輛車在服務周期開始時在各節(jié)點處的分配情況已知.現(xiàn)在要分別制定服務周期內(nèi)各時段t各節(jié)點i處的車隊調(diào)度方案，使得整個服務周期內(nèi)所能創(chuàng)造的總收益最大.

1 問題模型的動態(tài)規(guī)劃形式

對問題的線性規(guī)劃模型進行改進，將其表述成動態(tài)規(guī)劃形式P1[1]

(1)

其中,xt表示服務周期內(nèi)時段t各節(jié)點處采取載貨移動形式的任務量；yt表示服務周期內(nèi)時段t各節(jié)點處采取空車移動和原地駐留形式的車輛數(shù)量；Vt表示服務周期內(nèi)時段t各節(jié)點處的可調(diào)配車輛數(shù)量；Lt表示服務周期內(nèi)時段t各節(jié)點處可以發(fā)送的任務集合量；rlt表示車輛在時段t發(fā)送運輸任務l所能創(chuàng)造的純利潤；cij表示車輛從節(jié)點i空移到節(jié)點j的成本；xlt為0-1變量，如果時段t運輸任務l分配到一輛車則xlt=1，否則xlt=0；yijt表示時段t從節(jié)點i發(fā)往節(jié)點j的空車數(shù).

因為模型的目標函數(shù)Ft(Vt,Lt)表示服務周期內(nèi)時段t及t以后各時段的車隊調(diào)度方案(xt,yt)所創(chuàng)造的總收益值，故又將目標函數(shù)稱為總收益函數(shù)[1-4].

2 總收益函數(shù)分析

2.1單時段單節(jié)點收益函數(shù)分析

2.1.1單時段單節(jié)點總收益函數(shù)Fit(Vit,Lit)的定義[1]

Fit(Vit,Lit)表示時段t節(jié)點i處的車隊調(diào)度方案(xlt,yit)所能創(chuàng)造的總收益值.因為(i,t)處的車隊調(diào)度方案(xlt,yit)會對時段t以后各時段的車隊調(diào)度方案制定產(chǎn)生影響，所以Fit(Vit,Lit)不僅包括車隊調(diào)度方案(xlt,yit)在時段t所創(chuàng)造的收益，而且包括其對以后各時段的影響.故Fit(Vit,Lit)≠fit(Vit,Lit).

2.1.2Fit(Vit,Lit)的函數(shù)值確定方法

根據(jù)(i,t)處的運輸需求量Lit，對車輛Vit進行合理調(diào)配，從而得到該處的車隊調(diào)度方案(xlt,yit)，代入函數(shù)Fit(Vit,Lit)可求得收益值.由此可以看出，車輛供給量變量Vit直接影響著函數(shù)Fit(Vit,Lit)的取值，所以可以將函數(shù)Fit(Vit,Lit)看作車輛供給量變量Vit的函數(shù)，故又將其簡記為Fit(Vit).

2.1.3單時段單節(jié)點車輛選擇項排序

2.1.4單時段單節(jié)點車隊調(diào)度

(2)

這里稱ξit(Vit)為Fit(Vit)在Vit處的邊際收益，由式(2)可以看出ξit(Vit)等于第Vit+1輛車所創(chuàng)造的總收益值.將函數(shù)Fit(Vit)在Vit處的斜率記作αit(Vit)，因為(i,t)處車輛供給量Vit相對較大，故邊際收益ξit(Vit)可用函數(shù)Fit(Vit)在Vit處的斜率αit(Vit)來近似表示，即

圖1 (i,t)處的凹收益函數(shù)Fig.1 Concave recourse function in region i at time t

在圖1中，αit(m)為總收益函數(shù)Fit(Vit)在m處的斜率，它可用來近似表示(i,t)處車輛供給量Vit為m時，增加一輛車所引起的總收益值改變量，即Fit(Vit)在m處的邊際收益值ξit(m).

2.2選擇項收益值分析

1)選擇項為載貨移動方式時的利潤rlt或選擇項為空車移動和原地駐留時的成本cij；

2)車輛到達目的地(j,t+1)后使得該處增加一輛車輛供給所帶來的收益增加量ξj,t+1(Vj,t+1)，即(j,t+1)處的邊際收益.

(3)

2.3單時段單節(jié)點車隊調(diào)度方案確定過程的連鎖關系

一旦時段t其他各節(jié)點發(fā)往目的地j的車輛數(shù)被確定就可以求得(j,t+1)處的車輛供給量Vj,t+1，從而利用(j,t+1)處的總收益函數(shù)Fj,t+1(Vj,t+1)求得αj,t+1(Vj,t+1)來近似邊際收益ξj,t+1(vj,t+1)，該過程如圖2所示.

圖2 邊際收益值的求解Fig.2 Solution of marginal value in region i at time t

上述單時段單節(jié)點車隊調(diào)度方案確定過程的連鎖關系如圖3所示.

圖3 單時段單節(jié)點車隊調(diào)度方案確定過程的連鎖關系Fig.3 Process of solving fleet scheduling scheme to local problem for each terminal at each time period

由圖3所示的關系圖可以看出，要確定(i,t)處的車隊調(diào)度方案，必須要確定時段t其他各節(jié)點處的車隊調(diào)度方案，由此得知動態(tài)運輸網(wǎng)絡中各單時段單節(jié)點處車隊調(diào)度方案的確定并不相互獨立，而是通過目的節(jié)點在下一時段的車輛供給量相互之間發(fā)生著聯(lián)系，從而使得問題很難分解為一個個相互獨立的單時段單節(jié)點車隊調(diào)度問題，大大增加了問題的求解難度.

2.4凹收益函數(shù)的線性逼近函數(shù)

凹收益函數(shù)是造成各單時段單節(jié)點處車隊調(diào)度之間不相互獨立的原因所在，也正是因為這種不獨立性使得問題難于求解.

考慮將凹收益函數(shù)用線性函數(shù)來近似逼近，如圖4所示.

圖4 (j,t+1)處的線性收益函數(shù)Fig.4 Linear recourse function in region j at time t+1

由圖4可以看出，當(j,t+1)處的凹收益函數(shù)被線性函數(shù)替代后，邊際收益ξj,t+1(Vj,t+1)變?yōu)榱顺Ａ浚撎幍能囕v供給量Vj,t+1無關，從而也無需確定時段t其他各節(jié)點發(fā)往目的地j的車輛數(shù)，故可直接將(j,t+1)處的邊際收益記作ξj,t+1.

由此可知，當單時段單節(jié)點處的凹收益函數(shù)用線性函數(shù)替代后，問題被時空分解為了一個個相互獨立的單時段單節(jié)點車隊調(diào)度問題，從而使問題的求解得到了大大簡化.線性逼近函數(shù)近似處理勢必會對最終求出的解的精度產(chǎn)生一定影響，由于篇幅原因關于精度問題的分析作者將另撰文予以探討.

3 時空分解模型的構(gòu)造

3.1總收益函數(shù)的線性逼近函數(shù)設計

(4)

(5)

(6)

3.2約束條件的調(diào)整

問題的目標函數(shù)(即總收益函數(shù))用式(6)形式的線性逼近函數(shù)替代之后可以分解為一個個單時段單節(jié)點的車隊調(diào)度問題，從而使得求解過程得到大大簡化.但當問題轉(zhuǎn)化為單時段單節(jié)點車隊調(diào)度問題之后，問題的約束也會隨之發(fā)生變化，所以需要對原有的約束條件進行調(diào)整.對新形成的單時段單節(jié)點車隊調(diào)度進行分析可以發(fā)現(xiàn)，載貨車輛數(shù)被任務需求數(shù)所限定，但空移車數(shù)和原地駐留車數(shù)卻缺少必要的限制條件[3,6].基于上述原因，引入一個新的控制變量uijt.

uijt：當i≠j時，表示時段t從節(jié)點i發(fā)往節(jié)點j的空車數(shù)上限；當i=j時，表示時段t在節(jié)點i原地駐留到時段t+1的車輛數(shù)上限，?i,j∈N,t∈T.

從而為單時段單節(jié)點決策問題增加了一個新的約束條件

yijt≤uijt，?i,j∈N,

(7)

3.3時空分解模型的構(gòu)造

根據(jù)對目標函數(shù)和約束條件的調(diào)整，創(chuàng)建新的問題模型P2：

yijt≤uijt，?i,j∈N,i≠j,

模型P2同P1相比其優(yōu)越之處在于問題按時間和空間分解為了一個個單時段單節(jié)點的車隊調(diào)度問題.

4 結(jié)束語

論文構(gòu)造了問題的動態(tài)規(guī)劃模型，詳細分析了總收益函數(shù)的凹函數(shù)特性，進而設計出線性逼近函數(shù)，構(gòu)造了問題的時空分解模型，從而將問題時空分解為一個個單時段單節(jié)點的車隊調(diào)度問題.

[1] 李冰．單車型確定性動態(tài)車輛調(diào)配問題[J]．系統(tǒng)管理學報，2008，17(3)：353-360．

[2] 李冰，王化河．動態(tài)車隊管理問題研究的現(xiàn)狀與展望[J]．公路交通科技，2004，21(4)：109-113．

[3] 李冰．動態(tài)車隊管理問題的模型及算法研究[D]．成都：西南交通大學，2003．

[4] 李冰．確定性動態(tài)車輛調(diào)配問題分析[J]．鄭州大學學報：理學版，2006，38(2)：116-120．

[5] 李冰．隨機動態(tài)車隊管理問題研究[J]．系統(tǒng)工程，2005，23(1)：96-101．

[6] 李冰．多車型確定性動態(tài)車輛調(diào)配問題[J]．管理工程學報，2006，20(3)：52-56．

Spatial-TemporalDissolutionModelinDynamicFleetSchedulingProblemwithHomogeneousVehicleType

LI Bing

(DepartmentofManagementEngineering,ZhengzhouUniversity,Zhengzhou450001,China)

The dynamic programming model was expressed.Then the concavity of recourse function in the model was researched in detail.A particular linear function was devised to approximate the recourse functions.The spatial temporal dissolution model was formulated.The problem by time and space was decomposed into a series of local problems for each terminal at each time period.

dynamic fleet scheduling; recourse function; spatial temporal dissolution

U 492.312； F 540.82

A

1671-6841(2011)03-0078-05

2010-09-20

國家自然科學基金資助項目，編號71001091，71001090；河南省高等學校青年骨干教師計劃項目，編號 教高〔2008〕708號；河南省教育廳自然科學研究計劃項目，編號2009A120002.

李冰(1976-)，男，副教授，博士，主要從事運輸組織優(yōu)化、物流系統(tǒng)優(yōu)化研究，E-mail:lbing@zzu.edu.cn．