在時間窗條件下應(yīng)急物資運輸路徑優(yōu)化問題研究

陳鋼鐵，帥 斌

（西南交通大學(xué) 交通運輸學(xué)院，四川 成都 610031）

城市應(yīng)急系統(tǒng)的一項重要任務(wù)就是決定城市應(yīng)急運輸路線，要求發(fā)生事故時，救援者能以最快的速度到達現(xiàn)場進行救援。傳統(tǒng)的車輛路徑問題(Vehicle Routing Problem，VRP)是為運輸物資的車輛設(shè)計最佳路徑，使其總運輸費用最小。這個問題是Dantzig和Ramser在解決一個實際汽油運輸問題時提出的[1]。Toth 和Vigo、Laporte建立了多種變形的VRP模型，如有時間窗的VRP模型，有多個供應(yīng)點的VRP模型，動態(tài)選擇路徑的VRP模型，并給出了相應(yīng)的算法[2-3]。與傳統(tǒng)的VRP相比，應(yīng)急物資調(diào)運主要是應(yīng)急車輛在最短的時間內(nèi)把應(yīng)急物資由應(yīng)急服務(wù)點運送到需求點，其研究的核心是最短路徑選擇問題。近年來，隨著應(yīng)急管理的推廣實施，應(yīng)急物資調(diào)度中的車輛路徑選擇與優(yōu)化，成為該領(lǐng)域的一個新的熱點。在應(yīng)急情況下，由于可選擇的路徑有限，因此需要研究在最短的時間求得最優(yōu)化的路徑。

1 問題描述

基于禁止時間窗的應(yīng)急物資調(diào)度車輛路徑問題，在對研究問題進行界定的基礎(chǔ)上，構(gòu)建問題的整數(shù)規(guī)劃優(yōu)化模型。在應(yīng)急情況下，可供選擇的路徑不是很多，可以采用動態(tài)規(guī)劃和標(biāo)號法求解。采用這種算法能在短時間內(nèi)為在時間窗條件下應(yīng)急物資的運輸路徑優(yōu)化求得最優(yōu)解。最后通過實例計算對研究成果進行說明。

現(xiàn)假定在網(wǎng)絡(luò)中的某一節(jié)點nacci發(fā)生一突發(fā)應(yīng)急事件，需要從另節(jié)點nstor緊急調(diào)運應(yīng)急物資。不失一般性，將運輸車輛離開出發(fā)節(jié)點nstor的時間標(biāo)記為基準(zhǔn)時刻0，即nstor＝0，網(wǎng)絡(luò)G中其他節(jié)點和枝線的禁止時間窗均基于該時刻進行定義。則本文所解決的問題就是在禁止時間窗限制下，從網(wǎng)絡(luò)G中選擇節(jié)點nacci到節(jié)點nstor的運輸路徑，使車輛到達應(yīng)急事件發(fā)生節(jié)點的時間最少。

2 模型建立

由于網(wǎng)絡(luò)路徑由節(jié)點和枝線組成，因此通過定義兩組決策變量來確定所選擇的運輸路徑。

在上述定義的基礎(chǔ)上，根據(jù)對問題的界定，可構(gòu)建基于禁止時間窗的應(yīng)急物資調(diào)度車輛路徑問題優(yōu)化模型為：

式中，Snstor和Snacci為節(jié)點nstor和nacci相連枝線的集合；nother為除nstor和nacci以外的其他節(jié)點；Snother為與節(jié)點nother相連枝線的集合；和為運輸車輛在枝線a上的進入和離開節(jié)點。

上述優(yōu)化模型為一個整數(shù)規(guī)劃模型。目標(biāo)函數(shù)⑴式為最小化運輸車輛到達應(yīng)急事件發(fā)生地的時間。⑴式等號右邊第一項為運輸車輛在所選路徑上各節(jié)點的等待時間；第二項為運輸車輛在各枝線的等待時間與行駛時間之和。

約束條件⑵式包含有兩個式子，第一個是確保應(yīng)急物資存儲地點和應(yīng)急事件發(fā)生地點都位于所選路徑上；第二個是保證在與起始節(jié)點和終止節(jié)點相連的所有枝線中，有且只有一條被選中。約束條件⑶式是一個路徑連通性約束，包含有兩個式子，第一個是當(dāng)某一枝線被選中時，其兩端的兩個節(jié)點同時被選中；第二個是確保當(dāng)某一節(jié)點(nstor和nacci除外)被選中時，與其相連的枝線中有且只有兩條被選中。約束條件⑷式是車輛運輸時間遞推約束，包含有兩個式子，第一個將運輸車輛離開應(yīng)急物資存儲地點的時刻定義為0；第二個是通過與節(jié)點相連的枝線，將車輛運輸時間由某一個節(jié)點遞推到與其相鄰的下一個節(jié)點。約束條件⑸式是等待時間約束，通過這兩個式子可分別計算出由于禁止時間窗的限制，運輸車輛在某一節(jié)點或枝線的等待時間。約束條件⑹式為決策變量的定義域約束。

