图论在城市规划和交通运输中的数学模型

摘要

二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题和旅行售货员问题已经是图论中的典型问题，本文通过两个实际例子说明最短路问题在山区修建公路和旅行售货员问题灾区巡视路线中的应用。在山区修路中采用将地形图转化为网络图的方法对网络的边的公路、隧道、桥梁分别赋予不同的值，最后求最小成本路线问题就转化为求网络中最短路径的问题。在灾区巡视路线的数学模型属于旅行售货员问题，应用多推销员回路等近似解法制订了三种行驶路线。在本文中根据实际问题的需要选择恰当的算法合理的解决实际需要。

目录

文摘

英文文摘

第一章 绪论

1.1 概述

1.2 相关的研究综述

1.3 研究思路和主要研究方法

第二章 最短路和旅行售货员问题的算法

2.1 最短路问题的算法

2.2 解最优旅行售货员回路的树形搜索分枝定界法

2.3 最小生成树算法解最优哈密尔顿回路

2.4 解近似最优哈密尔顿回路的局部搜索法

2.5 多推销员回路问题

第三章 最短路问题在城市规划中的数学模型

3.1 问题的提出

3.2 摘要

3.3 问题的重述

3.4 问题的分析

3.5 模型的建立与求解

3.6 模型结果分析以及改进

第四章 旅行售货员问题在交通运输中的数学模型

4.1 问题的提出

4.2 问题的重述

4.3 问题分析

4.4 建立模型

4.5 模型求解

结束语与研究展望

参考文献

致 谢