高速公路聯(lián)網(wǎng)收費(fèi)ITS中車輛調(diào)度問(wèn)題研討

1、ITS中車輛調(diào)度問(wèn)題研究河南省高速公路聯(lián)網(wǎng)收費(fèi)工作領(lǐng)導(dǎo)小組辦公室 (E-mail: lwb)摘要：在智能交通系統(tǒng)（ITS，Intelligent Transportation Systems）的各個(gè)子系統(tǒng)中，車輛調(diào)度應(yīng)用非常廣泛，但目前大都是針對(duì)物流企業(yè)車輛動(dòng)態(tài)調(diào)度問(wèn)題，很少應(yīng)用ITS問(wèn)題上。本文首先根據(jù)實(shí)際情況，提出ITS中車輛調(diào)度問(wèn)題，并分析了運(yùn)輸網(wǎng)絡(luò)的特點(diǎn)，建立了模型。本文綜合運(yùn)用多種運(yùn)籌技術(shù)，提出一種動(dòng)態(tài)規(guī)劃方法，為車輛調(diào)度問(wèn)題提供了較好的解決方案。最后分析了現(xiàn)實(shí)中運(yùn)輸網(wǎng)絡(luò)狀態(tài)改變的類型與形式，并針對(duì)不同的狀況，提出有效的對(duì)策。關(guān)鍵詞：智能交通系統(tǒng)(ITS)；車輛調(diào)度；運(yùn)輸網(wǎng)絡(luò)；原子規(guī)

2、劃0 引 言智能交通系統(tǒng)（ITS，Intelligent Transports Systems）就是將先進(jìn)的信息技術(shù)、傳感器技術(shù)、數(shù)據(jù)通訊技術(shù)、自動(dòng)控制技術(shù)、運(yùn)籌學(xué)、圖像分析技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)和人工智能等有效地綜合運(yùn)用于整個(gè)交通管理體系,在系統(tǒng)工程綜合集成思想指導(dǎo)下,建立起實(shí)時(shí)、準(zhǔn)確、高效的交通運(yùn)輸綜合體系。在ITS的各個(gè)子系統(tǒng)中，車輛調(diào)度問(wèn)題（VSP，Vehicle Scheduling Problem）具有重要地位和作用，比如公交車輛調(diào)度、交通信息發(fā)布、智能路徑調(diào)度等。車輛調(diào)度問(wèn)題(Vehicle Scheduling Problem)首先由Dantzig和Ramser于1959年提出，它主

3、要探討：組織的行車路線，能否使車輛在滿足一定的約束條件(如需求量、發(fā)送量、車載容量限制、行程限制、時(shí)間限制等)下，有序地通過(guò)一系列供應(yīng)點(diǎn)或需求點(diǎn)，達(dá)到諸如路程最短、費(fèi)用最小，耗費(fèi)時(shí)間盡量少等目的1 7。本文綜合應(yīng)用多種運(yùn)籌技術(shù)，提出一種快速搜索方法，為集貨和送貨一體化、多供應(yīng)點(diǎn)、多需求點(diǎn)、多運(yùn)力點(diǎn)（車場(chǎng)）、單車型條件下的車輛調(diào)度問(wèn)題提供了較好的解決方案，并且分析了現(xiàn)實(shí)中運(yùn)輸網(wǎng)絡(luò)狀態(tài)改變的類型與形式，并提出有效的對(duì)策2 8。1提出問(wèn)題并分析建模1.1 提出問(wèn)題設(shè)某運(yùn)輸網(wǎng)絡(luò)有M個(gè)供應(yīng)點(diǎn)（即S點(diǎn)，下同），N個(gè)需求點(diǎn)（即R點(diǎn)，下同），L個(gè)運(yùn)力點(diǎn)（即C點(diǎn)，下同），每個(gè)運(yùn)力點(diǎn)只能接受自己發(fā)出去的車。每個(gè)S

