基于多头绒泡菌的交通网络设计算法的研究

摘要

交通网络在人们的日常生活中发挥着重要的作用。近几年，随着城市的扩张，越来越多的人涌入城市，城市内部的交通需求越来越大。另外，随着居民收入的升高，城市之间的社会活动日渐频繁。随着城市人口与私家车的迅速增加，城市交通遇到了前所未有的困难与挑战。交通拥堵现象日益严重，不仅造成了资源的浪费，同时对环境产生了严重的污染。在交通系统中，道路的设计、建设和使用，对用户行为有着重要的影响。合理的交通系统能够在一定程度上减轻道路拥堵现象。因此，如何设计高效，费用低，容错率高的网络成为摆在我们面前的一个亟待解决的问题。
　　根据最近的研究发现，一种名为多头绒泡菌（Physarum polycephalum）的单细胞生物在网络设计、分析与优化方面展现出了惊人的智能特性。在生物实验中，它所设计出的连接各食物源的觅食管道网络在成本、效率和容错性等方面都堪比实际的东京铁路网络。因此，本文提出了基于智能仿生对象-多头绒泡菌的网络优化机理，构提出了构建交通网络的模型。
　　本文首先对多头绒泡菌路径寻优模型进行了拓展，提出了有向网络中的多头绒泡菌路径寻优模型。基于此模型，结合用户的需求情况，建立了路网设计模型，并且将其应用到Mexio路网，中国高速路网以及供应链网络的设计当中。最后，通过具体的参数指标对构建的网络进行了评估。具体来说，本文的工作可以分为以下几个部分:
　　(1)将多头绒泡菌路径寻优模型扩展到有向网络中针对原有模型仅仅适用于无向网络的缺陷，我们对其进行了拓展。通过修改基尔霍夫定律，嵌入检查程序（一旦发现边的方向信息与对应的节点压力信息不符时，我们将这条边的流量修改为0），我们建立了多头绒泡菌解决有向网络路径寻优的模型。同时，我们证明了该模型的收敛性，并且与Dijkstra算法进行了对比。
　　(2)基于多头绒泡菌的最短路径树算法基于有向网络中的多头绒泡菌模型，我们进一步进行了改进。我们将最短路径树中的根节点当作起点，其他的节点当作终点，利用多头绒泡菌算法解决了最短路径树问题。通过在网络上的测试，多头绒泡菌模型得到的结果有效。
　　(3)在动态网路中，基于多头绒泡菌的最短路径树模型在实际中，网络的权重会随着时间而发生变化，因此，在这种情况下，如何重建最短路径树成为一个值得研究的问题。针对传统算法的缺陷，我们从权重增加、权重减少以及权重混合变化三个方面研究了多头绒泡菌算法的自适应性。我们通过在不同的网络上测试之后并且与其他算法相比较，实验结果表明我们提出的算法准确有效。
　　(4)基于多头绒泡菌的路网设计模型多头绒泡菌在觅食的过程中，既要消耗能量，又会从周围的环境中摄取能量，因此，它在不断调整自身的网络结构使之达到最优。利用该机制，我们基于初始的O-D需求，我们通过多头绒泡菌算法迭代一次，记录此时的流量矩阵，再利用多头绒泡菌模型进行优化。我们成功的将该模型应用到Mexico路网以及中国高速路网，通过过滤流量阈值的方式构建了不同的网络拓扑结构。另外，我们通过相关的参数分析了这些网络的优劣。
　　(5)将多头绒泡菌应用到供应链网络设计在供应链网络中，网络中边的花费会随着流量的大小而变化。我们充分利用了多头绒泡菌流量变化的连续性以及多头绒泡菌的自适应性来求解该问题。

目录

声明

摘要

第一章 绪论

1．1 研究背景与意义

1．2 研究现状

1．2．1 路网优化问题研究现状

1．2．2 多头绒泡菌研究现状

1．3 研究内容

1．4 论文组织结构

第二章 相关理论与技术基础

2．1 路网设计理论

2．1．1 网络设计

2．1．2 配流问题

2．1．3 用户均衡模式

2．1．4 系统最优模型

2．2 多头绒泡菌理论简介

2．2．1 多头绒泡菌迷宫模型

2．2．2 自适应网络设计实验

2．2．3 多头绒泡菌路径寻优模型

2．3 本章小结

第三章 多头绒泡菌仿生算法研究

3．1 有向图中的路径寻优算法

3．1．1 模型研究

3．1．2 证明

3．1．3 实验与分析

3．2 多头绒泡菌最短路径树算法研究

3．2．1 基于多头绒泡菌的最短路径树算法

3．2．2 动态网络中的最短路径树算法

3．3 动态网络中的多头绒泡菌的最短路径树算法研究

3．3．1 权重的增加

3．3．2 权重的减少

3．3．3 权重的混合变化

3．3．4 实验与分析

3．4 本章小结

第四章 基于多头绒泡菌的网络设计算法

4．1 基于多头绒泡菌的路网设计算法

4．1．1 模型的建立

4．1．2 实际应用

4．2 基于多头绒泡菌的供应链设计模型

4．2．1 供应链网络设计模型

4．2．2 基于多头绒泡菌的供应链网络设计模型

4．3 本章小结

第五章 总结和展望

5．1 论文工作总结

5．2 未来工作展望

参考文献

发表文章目录

致谢