南昌大学数学建模参赛论文--校园最短游览路线

校园最短游览路线

摘要:本文建立了一个游览路线最优化模型.将游览路线问题转化为最佳推销员问题,并用算法去寻求最优解.通过对校园景点图的分析,我们首先把全校路线分为二部分,将图分为二个子图建立了数学模型.将基础实验大楼至医学院这一块分为A区,剩余那块为B区，结果就是这两个的合成.我们采用了一种近似算法的思路，利用Matlab数学软件编程和最小生成树两种方法求出第一部分的最短路径,第二部分的最短路径，两条路径相连接起来,于是我们得到了游览路线的最短路径.本文模型一中我们分别对理、工、文、医四种报考专业的同学根据自己的报考专业制定了四条不同的游览路线, 同时在模型二中给出了所有点都去的最优路线.并通过程序统计出总的路径条数。

关键词：最短路线；H圈；游览路线；二边逐次修正法

1

一 问题的提出

南昌大学校园开放日时，会有许多学生及其家长要求参观新校园.为此校方要在本校高年级学生中招募一批导游，负责接待并陪同考生及其家长乘坐校园游览车（电动平板车）参观游览.路线是从新校园正大门出发，最后返回到出发地.

假设你就是其中的一名导游，为了向所有参观者展现南昌大学的全部风貌和亮点，同时满足参观者了解南昌大学的不同要求，请你制定一份详细的校园游览计划，计划中应包括参观者下车参观的主楼、景点或场地.

具体要求是，根据图一的数据及考生的理、工、文、医四种报考专业，建立数学模型，分别设计4条不同的具体游览路线，使每条游览路线的总路程最短.

校园景点图

2

二 模型的假设

1.两景点除图中给出路径外没有其他的路. 2.游览车在路上不会出现抛锚等现象. 3.游览车在路上的速度总是一定. 4.同一性质景点只参观一次.

三 模型的分析

这是个求游览路线最短的问题,我们可以将关于游览最短路线问题转化为图的最短回路问题进行分析.为了满足不同专业同学了解南昌大学的不同要求，以及展现南昌大学的全部风貌和亮点，我们分别建立了有选择性浏览的模型一和浏览全部景点的模型二. 模型一:

为了满足不同专业同学了解南昌大学的不同要求，同时尽量展现南昌大学的全部风貌和亮点，我们给出了一些必须去的景点，这些景点能满足不同类别参观者的要求.同时在去这些景点的路上，会经过其他类别的景点，这些景点只需在车上观赏就可以.

首先将学校各景点进行分类：

1. 公共类景点:正门,办公楼,学工楼,中心广场,图书馆,保安楼,正气广场,校医院,

体育场所,商业街,学生食堂,宿舍,教学楼,昌海楼,白求恩广场,国际学术交流中心;

2. 理科类景点:理科生命大楼,计算机实验中心,基础实验大楼;

3. 工科类景点:建工楼,机电楼,信工楼,材料楼,环境楼,计算机实验中心, 基础实

验大楼;

4. 文科类景点:人文楼,法学楼,外经楼,艺术楼;

5. 医学类景点:医学院第一、二教学大楼,医学实验大楼.

根据上述分类,各个专业同学必须去的景点为本类别景点和部分公共景点,于是我们对四类专业同学制定了四种不同旅游景点的方案:

理科类: 正门,办公楼,学工楼,中心广场,图书馆,保安楼,正气广场,校医院,体育馆,

商业街,本科公寓C区,学生食堂C,教学楼, 昌海楼,白求恩广场,国际学术交流中心, 理科生命大楼,计算机实验中心,基础实验大楼;

工科类: 正门,办公楼,学工楼,中心广场,图书馆,保安楼,正气广场,校医院,体育馆,

商业街,天健园,本科公寓B区,教学楼, 昌海楼,白求恩广场,国际学术交流中心, 建工楼,机电楼,信工楼,材料楼,环境楼计算机实验中心, 基础实验大楼;

文科类: 正门,办公楼,学工楼,中心广场,图书馆,保安楼,正气广场,校医院,体育馆,

商业街,学生食堂B,本科公寓C区,教学楼, 昌海楼,白求恩广场,国际学术交流中心;

医学类: 正门,办公楼,学工楼,中心广场,图书馆,保安楼,正气广场,校医院,体育馆,

商业街,学生食堂A,本科生公寓A区,教学楼,昌海楼,白求恩广场,国际学术交流中心, 医学院第一、二教学大楼,医学实验大楼.

对于要下车的主楼、景点或场地，我们给出如下约束.各专业参观者在本类别

景点和公共景点中能体现南昌大学亮点的景点.

3

模型二:

这一模型是针对于不区分专业的游客,即游览学校所有的景点.求出游览所有景点的最优路线.

四 模型的建立和求解

将校园简化示意图中每个主楼,景点和场地看作图中的一个节点,各节点之间的路看作图中对应节点间的边,各条路的长度看作对应边上的权,所给示意图就转化为加权网络图.问题就转化为在给定的加权网络图中寻找从给定点出发，行遍所有顶点至少一次再回到出发点使得总权（路程）最小，此即最佳推销员回路问题.

从图中可以注意到从基础实验大楼只有一条路，同时由于图中节点较多,不便于求解，我们将图分为两个区A区,B区.为了进行计算机处理，我们将个节点进行编号，具体见下图中.节点名为景点名和编号.

A区

B区

于是原问题可分解为两个问题:

1.A中由正门出发经过所有点回到正门.

2.B中由基础实验大楼出发经过所有点回到基础实验大楼. (一)模型一求解

在加权图G中求最佳推销员回路是NP-完全问题,我们采用两种近似算法求出该问题的近似最优解,来代替最优解(见文献[4]). 求加权图G（V，E）的最佳推销员回路的算法一：

1.用图论软件包求出G中任意两个顶点间的最短路，构造出完备图G?(V,E?)，

??x,y??E?， ??x,y??MindG?x,y?；

4

2.随机产生G?中若干个H圈，例如20000个

3.所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈；

算法中的完备图是由A区或B区的完备图经过图论软件得到,再通过matlab编程处理得来的. (程序见附录).

图中浏览路线的走法为： 对于A区，从基础实验大楼出发，B区从正门出发，沿着

路线走，遇到分支则打一个转回到圈.例如下图中理科B区路线为:28,29,5,11,16,15,14,13,14,17,18,19,20,19,21,22,23,25,24,9,8,7,2,1,2,7,26,3,4,29,28.也可反过来，其他的以此类推.

理科类A、B区游览路线

工科类A、B区游览路线

5

本文来源：https://www.bwwdw.com/article/sk6d.html