4、點(diǎn)可供應(yīng)量為si（i=1，2，M），每個(gè)R點(diǎn)的需求量為rj（j=1，2，N），每個(gè)C點(diǎn)可發(fā)出車輛數(shù)為ck（k=1，2，L），車型均相同，載重量都為Q，求滿足貨運(yùn)需求的路程最短的車輛行駛路線；運(yùn)輸網(wǎng)絡(luò)中隨時(shí)可能出現(xiàn)新的S點(diǎn)或R點(diǎn)，求此時(shí)的行車路線規(guī)劃；由于R點(diǎn)的需求量是由經(jīng)驗(yàn)估計(jì)確定的，可能會(huì)發(fā)生估計(jì)需求量大于實(shí)際需求量的情況，需要將已經(jīng)運(yùn)往該R點(diǎn)的貨物運(yùn)回到其它S點(diǎn)或R點(diǎn)3 4。1.2 物流網(wǎng)絡(luò)結(jié)點(diǎn)分析運(yùn)輸網(wǎng)絡(luò)結(jié)點(diǎn)有三類：供應(yīng)點(diǎn)、需求點(diǎn)和運(yùn)力點(diǎn)。各種結(jié)點(diǎn)有如下?tīng)顟B(tài)：Ø 供應(yīng)點(diǎn)有三種狀態(tài)：一般狀態(tài)、無(wú)存貨狀態(tài)、有需求狀態(tài)（只有當(dāng)出現(xiàn)有優(yōu)先供應(yīng)權(quán)的需求點(diǎn)時(shí)，供應(yīng)點(diǎn)對(duì)該需求點(diǎn)表現(xiàn)出這種狀態(tài)

5、）。Ø 需求點(diǎn)也有三種狀態(tài)：一般狀態(tài)、已滿足狀態(tài)、有優(yōu)先供應(yīng)權(quán)狀態(tài)（由于對(duì)需求點(diǎn)需求量的估計(jì)錯(cuò)誤，導(dǎo)致向該需求點(diǎn)的運(yùn)輸數(shù)量超過(guò)實(shí)際需求量，由于需求點(diǎn)貨物的存儲(chǔ)條件差等原因，需盡快將多余貨物運(yùn)回，此時(shí)，運(yùn)輸網(wǎng)絡(luò)中的供應(yīng)點(diǎn)和其它處于一般狀態(tài)的需求點(diǎn)，對(duì)于該需求點(diǎn)來(lái)說(shuō)都是需求點(diǎn)）。Ø 運(yùn)力點(diǎn)有兩種狀態(tài)：有運(yùn)輸能力狀態(tài)、無(wú)運(yùn)輸能力狀態(tài)。1.3 模型建立先對(duì)一般情況下的車輛調(diào)度問(wèn)題建模，而暫不考慮運(yùn)輸網(wǎng)絡(luò)的突發(fā)情況。設(shè)：1，第p個(gè)運(yùn)力點(diǎn)的q號(hào)車從i點(diǎn)行駛到j(luò)點(diǎn)0，第p個(gè)運(yùn)力點(diǎn)的q號(hào)車不從i點(diǎn)行駛到j(luò)點(diǎn)為從供應(yīng)點(diǎn)i點(diǎn)到需求點(diǎn)j點(diǎn)的供貨量，則可得車輛優(yōu)化調(diào)度的數(shù)學(xué)模型如下： i=1，2，

6、M （1） j=1，2，N （2） （3） （4） j=1，2，N （5）0或1 i，j=1，2，M+N+L；p=1，2，L；q=1，2，cp （6） i=1，2，M；j=1，2，N （7）說(shuō)明：dij表示從i點(diǎn)到j(luò)點(diǎn)的距離。約束（1）表示供應(yīng)點(diǎn)i的總供應(yīng)量小于等于其可供應(yīng)量；約束（2）表示需求點(diǎn)j從各供應(yīng)點(diǎn)的供貨量之和等于其總需求量；約束（3）表示任何一個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)向其它結(jié)點(diǎn)發(fā)出的車輛總數(shù)等于接收的車輛總數(shù)；約束（4）表示運(yùn)力點(diǎn)的存有車輛數(shù)大于等于其向供應(yīng)點(diǎn)和需求點(diǎn)發(fā)出的車輛之和；約束（5）表示需求點(diǎn)接收的車輛數(shù)與載重的積大于等于其需求量5 6 10。2 解決方案2.1 為需求點(diǎn)分配運(yùn)輸車輛的

