單車(chē)型動(dòng)態(tài)車(chē)隊(duì)調(diào)度問(wèn)題的時(shí)空分解模型構(gòu)造

李 冰

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

單車(chē)型動(dòng)態(tài)車(chē)隊(duì)調(diào)度問(wèn)題的時(shí)空分解模型構(gòu)造

李 冰

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

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

動(dòng)態(tài)車(chē)隊(duì)調(diào)度； 收益函數(shù)； 時(shí)空分解

0 引言

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

1 問(wèn)題模型的動(dòng)態(tài)規(guī)劃形式

對(duì)問(wèn)題的線性規(guī)劃模型進(jìn)行改進(jìn)，將其表述成動(dòng)態(tài)規(guī)劃形式P1[1]

(1)

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

因?yàn)槟Ｐ偷哪繕?biāo)函數(shù)Ft(Vt,Lt)表示服務(wù)周期內(nèi)時(shí)段t及t以后各時(shí)段的車(chē)隊(duì)調(diào)度方案(xt,yt)所創(chuàng)造的總收益值，故又將目標(biāo)函數(shù)稱(chēng)為總收益函數(shù)[1-4].

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

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

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

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

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

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

2.1.3單時(shí)段單節(jié)點(diǎn)車(chē)輛選擇項(xiàng)排序

2.1.4單時(shí)段單節(jié)點(diǎn)車(chē)隊(duì)調(diào)度

(2)

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

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

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

2.2選擇項(xiàng)收益值分析

1)選擇項(xiàng)為載貨移動(dòng)方式時(shí)的利潤(rùn)rlt或選擇項(xiàng)為空車(chē)移動(dòng)和原地駐留時(shí)的成本cij；

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

(3)

2.3單時(shí)段單節(jié)點(diǎn)車(chē)隊(duì)調(diào)度方案確定過(guò)程的連鎖關(guān)系

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

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

上述單時(shí)段單節(jié)點(diǎn)車(chē)隊(duì)調(diào)度方案確定過(guò)程的連鎖關(guān)系如圖3所示.

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

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

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

凹收益函數(shù)是造成各單時(shí)段單節(jié)點(diǎn)處車(chē)隊(duì)調(diào)度之間不相互獨(dú)立的原因所在，也正是因?yàn)檫@種不獨(dú)立性使得問(wèn)題難于求解.

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

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

由圖4可以看出，當(dāng)(j,t+1)處的凹收益函數(shù)被線性函數(shù)替代后，邊際收益ξj,t+1(Vj,t+1)變?yōu)榱顺Ａ?，同該處的?chē)輛供給量Vj,t+1無(wú)關(guān)，從而也無(wú)需確定時(shí)段t其他各節(jié)點(diǎn)發(fā)往目的地j的車(chē)輛數(shù)，故可直接將(j,t+1)處的邊際收益記作ξj,t+1.

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

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

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

(4)

(5)

(6)

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

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

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

從而為單時(shí)段單節(jié)點(diǎn)決策問(wèn)題增加了一個(gè)新的約束條件

yijt≤uijt，?i,j∈N,

(7)

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

[3] 李冰．動(dòng)態(tài)車(chē)隊(duì)管理問(wèn)題的模型及算法研究[D]．成都：西南交通大學(xué)，2003．

[4] 李冰．確定性動(dòng)態(tài)車(chē)輛調(diào)配問(wèn)題分析[J]．鄭州大學(xué)學(xué)報(bào)：理學(xué)版，2006，38(2)：116-120．

[5] 李冰．隨機(jī)動(dòng)態(tài)車(chē)隊(duì)管理問(wèn)題研究[J]．系統(tǒng)工程，2005，23(1)：96-101．

[6] 李冰．多車(chē)型確定性動(dòng)態(tài)車(chē)輛調(diào)配問(wèn)題[J]．管理工程學(xué)報(bào)，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

國(guó)家自然科學(xué)基金資助項(xiàng)目，編號(hào)71001091，71001090；河南省高等學(xué)校青年骨干教師計(jì)劃項(xiàng)目，編號(hào) 教高〔2008〕708號(hào)；河南省教育廳自然科學(xué)研究計(jì)劃項(xiàng)目，編號(hào)2009A120002.

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