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

论文题目: 不确定环境下交通运输网络路径求解方法及应用研究

论文类型: 博士论文

论文专业: 管理科学与工程

作者: 李引珍

导师: 郭耀煌

关键词: 随机路径,模糊路径,机会规划模型,相关机会规划模型,混合智能算法,交通网络

文献来源: 西南交通大学

发表年度: 2005

论文摘要: 在生产实践中，传统的最短路径问题(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规划模型，并进一步将其转换为一种超图模型，从而可利用基于随机模拟的以顶点优先权编码的混合智能算法求解这一模型，通过计算可为旅客提供最佳换乘路线。在城市交通车辆导航系统中，需要为驾驶人员提供最佳的行车路线。当某些路段或交叉口出现交通拥挤或堵塞时，由于正在运行的车辆会逐渐流入相临路段，因此，一定范围的路阻必然会增大，无庸置疑，“一定范围”是一个模糊概念，即使在这个一定范围内，也会存在对不同路段路阻的影响程度不同的现象。在这种情况下，驾驶人员往往希望车辆导航系统或其它服务系统为其提供一条或多条与“拥挤区域”相异的路径。针对这一类最佳模糊相异路径问题，我们首先提出了κ级关联点和κ级关联边的概念，建立了网络中点边属于该“区域”的隶属度函数，以兰州市为例对模糊相异路径问题进行了计算分析。

论文目录:

摘要

ABSTRACT

第1章绪论

1.1 研究背景及意义

1.2 有关概念及符号

1.2.1 基本概念

1.2.2 图的基本运算

1.2.3 路的基本概念

1.3 网络路径基本算法回顾

1.3.1 最短路问题的数学模型

1.3.2 Bellman最优化原理

1.3.3 无圈网络最短路的递推算法

1.3.4 Dijkstra算法

1.3.5 Ford算法

1.3.6 Floyd算法

1.4 SP问题国内外研究动态评述

1.4.1 基本路径算法时效性方面的研究进展

1.4.2 确定环境下约束网络最短路的研究

1.4.3 不确定环境下网络路径研究进展

1.4.4 交通运输网络路径研究进展

1.5 本文研究的主要内容及特点

第2章交通网络约束路径问题及其智能算法研究

2.1 约束网络路径问题概述

2.2 指定经由约束的铁路货运路径问题及双向定界搜索算法

2.2.1 问题

2.2.2 双向定界搜索算法

2.2.3 指定经由约束的铁路网络货运最短路径

2.2.4 应用情况

2.3 基于顶点优先权和基因权重编码的遗传算法

2.3.1 遗传算法

2.3.2 SP问题与遗传算法

2.3.3 基于顶点优先权和基因权重动态编码的遗传算法

2.3.4 实验分析

2.4 时间依赖网络路径模型及双层优化智能算法研究

2.4.1 问题

2.4.2 数学模型

2.4.3 双层优化智能算法

2.4.4 算例分析

2.5 交通运输网络中相异路径问题及算法研究

2.5.1 多目标SP问题

2.5.2 相异路径

2.5.3 相异路径的α测度概念

2.5.4 相异路径的优化模型

2.5.5 两条相异路径的遗传算法

2.5.6 多条相异路径的遗传算法

2.5.7 多目标相异路径优化模型的求解

第3章随机环境下网络最佳路径计算研究

3.1 随机网络最佳路径问题概述

3.2 基于随机模拟的SP问题的混合智能算法

3.2.1 随机模拟

3.2.2 基于随机模拟的混合智能算法

3.3 期望值模型及算法研究

3.4 最大概率模型及算法研究

3.4.1 优化模型

3.4.2 妥协解及求解方法

3.4.3 Pareto解集及求解方法

3.5 机会约束模型及算法研究

第4章模糊环境下网络最佳路径计算研究

4.1 模糊网络最佳路径问题概述

4.2 模糊集及排序方法

4.3 期望值模型讨论

4.3.1 考虑偏好信息的密度-质量综合型排序

4.3.2 考虑模糊扩散的期望值模型

4.3.3 α置信度下路径的模糊区间求解模型

4.4 模糊机会约束模型

4.5 模糊相关机会规划模型

4.6 基于模糊模拟的智能算法及算例分析

4.6.1 模糊模拟

4.6.2 基于模糊模拟的智能算法

4.6.3 算例分析

第5章兰州市道路公交系统乘车路线及模糊相异路径实例计算分析

5.1 兰州市道路交通网络现状

5.2 随机环境下最佳乘车路线优化模型

5.2.1 0-1规划模型

5.2.2 超图模型及其遗传算法

5.3 兰州市道路公交系统乘车路线实例计算分析

5.4 城市道路交通网络模糊相异路径优化模型

5.5 兰州市道路交通网络模糊相异路径实例计算分析

结论

致谢

参考文献

附录

攻读博士学位期间发表的论文及科研成果

发布时间: 2006-08-02

参考文献

[1].多车型校车路径问题优化算法研究[D]. 侯彦娥.河南大学2016
[2].大规模混载校车路径问题优化算法研究[D]. 党兰学.河南大学2014
[3].考虑环境风险的危险废物回收体系选址—路径问题研究[D]. 赵佳虹.西南交通大学2015
[4].随机车辆路径问题研究[D]. 谢秉磊.西南交通大学2003

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

猜你喜欢