經(jīng)過指定中間服務(wù)節(jié)點(diǎn)的抗堵塞路徑選擇研究.pdf

1、如何在出發(fā)前為運(yùn)輸車輛選擇一條抗堵塞路徑使路段堵塞帶來的時(shí)間延誤損失最少具有重要意義?，F(xiàn)有研究或者不考慮路段突發(fā)性堵塞只研究經(jīng)過指定節(jié)點(diǎn)的路徑選擇，或者不考慮經(jīng)過指定節(jié)點(diǎn)只研究從起點(diǎn)到終點(diǎn)的抗堵塞路徑選擇，不能滿足實(shí)際需求。本文針對(duì)任意路段都有可能發(fā)生堵塞的情形，提出路段堵塞對(duì)路徑選擇影響的度量指標(biāo)，建立運(yùn)輸車輛經(jīng)過單個(gè)和多個(gè)指定中間服務(wù)節(jié)點(diǎn)的抗堵塞路徑選擇模型并進(jìn)行求解，為相關(guān)企業(yè)和部門制定路徑選擇方案提供決策依據(jù)。論文的主要工作和成

2、果如下。
　　建立經(jīng)過單個(gè)指定中間服務(wù)節(jié)點(diǎn)的抗堵塞路徑選擇模型并設(shè)計(jì)算法求解。提出路段堵塞對(duì)路徑選擇影響的度量指標(biāo)——路段堵塞損失值。分析堵塞路段在路徑上位于單個(gè)中間服務(wù)節(jié)點(diǎn)之前和之后2種位置關(guān)系，給出路段堵塞損失值的具體計(jì)算方法。計(jì)算任一路徑上每一條路段堵塞損失值的最大值，比較每一條路徑的路段損失值最大值并找出其中的最小值，把它對(duì)應(yīng)的路段所在的路徑稱為單節(jié)點(diǎn)抗堵塞服務(wù)路徑，并結(jié)合抗堵塞服務(wù)路徑本身的長(zhǎng)度選擇出單節(jié)點(diǎn)最優(yōu)抗堵塞服務(wù)

3、路徑。分析網(wǎng)絡(luò)中特殊路段的性質(zhì)分別在一般網(wǎng)絡(luò)中設(shè)計(jì)時(shí)間復(fù)雜性為O(n3)的算法，在方格網(wǎng)絡(luò)中設(shè)計(jì)時(shí)間復(fù)雜性為O(1)的算法進(jìn)行求解，并用MATLAB進(jìn)行編程實(shí)現(xiàn)。結(jié)合實(shí)例驗(yàn)證模型和算法的有效性。
　　建立經(jīng)過多個(gè)指定中間服務(wù)節(jié)點(diǎn)的抗堵塞路徑選擇模型并設(shè)計(jì)算法求解。分析堵塞路段在路徑上位于所有中間服務(wù)節(jié)點(diǎn)之前、經(jīng)過部分指定中間服務(wù)節(jié)點(diǎn)和位于所有中間服務(wù)節(jié)點(diǎn)之后3種位置關(guān)系，給出路段堵塞損失值的具體計(jì)算方法。計(jì)算任一路徑上每一條路段堵

4、塞損失值并找出最大值，每一條路徑均可找出該最大值，從這些最大值中找出最小值，把它對(duì)應(yīng)的路段所在的路徑稱為多節(jié)點(diǎn)抗堵塞服務(wù)路徑，并結(jié)合抗堵塞服務(wù)路徑本身的長(zhǎng)度選擇出多節(jié)點(diǎn)最優(yōu)抗堵塞服務(wù)路徑。分別計(jì)算起點(diǎn)到某個(gè)中間服務(wù)節(jié)點(diǎn)的局部路徑，連接所有中間服務(wù)節(jié)點(diǎn)的局部路徑和某一中間服務(wù)節(jié)點(diǎn)到終點(diǎn)的局部路徑，將這三段局部路徑連接在一起得到從起點(diǎn)出發(fā)經(jīng)過多個(gè)指定中間服務(wù)節(jié)點(diǎn)到達(dá)終點(diǎn)的路徑。分析網(wǎng)絡(luò)中特殊路段的性質(zhì)在一般網(wǎng)絡(luò)中設(shè)計(jì)時(shí)間復(fù)雜性為O(kn3)