详情

原文传递不确定环境下交通运输网络路径求解方法及应用研究

论文题名：	不确定环境下交通运输网络路径求解方法及应用研究
关键词：	城市交通;交通网络;路径规划;随机优化
摘要：	在生产实践中，传统的最短路径问题(Shortest Path Problem，简称SP)有其应用的局限性，应用最多的是SP的衍生问题，如约束路径问题，多目标多权路径问题，以及不确定环境下的随机路径问题、模糊路径问题等。在诸如交通、军事、通讯、计算机及管理科学等学科领域中，不确定环境下的约束SP问题占有相当重要的地位。　　自1959年Dijkstra对基本SP问题提出其有效算法以来，许多学者对此问题进行了深入而大量的研究，主要表现在两个方面：算法时效性研究和SP衍生问题的研究。尽管以Dijkstra算法为代表的基于Bellman优化原理的一些经典算法被认为是最有效的算法，但随着网络规模的增大，或在实际应用中需要反复多次计算最短路时，其算法的时效性将表现得极为乏力，甚至因实时控制的要求，致使算法无法在允许的时限内实现。特别对于SP的衍生问题，如约束路径问题或不确定环境下的路径问题，传统算法已不再适用。　　二十世纪70年代至80年代中期，国内外对SP问题的研究处于低谷状态。之后，尤其进入90年代后期，随着计算机应用学科的发展，特别是通讯、交通等学科的发展需要，使得对SP问题的研究又一次成为国内外学者研究的热点。对于不确定环境下的网络路径问题，有不少学者在寻求最精确解的方法方面进行了大量的研究，并对不同性质的实例研究取得了令人瞩目的成果。然而，本文认为，由于事实上模型本身的不精确性，如随机函数和模糊函数的确定等都具有不精确性，即使求出模型意义下的最优解，在实际应用中也是难以实施的。　　因此，本文另辟途径，就国内外目前尚少有研究的约束网络SP问题的遗传算法以及不确定环境下SP问题的机会约束模型和相关机会规划模型进行研究分析，以基本SP问题的遗传算法为核心，针对约束网络和不确定环境下SP问题的特征，设计了基于顶点优先权和基因权重编码的混合智能算法求解此类模型，并利用所建模型和设计算法，对随机环境下城市公交换乘问题及城市道路交通网络模糊相异路径问题进行了实例分析研究。　　 SP的衍生问题非常之多，应用非常之广。约束网络路径问题就是一类SP的衍生问题，而且往往是其它衍生问题的核心子问题。以交通运输网络为背景，本文首先对铁路运输中应用非常广泛的具有指定经由约束的SP问题进行研究，提出了多项式时间的双向定界搜索算法。进一步针对一般约束网络路径的难解性，提出基于顶点优先权和基因权重的动态编码的快速遗传算法，并以此作为求解网络路径的基本算法，利用双层优化技术，通过逼近内层染色体的适应度函数值，求解交通运输网络中有重要应用价值的时间依赖网络路径问题。此外，提出了交通运输中具有重要应用价值的相异路径问题，给出了具有对称性的α相异度概念及计算方法，这是一类带约束的路径问题，也可认为是一类多目标路径问题，文中给出了相应的智能算法，利用该算法可求出路径长约束下最佳相异度路径，或相异度约束下最短路径，对多目标问题，可计算得到Pareto解集。　　对于随机环境下的网络最佳路径问题，传统的研究方法主要是建立在期望值模型和最大概率模型基础上的，并且近期国内外的研究成果大多数都是在下列假设条件下进行的：点或弧具有相互独立的随机分布，且分布函数是解析可计算的。本文在不受上述假设条件的情况下，更有一般性，首先研究并给出了随机分布的期望值、方差、概率等特征值的随机模拟方法，在研究期望值模型和最大概率模型解法的基础上，对传统的期望值模型进行扩展，提出了更有实用价值和普遍意义的乐观和悲观期望值模型，方差约束模型，建立了以概率最大和路径最短为准则的多目标随机网络模型，进一步提出并建立了网络最佳路径的机会约束模型。针对随机环境下的SP问题，建立了基于随机模拟的以顶点优先权编码的混合智能算法。　　相对确定环境和随机环境而言，国内外对模糊环境下网络最佳路径的研究成果较少，且已有的研究成果大多数是建立在模糊数扩展和基础上的。本文首先对基于模糊集可能性质量型排序理论与方法的网络最佳路径进行了分析研究，实际上，这是一种从不同的角度计算模糊变量期望值的方法，最终将模糊变量清晰化，使问题变为确定性问题。然而，本文作者认为，从模糊性的本质来讲，模糊问题的解应该具有模糊性，因此，我们通过研究α截集下最佳和最劣路径的计算，可给出不同α下的模糊路径的取值区间。此外，本文利用模糊可能性测度理论，建立了网络最佳路径的模糊机会约束模型和模糊相关机会规划模型。最后，在研究并给出模糊变量的期望值、α悲观值、乐观值及可能性等特征值的模糊模拟方法的基础上，提出并设计出了基于模糊模拟的以顶点优先权编码的混合智能算法。　　作为本文主要研究模型和算法的应用，对兰州市城市道路公交系统最佳乘车路线问题及模糊相异路径问题进行了实例计算与分析。在随机走行时间和换乘有随机延误的环境下，建立了换乘问题的0-1规划模型，并进一步将其转换为一种超图模型，从而可利用基于随机模拟的以顶点优先权编码的混合智能算法求解这一模型，通过计算可为旅客提供最佳换乘路线。　　在城市交通车辆导航系统中，需要为驾驶人员提供最佳的行车路线。当某些路段或交叉口出现交通拥挤或堵塞时，由于正在运行的车辆会逐渐流入相临路段，因此，一定范围的路阻必然会增大，无庸置疑，“一定范围”是一个模糊概念，即使在这个一定范围内，也会存在对不同路段路阻的影响程度不同的现象。在这种情况下，驾驶人员往往希望车辆导航系统或其它服务系统为其提供一条或多条与“拥挤区域”相异的路径。针对这一类最佳模糊相异路径问题，我们首先提出了k级关联点和k级关联边的概念，建立了网络中点边属于该“区域”的隶属度函数，以兰州市为例对模糊相异路径问题进行了计算分析。
作者：	李引珍
专业：	管理科学与工程
导师：	郭耀煌
授予学位：	博士
授予学位单位：	西南交通大学
学位年度：	2005
正文语种：	中文