3 模型算法

對于時變條件下有時間窗最短路徑動態(tài)優(yōu)化問題，可以采用動態(tài)規(guī)劃和標(biāo)號法求解。一般對于一個運輸網(wǎng)絡(luò)，在求解過程中可以將其劃分成若干階段，以起始階段由前向后逐段推移，直到最后一個階段結(jié)束為止。

為了獲得各個目標(biāo)值和相應(yīng)的概率，首先，第一層確定時間組合；然后，第二層確定目標(biāo)組合，獲得期望目標(biāo)值。因此，對于任意一個節(jié)點 j 賦以兩個標(biāo)號，標(biāo)號1是確定了時間組合時所獲得的目標(biāo)值、概率和時間，；標(biāo)號2是所有時間組合下的目標(biāo)值。在此，對于任意一個節(jié)點 j 均賦以標(biāo)號q?1)]和標(biāo)號其中，q為節(jié)點 j 的所屬段；為節(jié)點 j 在階段 q 的時間組合；q－1為節(jié)點 i 的所屬的階段；為節(jié)點i在階段q－1的時間組合；Zj為時間組合在從節(jié)點 j 出發(fā)時各個目標(biāo)的期望值，)；Pj為時間組合在到達節(jié)點 j 時各個目標(biāo)的概率，其中，是一個向量，表示在時間組合wtj,η下從節(jié)點 j 出發(fā)的時間；表示在時間組合下到達節(jié)點 j 的時間；EZj為選擇了所有的時間組合后的期望目標(biāo)值，是一個向量，)，為選擇了所有的時間組合后目標(biāo)h的期望值。其中，j∈N?{O}，(i ，j)∈E。

圖1 網(wǎng)絡(luò)運輸圖實例

4 實例計算

利用圖1所示的實例對研究結(jié)果進行說明。圖1中節(jié)點1和節(jié)點7分別為應(yīng)急物資的儲存地點和應(yīng)急事件的發(fā)生地點，節(jié)點和枝線的代號用數(shù)字表示，其禁止時間窗標(biāo)注在節(jié)點代號的下部，枝線代號后圓括號中的數(shù)字為車輛在該枝線上的行車單位時間，利用動態(tài)規(guī)劃和標(biāo)號法求解該實例。

車輛沿著“節(jié)點1→枝線1→節(jié)點2→枝線3→節(jié)點4→枝線9→節(jié)點7”將應(yīng)急物資從儲存地點運送到事發(fā)地點，所消耗的總時間為10。這是從應(yīng)急存儲地點到應(yīng)急事件發(fā)生地點的最短時間。

車輛先從應(yīng)急存儲地點節(jié)點1出發(fā)，選擇枝線1，經(jīng)過2個單位時間行駛到節(jié)點2，在該節(jié)點上需要等待2個單位時間后(禁止時間窗為[2，4])，選擇枝線3，經(jīng)過3單位時間行駛后，于7個單位時間到節(jié)點4，在該節(jié)點上需要等待1個單位時間后(禁止時間窗[5，8])，選擇枝線9，經(jīng)過2個單位時間，于10個單位時間到達節(jié)點7應(yīng)急事件發(fā)生地點。

5 結(jié)束語

帶有禁止時間窗的應(yīng)急物資調(diào)度車輛路徑問題，只考慮時間窗條件下對應(yīng)急物資和救援的路徑的優(yōu)化，而在現(xiàn)實生活和情景中有很多不確定因素對應(yīng)急路徑優(yōu)化產(chǎn)生影響，因此對于在多個不確定因素條件下應(yīng)急路徑優(yōu)化需要進一步的研究。在應(yīng)急路徑中更復(fù)雜的網(wǎng)絡(luò)問題、路徑優(yōu)化及其相關(guān)的算法也是進一步研究的方向。

：

[1] Dantzig G B，Ramser J H. The Truck Dispatching Problem[J].Management Science，1959，6(1)：80-91.

[2]Toth P，Vigo D. The Vehicle Routing Problem，SLAM Monographs on Discrete Mathematics and Application[M].SLAM Publishing，2002.

[3] Laporte，G. The Vehicle Routing Problem，An Overview of Exact and Approximate Algorithms [J]. European Journal of Operations Research，1992(59)：345-358.