交通規(guī)劃中專用道設(shè)置問題建模和求解研究.pdf

1、交通運(yùn)輸中的路徑規(guī)劃問題是交通規(guī)劃重要的研究領(lǐng)域之一，比較典型的問題有如最短路徑問題(SRP)、旅行商問題(TSP)和車輛路徑問題（VRP）等。隨著社會(huì)生產(chǎn)的進(jìn)步和文化經(jīng)濟(jì)的發(fā)展，交通運(yùn)輸中又不斷地涌現(xiàn)出一些新的實(shí)際問題，如專用道設(shè)置問題（LRP）。專用道設(shè)置問題是指受交通道路資源及運(yùn)輸任務(wù)的特殊要求等的限制，只能在現(xiàn)有交通網(wǎng)絡(luò)中選擇一些路段來設(shè)置專用車道供特殊車輛行駛，才能完成所要求的運(yùn)輸任務(wù)，同時(shí)又要求整個(gè)交通網(wǎng)絡(luò)中設(shè)置專用車道的代

2、價(jià)最小，由此而形成的一類交通運(yùn)輸?shù)穆窂揭?guī)劃問題。專用道設(shè)置問題是運(yùn)籌與優(yōu)化領(lǐng)域一類新的問題，它是涉及到交通、物流、管理、社會(huì)與人文科學(xué)、運(yùn)籌與組合優(yōu)化、計(jì)算機(jī)科學(xué)等眾多學(xué)科知識(shí)的綜合性應(yīng)用研究問題，可應(yīng)用于諸如大型特殊事件中的緊急交通和城市公共交通管理等情況。開展專用道設(shè)置問題的研究具有很強(qiáng)的實(shí)際價(jià)值和理論意義。雖然很早就有在實(shí)際交通管理中采用設(shè)置專用車道這一交通管制措施的做法，但專用道設(shè)置問題作為學(xué)術(shù)問題使用數(shù)學(xué)方法加以定量分析研究的

3、歷史并不長。本論文以專用道設(shè)置問題作為研究對(duì)象，綜合運(yùn)用交通運(yùn)輸學(xué)、運(yùn)籌與組合優(yōu)化和啟發(fā)式算法分析與設(shè)計(jì)等理論知識(shí)及工具方法，在問題的規(guī)范描述和形式化定義、標(biāo)準(zhǔn)專用道設(shè)置問題的數(shù)學(xué)規(guī)劃模型、擴(kuò)展問題的定義及其建模、傳統(tǒng)構(gòu)造式啟發(fā)式算法的分析與設(shè)計(jì)、利用元啟發(fā)式算法框架設(shè)計(jì)混合遺傳禁忌搜索算法及仿真實(shí)驗(yàn)分析等方面展開了系統(tǒng)的研究。
　　在專用道設(shè)置問題中，需要為每一個(gè)運(yùn)輸任務(wù)規(guī)劃一條滿足其要求的一條可行路徑。因而，從完成運(yùn)輸任務(wù)的角

4、度來說，專用道設(shè)置問題屬于交通規(guī)劃中的路徑規(guī)劃問題。本論文分析了路徑規(guī)劃問題的層次劃分，介紹了一些經(jīng)典的路徑規(guī)劃問題，闡述了車輛路徑問題的構(gòu)成要素、數(shù)學(xué)模型、擴(kuò)展問題及其求解算法。通過與這些經(jīng)典問題的比較，重點(diǎn)與相似度最高的具時(shí)間期限的開放車輛路徑問題的比較，提出專用道問題與以往的問題在節(jié)點(diǎn)可被多個(gè)任務(wù)訪問、專用道設(shè)置與使用方式、任務(wù)的時(shí)間限制等方面存在很大不同，是一類新的路徑規(guī)劃問題。
　　作者以舉辦大型運(yùn)動(dòng)會(huì)時(shí)在交通網(wǎng)絡(luò)中設(shè)置

5、專用車道的實(shí)際應(yīng)用為背景，通過分析運(yùn)送任務(wù)的特點(diǎn)和要求、車輛行駛路徑要求、專用道設(shè)置要求與使用方式、專用道設(shè)置后對(duì)其他車輛的影響評(píng)價(jià)等，從規(guī)范和形式化角度較為正式地描述和定義了標(biāo)準(zhǔn)專用道設(shè)置問題，然后構(gòu)建其0-1整數(shù)線性規(guī)劃模型，通過仿真實(shí)驗(yàn)驗(yàn)證模型的正確性和有效性。通過將模型歸約為0-1背包問題得出其為NP-Hard問題，以此作為后續(xù)分析和設(shè)計(jì)近似算法的理論基礎(chǔ)。
　　通過分析專用道設(shè)置問題的構(gòu)成要素，本論文研究了在標(biāo)準(zhǔn)專用道設(shè)

6、置問題基礎(chǔ)上擴(kuò)展出來三個(gè)問題:1）考慮運(yùn)送任務(wù)合并條件下的專用道設(shè)置問題，該問題考慮到將多個(gè)車輛線路合并為一條以減少規(guī)劃線路數(shù)目和降低交通管理成本，其實(shí)質(zhì)是對(duì)車輛行駛的路徑增加了約束條件，即某條路徑中必須包含某些節(jié)點(diǎn)。2）?；愤\(yùn)輸?shù)膶Ｓ玫涝O(shè)置問題，該問題是出于運(yùn)輸車輛的行駛安全考慮。雖然減少了車輛行駛時(shí)間限制的約束條件，但該問題仍然屬于NP-Hard問題。3）多目標(biāo)的專用道設(shè)置問題。該問題增加了目標(biāo)函數(shù)，形成一個(gè)線性規(guī)劃的多目標(biāo)問題。

7、
　　在分析他人提出的啟發(fā)式算法的基礎(chǔ)上，本論文提出了一種基于時(shí)間代價(jià)比選擇策略的啟發(fā)式算法。該算法是一種構(gòu)造式算法，即按照一定的約束條件，每次選擇交通網(wǎng)絡(luò)中時(shí)間代價(jià)比最大的路段來設(shè)置專用道，直到所有運(yùn)輸任務(wù)的時(shí)間約束條件均得到滿足。由于缺少適合專用道設(shè)置問題的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)庫，作者參考Waxman方法和問題本身的一些要求，自行設(shè)計(jì)了實(shí)驗(yàn)的算例。從仿真實(shí)驗(yàn)的結(jié)果來看，作者在本論文提出的啟發(fā)式算法的求解效果比精確算法和其他啟發(fā)式算法更

8、好。
　　元啟發(fā)式算法可以獲得更高質(zhì)量的解。但元啟發(fā)式算法主要是一種算法框架，且每種元啟發(fā)算法由于其原理及方法的原因，都存在著一些不足。本論文提出了混合遺傳禁忌搜索算法，該算法把禁忌搜索算法作為遺傳算法中的局部優(yōu)化算子，可將全局多點(diǎn)并行尋優(yōu)和局部“智能記憶”尋優(yōu)的優(yōu)勢(shì)結(jié)合起來。針對(duì)專用道設(shè)置問題這一具體問題，詳細(xì)設(shè)計(jì)算法框架中的每個(gè)具體規(guī)則、方法和算子等。實(shí)驗(yàn)結(jié)果表明，算法在提高解的質(zhì)量方面非常有效。
　　雖然，不管從深度還