本文關(guān)鍵詞：交通規(guī)劃中專用道設(shè)置問題建模和求解研究　出處：《廣東工業(yè)大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 交通規(guī)劃 專用道設(shè)置問題 整數(shù)規(guī)劃模型 啟發(fā)式算法 混合遺傳禁忌搜索算法

【摘要】：交通運(yùn)輸中的路徑規(guī)劃問題是交通規(guī)劃重要的研究領(lǐng)域之一,比較典型的問題有如最短路徑問題(SRP)、旅行商問題(TSP)和車輛路徑問題(VRP)等。隨著社會生產(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è)置專用車道的代價(jià)最小,由此而形成的一類交通運(yùn)輸?shù)穆窂揭?guī)劃問題。專用道設(shè)置問題是運(yùn)籌與優(yōu)化領(lǐng)域一類新的問題,它是涉及到交通、物流、管理、社會與人文科學(xué)、運(yùn)籌與組合優(yōu)化、計(jì)算機(jī)科學(xué)等眾多學(xué)科知識的綜合性應(yīng)用研究問題,可應(yīng)用于諸如大型特殊事件中的緊急交通和城市公共交通管理等情況。開展專用道設(shè)置問題的研究具有很強(qiáng)的實(shí)際價(jià)值和理論意義。雖然很早就有在實(shí)際交通管理中采用設(shè)置專用車道這一交通管制措施的做法,但專用道設(shè)置問題作為學(xué)術(shù)問題使用數(shù)學(xué)方法加以定量分析研究的歷史并不長。本論文以專用道設(shè)置問題作為研究對象,綜合運(yùn)用交通運(yùn)輸學(xué)、運(yùn)籌與組合優(yōu)化和啟發(fā)式算法分析與設(shè)計(jì)等理論知識及工具方法,在問題的規(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ù)的角度來說,專用道設(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)動會時(shí)在交通網(wǎng)絡(luò)中設(shè)置專用車道的實(shí)際應(yīng)用為背景,通過分析運(yùn)送任務(wù)的特點(diǎn)和要求、車輛行駛路徑要求、專用道設(shè)置要求與使用方式、專用道設(shè)置后對其他車輛的影響評價(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è)置問題基礎(chǔ)上擴(kuò)展出來三個(gè)問題：1)考慮運(yùn)送任務(wù)合并條件下的專用道設(shè)置問題,該問題考慮到將多個(gè)車輛線路合并為一條以減少規(guī)劃線路數(shù)目和降低交通管理成本,其實(shí)質(zhì)是對車輛行駛的路徑增加了約束條件,即某條路徑中必須包含某些節(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)問題。在分析他人提出的啟發(fā)式算法的基礎(chǔ)上,本論文提出了一種基于時(shí)間代價(jià)比選擇策略的啟發(fā)式算法。該算法是一種構(gòu)造式算法,即按照一定的約束條件,每次選擇交通網(wǎng)絡(luò)中時(shí)間代價(jià)比最大的路段來設(shè)置專用道,直到所有運(yùn)輸任務(wù)的時(shí)間約束條件均得到滿足。由于缺少適合專用道設(shè)置問題的標(biāo)準(zhǔn)測試數(shù)據(jù)庫,作者參考Waxman方法和問題本身的一些要求,自行設(shè)計(jì)了實(shí)驗(yàn)的算例。從仿真實(shí)驗(yàn)的結(jié)果來看,作者在本論文提出的啟發(fā)式算法的求解效果比精確算法和其他啟發(fā)式算法更好。元啟發(fā)式算法可以獲得更高質(zhì)量的解。但元啟發(fā)式算法主要是一種算法框架,且每種元啟發(fā)算法由于其原理及方法的原因,都存在著一些不足。本論文提出了混合遺傳禁忌搜索算法,該算法把禁忌搜索算法作為遺傳算法中的局部優(yōu)化算子,可將全局多點(diǎn)并行尋優(yōu)和局部“智能記憶”尋優(yōu)的優(yōu)勢結(jié)合起來。針對專用道設(shè)置問題這一具體問題,詳細(xì)設(shè)計(jì)算法框架中的每個(gè)具體規(guī)則、方法和算子等。實(shí)驗(yàn)結(jié)果表明,算法在提高解的質(zhì)量方面非常有效。雖然,不管從深度還是廣度來說,本論文在研究專用道設(shè)置問題時(shí)取得了一定的進(jìn)展和成果,但該問題范疇不亞于車輛路徑問題,仍有很多問題需要完善和更加深入的研究。
[Abstract]:The path planning problem in traffic transportation planning is one of the important research fields, typical problems such as the shortest path problem (SRP), the traveling salesman problem (TSP) and the vehicle routing problem (VRP). With the development of social production and the progress of cultural economy, transportation is constantly emerging some practical problems, such as Lane Setting Problem (LRP). Lane setting problem refers to the traffic resources and transport tasks to the special requirements of the restrictions, only to set up special lane for special vehicle selection in some sections of the existing traffic network, to complete the required transport task, at the same time the price setting lanes and the whole traffic network in the minimum path planning problem for a class of transportation which is formed. The problem set lane is a new field of operations research and optimization problem, which is related to Transportation, logistics, management, social sciences and the humanities, operations research and combinatorial optimization, computer science and so on comprehensive application of knowledge, emergency transportation and city public traffic management can be used in applications such as large special events. It has a strong practical value and theoretical significance to carry out research on Lane set problem although very early on. By setting the lanes of traffic control measures in the actual traffic management practices, but the lanes as academic problems using mathematical methods to quantitative analysis of the history is not long. The lane setting problem as the research object, the integrated use of transportation, logistics and combinatorial optimization and heuristic algorithm analysis and design theory of knowledge and tools and methods, in the definition of description and formal problem specification, mathematical problem for standard setting Planning model, definition and modeling propagation problems, analysis and design of the traditional heuristic algorithm, researched by using meta heuristic algorithm framework design of hybrid genetic tabu algorithm and simulation analysis of search. Set problems in lane, a need to meet a feasible path for the requirements of transportation a mission planning. Therefore, from the perspective of completing the task, Lane setting problem belongs to the path planning problem in traffic planning. This paper analyzes the hierarchical path planning problem, introduces some classical path planning problem, expounds the key elements, the mathematical model of vehicle routing problem, expansion problem and its solution by comparing with the classical algorithm. These problems, more focused and the highest similarity with the time limit of the open vehicle routing problem, put forward special question Problems with previous problems in the node can be multiple tasks access lanes and use, there is a big different task time limit, is a kind of new path planning problem. The practical application of setting lanes in traffic network the author to organize large-scale games as the background, characteristics and requirements of transport through the analysis of the task, the vehicle driving route, lanes and lanes, after the impact on other vehicle evaluation, from the specification and formal point of view is formally described and defined the problem of setting standard lanes, then construct the 0-1 integer linear programming model, the correctness and effectiveness of the simulation results verify the model. The model is reduced to the 0-1 knapsack problem is NP-Hard problem, as the subsequent analysis and design approximation algorithm theoretical basis. Through the analysis of College Set the problem with road elements, this paper set the problem based on the standard Lane expansion out of three questions: 1) consider the problem of setting special road transport tasks with conditions, taking into account the problem of multiple vehicle lines into a number of lines to reduce planning and reduce transportation management costs its essence is on the path of vehicles increased constraints, which contains some nodes of.2 must be a certain path) problem set for the transportation of dangerous goods, the problem is considered for driving safety of transport vehicles. Although constraints reduce vehicle travel time limit, but the problem still belongs to NP-Hard.3 the problem of multi-objective) Lane setting. The problem increases the objective function, the formation of a multi-objective linear programming problem. Based on the analysis of the heuristic algorithm proposed by others on the A heuristic algorithm based on time cost ratio selection strategy. This algorithm is a structural algorithm, namely according to certain constraints, each time the traffic network cost than the largest section to set up special lanes, until all the transportation task time constraints are met. Due to the lack of standard test database suitable for lane setting problems, some of the requirements according to the Waxman method and the problem itself, we designed the experimental examples. From the simulation results, the heuristic algorithm proposed in this paper by solving the effect than the exact algorithm and other heuristic algorithms better. Meta heuristic algorithm can obtain higher quality solutions but meta heuristic algorithm is mainly an algorithm framework, and each kind of meta heuristic algorithm due to its principle and method, there are some defects. This paper presents The hybrid genetic tabu search algorithm, the algorithm of tabu search algorithm as a local optimization operator of genetic algorithm, the multi point parallel global optimization and local optimization of "intelligent memory". It combines the advantages of a specific problem in lanes, each with specific rules of design optimization framework, and methods operator. Experimental results show that the algorithm can improve the quality of the solution is very effective. Although, no matter from the depth or breadth, this paper set up in the study of lane has made some progress and achievements, but the problem is not less than the vehicle routing problem, there are still many problems to be improved and more in-depth study.

【學(xué)位授予單位】：廣東工業(yè)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：U491.12
，

本文編號：1428928