7、原則分析從總行駛里程最少的角度來(lái)考慮，如果給某些需求點(diǎn)都選定了一個(gè)運(yùn)力點(diǎn)，那么從該運(yùn)力點(diǎn)只派一輛車給這些需求點(diǎn)最經(jīng)濟(jì)。但實(shí)際上很難按時(shí)完成運(yùn)輸任務(wù)，也是對(duì)運(yùn)輸能力的浪費(fèi)。所以，這里我們將每個(gè)需求點(diǎn)都至少分配一輛車，并根據(jù)任務(wù)量的大小和時(shí)間的緊迫程度來(lái)分配車輛的數(shù)量。如果某需求點(diǎn)的需求量太少，且任務(wù)時(shí)間寬裕，也可不分配，等其它需求點(diǎn)的車輛完成任務(wù)后，再完成該需求點(diǎn)任務(wù)11。2.2 單車運(yùn)輸情況下的行車路線規(guī)劃1) 為需求點(diǎn)選擇運(yùn)力點(diǎn)：1. 找出各未分配車輛的需求點(diǎn)的包含一個(gè)一般狀態(tài)的供應(yīng)點(diǎn)和一個(gè)有運(yùn)輸能力的運(yùn)力點(diǎn)的最短初等圈或環(huán)；2. 對(duì)所有初等圈或環(huán)進(jìn)行比較，找出總行程最短的初等圈或環(huán)，這樣確

8、定了一個(gè)需求點(diǎn)的運(yùn)力點(diǎn)。3. 設(shè)該運(yùn)力點(diǎn)已經(jīng)派出一輛汽車完成向該需求點(diǎn)的第一次運(yùn)輸，將此時(shí)各結(jié)點(diǎn)的狀態(tài)設(shè)為運(yùn)輸網(wǎng)絡(luò)的最新?tīng)顟B(tài)，重復(fù)步驟1，直到對(duì)所有的需求點(diǎn)都分配完成為止。2) 整車運(yùn)輸部分。設(shè)各車輛都向需求點(diǎn)完成第一次運(yùn)輸，那么此時(shí)的運(yùn)輸網(wǎng)絡(luò)達(dá)到運(yùn)輸規(guī)劃的標(biāo)準(zhǔn)狀態(tài)，可以通過(guò)運(yùn)輸規(guī)劃來(lái)確定下一步的運(yùn)輸任務(wù)。以下兩條原則可以幫助尋找最佳的行車路線：1. 整數(shù)倍原則：如某個(gè)供應(yīng)點(diǎn)向某個(gè)需求點(diǎn)的運(yùn)輸量超過(guò)是汽車載重量的一倍或者幾倍，那么運(yùn)輸量除以汽車載重量的整數(shù)部分要優(yōu)先運(yùn)輸。2. 距離優(yōu)先原則：距離較近運(yùn)輸任務(wù)的優(yōu)先運(yùn)輸。因?yàn)檫\(yùn)輸網(wǎng)絡(luò)是動(dòng)態(tài)的，隨時(shí)可能出現(xiàn)意外情況，我們應(yīng)在最短的時(shí)間內(nèi)完成更多的任

