搜索
1灾情巡视路线的数学模型摘要本文解决的是灾情巡视路线的设计问题。由于路线图可看成网络图因此此问题可转化为在给定的加权网络图中寻找从给定点Ｏ出发行遍所有顶点至少一次再回到点Ｏ使得总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型进行求解。对于问题一：基于设计分三组巡视时使总路程最短且各组尽可能均衡的巡视路线的要求我们采用Dijkstra算法，通过对初始圈进行二边逐次修正,处理三组的巡视路线长度，用lingo软件求解出较优方案。定义分组的均衡度系数a检验分组均衡度，在均衡度为a=0.0751时得到分三组（路）巡视时，总路程最短且各组尽可能均衡的巡视路线见附表1。对于问题二：将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。利用lingo软件求得，至少要分四组，且四组的近似最优巡视路线见附表2。对于问题三：基于问题一二中图论的方法，考虑到从Ｏ点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。求得的最短时间为6.43小时，最佳巡视路线分为23组。（具体分组见附录二）对于问题四：由于组数一定，T，t和V改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组均衡的条件下T，t和V允许的最大变化范围。关键词：启发式算法Dijkstra算法均衡度图论二边逐次修正21.问题重述1.1问题背景今年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。附录一中给出了该县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。1.2本文需解决的问题问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。问题三：在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。2.模型的假设与符号说明2.1模型的假设假设1：公路不考虑等级差别，不受灾情和交通情况的影响。假设2：各条公路段上的汽车行驶速度均匀。假设3：各巡视组巡视的乡（镇）、村不受行政区划分的影响。假设4：各巡视组行动统一，一个巡视组不可再分成若干小组。假设5：巡视当中在每个乡（镇）村的停留时间一定，不会出现特殊情况而延误时间。2.2符号说明符号符号说明T巡视小组在乡（镇）巡视的停留时间t巡视小组在村巡视的停留时间V汽车行驶速度3iCiC为导出子图中的最佳Ｈ圈。（其中i=1，2，3，…，n.）)(iCw)(iCw为iC的权，（其中i=1，2，3，…，n.）最大允许均衡度0分组后的实际均衡度il第i个点距起始点的路线长度)(HwH点的时间权重n分组数ia第i组巡视时要停留的乡（镇）数ib第i组巡视时要停留的村数mint最短时间下限jC第j巡视路线的长度jh第j巡视所用的时间3.问题分析此题研究的是某县灾情巡视路线的设计问题。问题要求设计出最佳的巡视路线，即：保证总路程最短或时间最小而且各组尽可能均衡的巡视路线。基于图论相关理论，借助于几何直观和生活体验的启发作用，便于为计算机搜索制定行之有效的操作规则，接着利用图论软件包通过计算机求解出较精确的路线。再通过线路均衡性比较，对均衡性不4好的线路进行微调。以此方法确定最佳巡视路线。针对问题一：基于对问题的分析，借助图论知识，将所给公路网就转化为图论中的加权网络图，因此问题就转化为一个图论问题，即在给定的加权网络图中，寻找从给定点Ｏ出发，行遍所有顶点至少一次再回到Ｏ点，使得总权（路程或时间）最小。此即多个推销员的最佳推销员回路问题。基于以上分析，运用图论知识和图论软件包进行求解，再利用均衡度分析对得到的分组路线进行微调，均衡度越小表示路线越均衡，微调后即可得到相对较优的分组路线。可认为这样设计的分组方法和巡回路线能使总路线近似最短。针对问题二：在问题一的基础上添加了巡视组在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时等条件，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。首先，由图中数据初步计算后判断分成四组可行，再针对分组为四组的情况进行线路设计，仍将问题转化为图论问题，运用问题一的求解方法，得到分为四组的路线，在通过均衡度分析之后得出近似最优巡视路线。针对问题三：在问题二中关于T,t和V的假定下且巡视人员足够多时，要求在最短时间完成巡视的要求下所得的最佳的巡视路线，此时考虑到从Ｏ点巡视H点的最短时间是所有巡视线路中用时最长的，将计算出的最长路线巡视所用的时间作为巡视路线的最短时间限定，在此限定下对路线进行设计。基于问题一二中图论的方法，从一些点的路线比较少的点开始，能够使搜素容易进行，因此选择从距离Ｏ点一些较远的点（如12101522等点）开始搜索，每次搜索时都要对该点的巡视时间进行判断，直到找到近似最优路线。针对问题四：在巡视组数已定(如三组）的情况下，为尽快完成巡视就要求每组完成的巡视时间尽量均衡，因为总的完成巡视时间按线路最长的完成巡视时间计算，由于组数一定，T，t和V改变，对每组内的最佳巡视路线是没有影响的，但可能会影响到各组件的均衡性，因此问题实质是讨论T，t和V对分组的影响，即在不破坏原来分组均衡的条件下T，t和V允许的最大变化范围。需要用控制单一变量的方法，分别讨论T、t、V三个量中任意两个量不变时第三个量的变化范围。从而确定T，t和V的改变对最佳巡视路线的影响。4.数据分析4.1问题一数据分析基于对该县公路图的初步分析，可以统计出该县有乡（镇）17个，村35个。（线路图见附录一）应用lingo软件求解(具体程序见附录三)得出巡视点距离县政府所在地的最短距离，如表1所示：表1：Ｏ点到其余各点的最短距离PR1C2M26O10.112.9611.59.219.820.6282931AB355O22.220.822.116.311.91417.5N2520L67DO31.131.838.33927.234.522.248E9F1012O34.949.741.749.555.165.967.311GH1314J19O55.962.777.564.172.754.346.218I15161722KO52.961.169.960.353.54943.721232427Q3032O39.63944.328.42835.730.2333534O23.73627.8由此表格画出了最短路径生成图，如图1图16由上图便于在第一问分析得到分组情况。4.2问题二数据分析问题二中给出了巡视小组在乡（镇）村的停留时间和汽车行驶速度，分别为：巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。对于要在24小时内完成巡视，至少应分几组的问题，应首先求出最长路线巡视所用的时间，用停留总时间加上行走时间除以4的结果与24进行比较，以此判断最少分组能否为4组。计算如下：(17*2+35+599.8/35)/4=21.524(小时)（其中路线长度估算为599.8公里）因此最少分组可定为4组。5．问题一的解答本文研究的是灾情巡视路线的最优设计问题，由于路线图可看成网络图，因此此问题可转化为在给定的加权网络图中寻找线路使总权（路程或时间）最小的问题。然后针对具体问题，采用一些启发式算法，建立模型。5.1模型一的建立5.1.1模型一的准备经对问题的初步分析，基于图论的相关知识，将公路网图中每个乡（镇）、村看成图中的一个节点，各乡镇村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为图论中的加权网络图，问题就转化为一个图论问题，即在给定的加权网络图中寻找从定点Ｏ出发，行遍所有顶点至少一次再回到Ｏ点，使得总权（路程或时间）最小。定义１经过图Ｇ的每个顶点正好一次的圈，称为Ｇ的哈密尔顿圈，简称Ｈ圈。定义２在加权图(,)GVE中（１）权最小的哈密尔顿圈称为Ｈ圈：（２）经过每个顶点至少一次且权最小的闭通路称为最佳推销员回路。由定义（2）可知本问题是一个寻求最佳推销员回路的问题，最佳推销员回路的问题可以转化为最佳Ｈ圈的问题，方法是由给定的图Ｇ＝（Ｖ，Ｅ）构造一个以Ｖ为顶点集的完备图Ｇ’=（Ｖ，Ｅ’）Ｅ’中每条边（xy）权等于顶点x与y在图Ｇ中最短路径的权，即(,),(,)min(,)GxyEwxydxy。在图论中有以下定理：定理１加权图Ｇ的最佳推销员回路的权和Ｇ’的最佳Ｈ圈的权相同。定理2在加权完备图中求最佳Ｈ圈的问题是NP——完全问题。我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：算法一求加权图Ｇ＝（Ｖ，Ｅ）的最佳推销员回路的近似算法：⑴用图论软件包求出Ｇ中任意两个顶点间的最短路，构造出完备图Ｇ’（Ｖ，Ｅ’）(,),(,)min(,)GxyEwxydxy⑵输入图Ｇ’的一个初始Ｈ圈；⑶用对角线完全算法[2]产生一个初始Ｈ圈；⑷随机搜索出Ｇ’中若干个Ｈ圈，例如3000个；⑸对⑵⑶⑷步所得的每个Ｈ圈用二边逐次修正法[2]进行优化，得到近似最佳Ｈ圈；7⑹在第⑸步求出的所有Ｈ圈中，找出权最小的一个，此即要找的最佳Ｈ圈的近似解。（算法程序见附录）由于二边主次修正法的结果与初始圈有关故本算法第⑵⑶⑷步分别用三种方法，产生初始圈，以保证能得到较优的计算结果。在此问题是多个推销员的最佳推销员回路问题，即在加权图Ｇ中求顶点集Ｖ的划分Ｖ1，Ｖ２，…，Ｖｎ将G分成n个生成子图G[Ｖ１]，Ｇ［Ｖ２］，…，Ｇ[Vn]，使得：⒈顶点ＯＶｉ，ｉ＝1,2,3，…，n.⒉1()niUVVG.⒊,max()()max()ijijjwCwCwC，其中Ｃi为导Ｖi的导出子图G[Ｖ１]中的最佳Ｈ圈，w(Ci)为Ci的权，i，j=1，2，3，…，n.⒋1()minnjwC.定义3称,0max()()max()ijijiwCwCwC为该分组的实际路线均衡度，为最大允许均衡度，显然001，0越小说明分组的均衡性越好，取定一个后，0与满足条件3的分组，条件4表示总巡视路程最短。此问题包含两个方面：第一，对点分组；第二，在每组中寻求最佳推销员回路，即为单个推销员的最佳推销员问题，我们只能去寻求一种较合理的划分准则，对图进行初步划分后，求出各部分的最佳推销员回路的权，在进一步进行调整，使得各部分满足均衡性条件3.从Ｏ点出发去其它点，要使路程较小应尽量走Ｏ点到该点的最短路，故用图论软件包求出Ｏ点到其余顶点的最短路，这些最短路构成一棵以Ｏ为树根的树，将从Ｏ点出发的树枝称干枝，如图2：8图2从图中可以看出，从Ｏ点出发到其它点共有6条干枝，他们的名称分别为①，②，③，④，⑤，⑥。根据实际工作的经验及上述分析，在分组时应遵循以下准则：准则一尽量使同一干枝上及其分支上的点分在同一组；准则二应将相邻的干枝上的点分在同一组；准则三尽量将的干枝与短的干枝分在同一组。由上述分组原则，为我们找到两组分组形式如下：分组一：（⑥，①），（②，③），（⑤，④）分组二：（①，②），（③，④），（⑤，⑥）显然由图中可以直接看出分组一的方法极不均衡，故考虑分组二。对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线，使用算法一时在每个子图所构造的完备图中，取一个尽量包含图1中树上的边的Ｈ圈作为其第二步输入的初始圈。依次求解得到巡视路线的近似最优解。5.1.1综上所述，问题一的优化模型为：1()minnjwC