交通规划中专用道设置问题建模和求解研究

发布时间：2018-01-15 15:21

  本文关键词：交通规划中专用道设置问题建模和求解研究　出处：《广东工业大学》2016年博士论文　论文类型：学位论文

  更多相关文章： 交通规划 专用道设置问题 整数规划模型 启发式算法 混合遗传禁忌搜索算法

【摘要】：交通运输中的路径规划问题是交通规划重要的研究领域之一,比较典型的问题有如最短路径问题(SRP)、旅行商问题(TSP)和车辆路径问题(VRP)等。随着社会生产的进步和文化经济的发展,交通运输中又不断地涌现出一些新的实际问题,如专用道设置问题(LRP)。专用道设置问题是指受交通道路资源及运输任务的特殊要求等的限制,只能在现有交通网络中选择一些路段来设置专用车道供特殊车辆行驶,才能完成所要求的运输任务,同时又要求整个交通网络中设置专用车道的代价最小,由此而形成的一类交通运输的路径规划问题。专用道设置问题是运筹与优化领域一类新的问题,它是涉及到交通、物流、管理、社会与人文科学、运筹与组合优化、计算机科学等众多学科知识的综合性应用研究问题,可应用于诸如大型特殊事件中的紧急交通和城市公共交通管理等情况。开展专用道设置问题的研究具有很强的实际价值和理论意义。虽然很早就有在实际交通管理中采用设置专用车道这一交通管制措施的做法,但专用道设置问题作为学术问题使用数学方法加以定量分析研究的历史并不长。本论文以专用道设置问题作为研究对象,综合运用交通运输学、运筹与组合优化和启发式算法分析与设计等理论知识及工具方法,在问题的规范描述和形式化定义、标准专用道设置问题的数学规划模型、扩展问题的定义及其建模、传统构造式启发式算法的分析与设计、利用元启发式算法框架设计混合遗传禁忌搜索算法及仿真实验分析等方面展开了系统的研究。在专用道设置问题中,需要为每一个运输任务规划一条满足其要求的一条可行路径。因而,从完成运输任务的角度来说,专用道设置问题属于交通规划中的路径规划问题。本论文分析了路径规划问题的层次划分,介绍了一些经典的路径规划问题,阐述了车辆路径问题的构成要素、数学模型、扩展问题及其求解算法。通过与这些经典问题的比较,重点与相似度最高的具时间期限的开放车辆路径问题的比较,提出专用道问题与以往的问题在节点可被多个任务访问、专用道设置与使用方式、任务的时间限制等方面存在很大不同,是一类新的路径规划问题。作者以举办大型运动会时在交通网络中设置专用车道的实际应用为背景,通过分析运送任务的特点和要求、车辆行驶路径要求、专用道设置要求与使用方式、专用道设置后对其他车辆的影响评价等,从规范和形式化角度较为正式地描述和定义了标准专用道设置问题,然后构建其0-1整数线性规划模型,通过仿真实验验证模型的正确性和有效性。通过将模型归约为0-1背包问题得出其为NP-Hard问题,以此作为后续分析和设计近似算法的理论基础。通过分析专用道设置问题的构成要素,本论文研究了在标准专用道设置问题基础上扩展出来三个问题：1)考虑运送任务合并条件下的专用道设置问题,该问题考虑到将多个车辆线路合并为一条以减少规划线路数目和降低交通管理成本,其实质是对车辆行驶的路径增加了约束条件,即某条路径中必须包含某些节点。2)危化品运输的专用道设置问题,该问题是出于运输车辆的行驶安全考虑。虽然减少了车辆行驶时间限制的约束条件,但该问题仍然属于NP-Hard问题。3)多目标的专用道设置问题。该问题增加了目标函数,形成一个线性规划的多目标问题。在分析他人提出的启发式算法的基础上,本论文提出了一种基于时间代价比选择策略的启发式算法。该算法是一种构造式算法,即按照一定的约束条件,每次选择交通网络中时间代价比最大的路段来设置专用道,直到所有运输任务的时间约束条件均得到满足。由于缺少适合专用道设置问题的标准测试数据库,作者参考Waxman方法和问题本身的一些要求,自行设计了实验的算例。从仿真实验的结果来看,作者在本论文提出的启发式算法的求解效果比精确算法和其他启发式算法更好。元启发式算法可以获得更高质量的解。但元启发式算法主要是一种算法框架,且每种元启发算法由于其原理及方法的原因,都存在着一些不足。本论文提出了混合遗传禁忌搜索算法,该算法把禁忌搜索算法作为遗传算法中的局部优化算子,可将全局多点并行寻优和局部“智能记忆”寻优的优势结合起来。针对专用道设置问题这一具体问题,详细设计算法框架中的每个具体规则、方法和算子等。实验结果表明,算法在提高解的质量方面非常有效。虽然,不管从深度还是广度来说,本论文在研究专用道设置问题时取得了一定的进展和成果,但该问题范畴不亚于车辆路径问题,仍有很多问题需要完善和更加深入的研究。
[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.

【学位授予单位】：广东工业大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：U491.12
，

本文编号：1428928