详情

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

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