9、務(wù)。由于這兩條原則在某些時(shí)候是矛盾的，我們主張根據(jù)運(yùn)輸網(wǎng)絡(luò)出現(xiàn)意外情況的頻率來(lái)安排這兩條原則的先后次序。如果意外情況出現(xiàn)頻率較高則適用距離優(yōu)先原則；反之則適用整數(shù)倍原則。一般情況下，應(yīng)該在整數(shù)倍原則下使用距離優(yōu)先原則。3） 非整車運(yùn)輸部分。經(jīng)過(guò)上一步，此時(shí)的運(yùn)輸網(wǎng)絡(luò)狀況是yij<Q，當(dāng)然yij（j=1，2，N）可能大于等于Q，yij（i=1，2，M）也可能大于等于Q，那是由于它們所對(duì)應(yīng)的結(jié)點(diǎn)的數(shù)量可能很多，比如一個(gè)S點(diǎn)可能要供給好幾個(gè)R點(diǎn)，一個(gè)R點(diǎn)也可能要從好幾個(gè)S點(diǎn)取貨。下面，我們先介紹在規(guī)劃中需要用的理論和一些規(guī)定：1. 節(jié)約公式。見(jiàn)參考文獻(xiàn)9。2. 運(yùn)輸網(wǎng)絡(luò)結(jié)點(diǎn)狀態(tài)改變假設(shè)。在從R

10、點(diǎn)開始向S點(diǎn)行進(jìn)的過(guò)程中，雖然還沒(méi)有到S點(diǎn)裝車，但是該S點(diǎn)應(yīng)該有一部分貨物已經(jīng)預(yù)分配給該車輛，所以此時(shí)S點(diǎn)的狀態(tài)應(yīng)處于預(yù)變的狀態(tài)。這種狀態(tài)改變（有可能是數(shù)量上的改變或真正的狀態(tài)發(fā)生變化）是隨著車輛從R點(diǎn)發(fā)出就已經(jīng)確定的了。同理，在S點(diǎn)裝車的過(guò)程中，此時(shí)R點(diǎn)也處于預(yù)變的狀態(tài)。在這里，我們假設(shè)車輛在R點(diǎn)開始向S點(diǎn)出發(fā)時(shí)的瞬間同時(shí)改變S點(diǎn)和R點(diǎn)的狀態(tài)，并在狀態(tài)改變的瞬間做出車輛此次運(yùn)輸路線的規(guī)劃。3. 原子規(guī)劃假設(shè)。運(yùn)輸車輛的一次運(yùn)輸過(guò)程可能在幾個(gè)S點(diǎn)上貨，并向很多R點(diǎn)送貨，因此可能影響到很多網(wǎng)絡(luò)結(jié)點(diǎn)的狀態(tài)。為了消除這種影響，我們把車輛從R點(diǎn)發(fā)出到送貨回到R點(diǎn)作為一次原子規(guī)劃，這期間不對(duì)其它R點(diǎn)的車

11、輛進(jìn)行規(guī)劃，該車輛此次運(yùn)輸任務(wù)完成前，也不再對(duì)它分配新的運(yùn)輸任務(wù)，網(wǎng)絡(luò)狀態(tài)也變?yōu)橐?guī)劃后的狀態(tài)。在輪到其它需求點(diǎn)車輛進(jìn)行規(guī)劃時(shí)，以變化后的狀態(tài)為準(zhǔn)。以上三點(diǎn)是行車路線規(guī)劃中主要應(yīng)用的理論，下面給出一個(gè)求可接受解的方法（以下圖中供應(yīng)點(diǎn)為S點(diǎn)，需求點(diǎn)為R點(diǎn)），這個(gè)方法是在考慮到各運(yùn)輸車輛的任務(wù)均衡，在此條件下，對(duì)行車路線進(jìn)行最優(yōu)規(guī)劃：1） 規(guī)劃運(yùn)輸車輛的順序。按當(dāng)前車輛計(jì)劃行駛里程排隊(duì)，選擇最先完成過(guò)去任務(wù)的車優(yōu)先進(jìn)行規(guī)劃。規(guī)劃后車輛重新進(jìn)入排隊(duì)系統(tǒng)。一次只對(duì)一輛車進(jìn)行規(guī)劃，都采用原子規(guī)劃的形式。2） 設(shè)某車在R1點(diǎn)，需向m個(gè)S點(diǎn)取貨。任選某Si點(diǎn)（i=1，2，m），標(biāo)為Si點(diǎn)，裝車后車載貨量為yi

