内容发布更新时间 : 2024/6/3 21:28:08星期一 下面是文章的全部内容请认真阅读。

交通系统分析 课程论文

关于最优灾情巡视路线的分析

摘要

本文旨在解决最佳的巡视路线方案的安排问题。对于问题一很明显是一个最佳旅行售货员问题，首先要使3段路的总里程最小（目标函数一）并且要使这3段路尽可能均衡（目标函数二）。我们用Dijkstra算法得到最优树图即O到各个点的最短距离，然后根据合理的选线原则选出合理的线路进行分析。对于巡视路线均衡度则用了数学中的方差的概念p=?i?132(ai?3?aii?13) ， ?=

1p。并设计

了两种方案，通过比较分析其中第二方案较为合适。

对于问题二，基于对问题一结果的分析，我们可以发现分三组的情况下，不能满足题目要求，由于T=2小时，t=1小时，V=35公里/小时,需访问的乡镇共有17个，村共有35个。计算出在乡(镇)及村的总停留时间为17?2?35?69小时，要在24小时内完成巡回，若不考虑行走时间，有:69/k<24(k为分的组数). 得k最小为4，所以至少要分4组。为了均衡性每组的停留小时数应在69/4=17.25h左右（这里没有考虑路上时间）再根据问题一的结论求解。

对于问题三是在不考虑人员数量的情，况下使得总时间最少。并求出了最佳的四条巡视路线及每条巡视路线所需要的时间即可。对于问题三在巡视人员足够多的情况下，巡视距离O点最远的点所用的时间为最短时间，根据最短路径树，从远到近，依次巡视各村镇，在所用时间不大于最短时间的前提下，各组尽可能多的巡视几个村镇，进行分组确立巡视点，并对已巡视过的点进行逐个剔除。通过人工记录，得出分组情况及巡视路线首先我们可以得到离O点最远的H点s=77.5km则最短巡视时间为t=（77.5*2）/35+2=6.43h

关键字： 方差 均衡度 最小生成树 Dijkst r算法

1问题重述

根据题目中的相关信息及巡视路线图，我们需要通过采用数学建模的方法来帮助解决以下问题：

问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。

问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

问题三：在上述关于T , t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

2. 模型的假设与符号说明

2.1模型的假设

2.1.1假设巡视途中只考虑巡视乡（镇）、村，只与巡视路线、时间有关 2.1.2假设第二次经过的乡镇，不计算停留时间；

2.1.3假设对于同一乡镇，如果某一小组停留过，其他小组经过时不计算停留时间；

2.1.4假设经过邻县村不做任何停留；

2.1.5假设汽车在行驶途中车速不变且满足速度要求。 2.1.6假设可使用车辆数量不受限制。

2.2符号说明 a i第i个小组所走路程 衡量均衡度（?越大，均衡度越好；反之，均衡度越差） 巡视一个村（镇）所花时间 汽车的行驶速度 第i个小组巡视所用时间 所求的路程或时间的方差 两相邻点间的距离 小组巡视乡镇的个数 小组巡视村得个数 表示ij两点的相关联取1或0 ? ab iiV hi p l in m x ijm，n ii表示该组停留的乡（镇）和村数 完成巡视时间的下限 tmin 3. 问题分析

此题研究的是某县灾情巡视路线的设计问题。问题要求设计出最佳的巡视路线，即：保证总路程最短或时间最小而且各组尽可能均衡的巡视路线。基于图论相关理论，借助于几何直观和生活体验的启发作用，便于为计算机搜索制定行之有效的操作规则，接着利用图论软件包通过计算机求解出较精确的路线。再通过线路均衡性比较，对均衡性不好的线路进行微调。以此方法确定最佳巡视路线。

针对问题一：基于对问题的分析，借助图论知识，将所给公路网就转化为图论中的加权网络图，因此问题就转化为一个图论问题，即在给定的加权网络图中，寻找从给定点Ｏ出发，行遍所有顶点至少一次再回到Ｏ点，使得总权（路程或时间）最小。此即多个推销员的最佳推销员回路问题。基于以上分析，运用图论知识和图论软件包进行求解，再利用均衡度分析对得到的分组路线进行微调，均衡度越小表示路线越均衡，微调后即可得到相对较优的分组路线。可认为这样设计的分组方法和巡回路线能使总路线近似最短。

针对问题二：在问题一的基础上添加了巡视组在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时等条件，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。首先，由图中数据初步计算后判断分成四组可行，再针对分组为四组的情况进行线路设计，仍将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。

针对问题三：在问题二中关于T , t和V的假定下且巡视人员足够多时，要求在最短时间完成巡视的要求下所得的最佳的巡视路线，此时考虑到从Ｏ点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。基于问题一二中图论的方法，从一些点的路线比较少的点开始，能够使搜素容易进行，因此选择从距离Ｏ点一些较远的点（如12 10 15 22等点）开始搜索，每次搜索时都要对该点的巡视时间进行判断，直到找到近似最优路线。

问题一的解答 4.1模型的建立

4.1.1 目标函数的确定

一共需要分为3个巡视组进行巡视要求总路程最小并且要求均衡度尽可能小。均衡度分析：我们把?称为该分组的实际路程均衡度。?为最大容许均衡度。显然?越大，说明分组的均衡度越好。

通过问题一的分析，建立多目标规划模型。 （1）三组巡视的总路线最短S：

S?min?ai

i?13

（2）巡视路线均衡度：p=?i?13(ai?3?aii?123) ， ?=

1 p我们需要比较所选的?值当其在合理范围内且总路程不是太大时即可,?>0.05就算满足均衡性要求。

目标函数：

3??min?ai ? i?1?min??（3）此问题包含两个方面：第一，对点分组；第二，在每组中寻求最佳推销员回路，即为单个推销员的最佳推销员问题，我们只能去寻求一种较合理的划分准则，求出各部分的最佳推销员回路的权，在进一步进行调整，使得各部分满足均衡性条件。下面根据选线的原则作出了两条比较合理的路线：

4.2问题的求解 1 巡视的路线一 路线 O,M,N,25,20,L,19,J,18,I,15,I,16,17,22,K,21,23,24,27,26,P,O O,1,A,33,31,R,29,Q,28,Q,30,32,35,34,B,C,3,D,4,D,3,2,O O,2,5,6,7,E,8,E,11,G,13,14,H,12,F,10,9,E,5,2,O 路程之和 总路程 208.8 624.6 2 3 205.3 210.5 其中3段路程平均值208.2公里

233?ai1p=? =14.06 , ==0.27（满足均衡度要求）但其路线总长?i?1p)i?1(ai?3度较长。

巡视的路线二 1 路线 O，P，28，27，26，N，24，23，22，17，16，I，15，I，18，K，21，20，25，M，O 路程之和 总路程 191 589.8