12、1。設(shè)此時(shí)已找到n個(gè)S點(diǎn)，搜索其它S點(diǎn)，若某Sj點(diǎn)使Qyi1> yj1，（i=1，2，n），則標(biāo)為Sj點(diǎn)。設(shè)共找到n個(gè)S點(diǎn)。3） 任意排列n個(gè)S點(diǎn)，每一種排列作為一種策略。1 若在某Sj點(diǎn)（j<n），有yjkQyp1（p=1，2，j），且yjk+yp1+yj1Qyq1（p=1，2，j1；j<qn），則裝上yjk，且將Rj點(diǎn)加入到Sj+1，Sq中，進(jìn)行排列組合規(guī)劃；2 在某Si點(diǎn)，有yijQyk1（k=1，2，n；yk1為在Si點(diǎn)實(shí)際裝車量），則裝上yij，且Rj點(diǎn)加入到剩余的ni個(gè)S點(diǎn)中，進(jìn)行排列組合規(guī)劃，若排列后Rj為最后，且n=m，那么將Rj與R1進(jìn)行排列組合規(guī)劃，找到最

13、優(yōu)路徑，最后回到C點(diǎn)。4） 一次規(guī)劃完成后，車輛重新進(jìn)入排隊(duì)隊(duì)列，等待下一次規(guī)劃。5） 車輛運(yùn)輸任務(wù)均衡調(diào)整。目的是平衡運(yùn)輸任務(wù)量，也可以省略。如各車輛之間的任務(wù)量差距很大，說(shuō)明分配給某個(gè)R點(diǎn)的車輛太少了，應(yīng)多分配一些車輛。也可通過(guò)對(duì)行車路線進(jìn)行調(diào)整來(lái)平衡運(yùn)輸任務(wù)，但這樣做有時(shí)會(huì)造成總行駛里程的增加。我們的原則是在不造成的總行駛里程增加的條件下的調(diào)整各車輛運(yùn)輸任務(wù)的均衡。如任務(wù)量仍很不均衡，則可以通過(guò)調(diào)整運(yùn)輸車輛的數(shù)量來(lái)平衡運(yùn)輸任務(wù)?？梢哉{(diào)整且不造成總行駛里程增加的情況如下例：C1的行車路線：C->R1->S1->R1->R2->C，C2的行車路線：C->R

14、2->S2->R2->S2->R2->S2->R2->C，可以調(diào)整為：C1的行車路線：C->R1->S1->R1->R2->S2->R2->C，C2的行車路線：C->R2->S2->R2->S2->R2->C。下面以一個(gè)最簡(jiǎn)單情況下的例子來(lái)說(shuō)明一次行車路線規(guī)劃方法：設(shè)運(yùn)輸網(wǎng)絡(luò)中有兩個(gè)供應(yīng)點(diǎn)（S1，S2），兩個(gè)需求點(diǎn)（R1，R2），一個(gè)運(yùn)力點(diǎn)（C），其中每個(gè)供應(yīng)點(diǎn)向需求點(diǎn)的供應(yīng)量都小于Q，數(shù)據(jù)如表2.1、2.2：表2.2 結(jié)點(diǎn)距離表S1S2R1R2CS10S2800R17050

15、0R23050800C40600表2.1 供應(yīng)量表R1R2S115S221目前各需求點(diǎn)的運(yùn)輸車輛都只有一輛，分別為C1，C2，汽車載重量都為6，各輛車的已規(guī)劃的行駛里程分別為：200，300，求此時(shí)的行車路線規(guī)劃。解：最先完成已規(guī)劃任務(wù)的C1，則從R1開始規(guī)劃，括號(hào)中的數(shù)為該點(diǎn)的狀態(tài)，第一個(gè)數(shù)是車輛的總行駛里程，第二個(gè)數(shù)是當(dāng)前該車的載重量：S1S2R2R1R1R2CCR2R2S1S1R2R2CC（480|0）（400|3）（350|4）（270|1）（960|0）（900|0）（870|5）（840|0）（540|0）（480|0）（400|1）（920|0）（860|0）（830|5）（80

16、0|0）（520|0）R1（200|0）CCR2R1R1R2S1S1S1R2R2CCR2R2（840|0）（810|5）（780|0）（480|0）（440|0）（360|3）（400|1）（330|4）（480|0）（540|0）（840|0）（870|5）（900|0）（960|0）（900|0）（250|3）S2S1R2（300|2）R2S1R2R1CC（400|0）（440|0）（740|0）（770|5）（800|0）（860|0）（330|3）選擇行車路線的方法：選擇總行程最短的行車路線；當(dāng)行車?yán)锍滔嗤瑫r(shí)，則比較在行駛過(guò)程中的載重量，計(jì)算方法是，將括號(hào)中的第二項(xiàng)相加，選擇和最小的做

17、為行車路線。如還無(wú)法比較出行車路線，則可任選其一。根據(jù)以上分析，本例的行車路線為：C1：R1->S2->R2->S1->R1->C，C2：R2->S1->R2->C?？傂旭偫锍?60，其中C1行駛里程為440，C2為420。若依經(jīng)驗(yàn)安排行車路線，則總行駛里程1000，僅第3）步節(jié)約里程140，可見(jiàn)節(jié)約量還是很大的。以上是按照均衡安排運(yùn)輸任務(wù)的原則安排運(yùn)輸任務(wù)。如果想得到總運(yùn)輸里程最小的行車路線，那么還需先對(duì)C2進(jìn)行規(guī)劃，規(guī)劃方法同上，將規(guī)劃結(jié)果與上述結(jié)果比較，選擇最優(yōu)解。2.3 多車運(yùn)輸情況下的行車路線規(guī)劃現(xiàn)實(shí)中向某個(gè)需求點(diǎn)派出的運(yùn)輸車輛一般多于

18、一輛。根據(jù)需求點(diǎn)需求量的大小和時(shí)間緊迫程度來(lái)決定調(diào)用車輛的多少。我們同樣采取均衡原則，依次分配運(yùn)輸任務(wù)。為需求點(diǎn)選擇運(yùn)力點(diǎn)調(diào)動(dòng)車輛及整車運(yùn)輸部分的方法同單車規(guī)劃。在非整車運(yùn)輸部分，我們將對(duì)每個(gè)原子規(guī)劃產(chǎn)生的小運(yùn)輸任務(wù)進(jìn)行依次分配。由于之前該需求點(diǎn)的各運(yùn)輸車輛的行駛里程相同，所以它們同時(shí)被激活，依次安排任務(wù)，并同時(shí)出發(fā)，完成各自的任務(wù)。例如：需求點(diǎn)R1有三輛運(yùn)輸車輛C1，C2，C3，共有三個(gè)供應(yīng)點(diǎn)S1，S2，S3，數(shù)據(jù)如表2.3、2.4：表2.4 結(jié)點(diǎn)距離表 S1S2S3R1S10S2300S390700R15060500表2.3 供應(yīng)量表S1S2S3R1825 汽車載重量都為6，各輛車的已規(guī)劃

19、的行駛里程為200，求此時(shí)的行車路線規(guī)劃。 解： 經(jīng)過(guò)規(guī)劃得出行車路線：R1->S1->R1->S1->S2->R1->S3->R1。將各原子規(guī)劃分配給各車輛，得出各車輛行車路線。C1：R1->S1->R1，C2：R1->S1->S2->R1，C3 ：R1->S3->R1。3 運(yùn)輸網(wǎng)絡(luò)的意外處理在運(yùn)輸過(guò)程中，常會(huì)出現(xiàn)某些意外情況，對(duì)運(yùn)輸任務(wù)的順利完成產(chǎn)生影響。大致可分為兩種：一種是自然災(zāi)害。如：惡劣的天氣、道路堵塞、車輛故障等，只能通過(guò)人為的調(diào)整、補(bǔ)充運(yùn)輸車輛、路線等方法，進(jìn)行補(bǔ)救；另一種是運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)的改變。

20、如：突然出現(xiàn)一個(gè)新的供應(yīng)點(diǎn)或需求點(diǎn)，或一個(gè)有優(yōu)先供應(yīng)權(quán)的需求點(diǎn)，這時(shí)需要采取措施重新規(guī)劃運(yùn)輸任務(wù)。下面將主要討論第二種情況下的意外處理12 13。3.1 出現(xiàn)新的供應(yīng)點(diǎn)或需求點(diǎn)情況下的意外處理出現(xiàn)新的供應(yīng)點(diǎn)或需求點(diǎn)將會(huì)使運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化，必將會(huì)導(dǎo)致現(xiàn)有運(yùn)輸任務(wù)的重新排定。應(yīng)用前文的運(yùn)輸網(wǎng)絡(luò)結(jié)點(diǎn)狀態(tài)改變假設(shè)，原有的網(wǎng)絡(luò)結(jié)點(diǎn)一律按照本次任務(wù)完成之后的狀態(tài)作為現(xiàn)在的狀態(tài)。將原有結(jié)點(diǎn)和新的網(wǎng)絡(luò)結(jié)點(diǎn)綜合起來(lái)，根據(jù)2.2節(jié)和2.3節(jié)提供的方法，統(tǒng)一規(guī)劃。3.2 出現(xiàn)有優(yōu)先供應(yīng)權(quán)的需求點(diǎn)情況下的意外處理由于對(duì)需求點(diǎn)需求量的估計(jì)錯(cuò)誤，需求點(diǎn)可能出現(xiàn)一種有優(yōu)先供應(yīng)權(quán)的狀態(tài)。此時(shí)應(yīng)將有優(yōu)先供應(yīng)權(quán)的需求點(diǎn)作為供

21、應(yīng)點(diǎn)，原供應(yīng)點(diǎn)變?yōu)樾枨簏c(diǎn)，原運(yùn)力點(diǎn)仍為運(yùn)力點(diǎn)，每個(gè)已經(jīng)分配的運(yùn)輸車輛的處于一般狀態(tài)的需求點(diǎn)都是同時(shí)是一個(gè)運(yùn)力點(diǎn)。完成這次規(guī)劃之后，按規(guī)劃完之后的狀態(tài)（有優(yōu)先供應(yīng)權(quán)的需求點(diǎn)肯定已經(jīng)消失），重新進(jìn)行行車路線規(guī)劃。4 結(jié)論本文通過(guò)對(duì)ITS中車輛調(diào)度問(wèn)題建立數(shù)學(xué)模型，并提出一種簡(jiǎn)便易行的搜索算法，為車輛調(diào)度問(wèn)題提供了較好的解決方案，但還有許多限制條件需要解決，如沒(méi)有考慮到時(shí)間窗的限制、多車型問(wèn)題、汽車滿載/空載時(shí)耗油量的不同等等，這也是我們繼續(xù)研究的方向。參考文獻(xiàn)1 F. Baita, R. Pesenti, W. Ukovich, D. Favaretto. A comparison of diff

22、erert solution approaches to the vehicle scheduling problem in a practical caseJ. Computer & Operations Research,2000,27:1249-1269.2 Yang-Byung Park. A hybrid genetic algorithm for the vehicle scheduling problem with due tmes and time deadlinesJ. International. Journal. Production Economics,2001

23、,73:175-188.3 Sotiris P. Gayialis, Ilias P. Tatsiopoulos. Design of an IT-driven decision support system for vehicle routing and schedulingJ. European Journal of Operational Research,2004,152:382-398.4 M. Desrochers, C.V.Jones, J.K. Lenstra, M.W.P. Savelsbergh, L. Stougie. Towards a model and algorithm management system for vehicle routing and scheduling problemsJ. Decision Support Systems,1999,25:109-133.5 Alan Slater. Specification for a dynamic vehicle r