1、第卷第期年月数学的实践 与认 识,【灾情巡视的最佳路线丁颂康上海海运学院,上海摘要今年夏季,我国长江、松花江流域的广大地区遭受了特大水灾作为冬州 年全国大学生数学建模竞赛题的“灾愉丛视路线”问题就是在这样的背景下构思而成的本文中,我们将结合答卷评阅情况,简单介绍一些有关该题解答的要点一、关于问题的数学模型本题给出了某县的道路交通 网络图,要求的是在不同条件下,灾情巡视的最佳分组方案和路线这是一类图上的点的行遍性问题,也就是要用若干条闭链复盖图上所有的顶点,并使某些指标达到最优点的行遍性问题在图论和组合最优化中分别称为哈密尔顿间题和旅行商问题所谓哈密尔顿问题,就是研究图中是否存在经过所有顶点恰好
2、一次的圈或路,这种圈或路如果存在分别称为哈密尔顿圈和哈密尔顿路,简称为一圈和一路而旅行商问题通常是指在赋权图上经过所有顶点至少一次,且使总长度即边权之和 达到最小的闭链而本题所求的分组巡视的最佳路线,则与多旅行商问题厂,日类似,也就是,条经过同一点并复盖所有其它顶点又使边权之和达到最小的闭链求解非完全图的多旅行商问题,通常所用的方法可分为两步首先是利用任意两点问的最短路长度作为该两点间边的权构造一个完全图这一点对于原图中没有边相连的点对尤为重要,容易证明,在如此构造出来的完全 图中,各边 的权将 自然满足三角不等式,即任意三点间,两边权之和不小于第三边的权并且该完全图中的最优哈密尔顿圈与原图上
3、的最优旅行商路线等价第二步,以一点为起终点 本题中的县城的多旅行商问题,可以采用将该点视作若干点,。,、左为旅行商人数,并令,。,。对所有的点,笋。,及,之,双,二笋,该,一,们的方法,再将前述的完全图拓展成增广完全图然后,在该增广完全图上求最优哈密尔顿圈通常情况下,这个最优哈密尔顿圈将经过。,汽各一次,而这些点在圈上又不相邻因此,它们将把这个圈分解成恰好段这左段形成以粉作为起终点的闭链,分别对应左个旅行商的旅行路线并月这些旅行路线对于总长度最短的目标来说一定是最优的在拓展完全图上求解最优哈密尔顿圈,可以表达成下述线性规划更确切地讲是一规划的形式,艺艺,更,“,之了。艺,礼,城艺,、为、艺二、
4、七斌官、爪且万并。任,少任写“、了或 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/丁颂康灾情巡视的最佳路线其中、“就是点和间边的权是图的点集而条件兄八全是为了保证取之夕,的边不形成小的圈,这里万是点集任意的非空真子集式的最优解中八二的边钾,力 将构成最优哈密尔顿圈值得注意的是,用式求得增广完全图上的最优解,也就是多旅行商问题的最优解,能使人条旅行路线的总路程达到最小,但是这条路线的均衡性可能相当差因此,当要求均衡性较好的解还需要做大量的调整工作此外,哈密尔顿问砰和旅
5、行商问题都属尸一完全类,也就是说,式问题的求解没有多项式时间的算法对于本题的规模咆括县城共有”个点,再加上构造增广完全图时添加的左一个点,要想求得真正的最优解是不现实的为此只能采用启发式算法,求得近似最优解单旅行商问题的近似算法,有如分枝定界、最小插入、最小生成树、对换调优、最近邻点,以及神经网络、模拟退火、遗传算法等方法容易证明,单旅行商的最优路线长度,必定是多旅行商最优路线总长度的下界已知的一条原图的单旅行商最优路线的近似解为一尸一一一一一一一一一一一一一卜一一一一一一一一一一一一一卜一卜一一一一一一了一一一一一尸一一尸一一一一一一一一一一月一一其长度为公里在求本题的解之前,对原问题所给条
6、件作一些适当的假设还是必要的例如,公路不考虑等级差别,也不受灾情或交通情况的影响,各条公路段上汽车行驶速度可以认为是均匀的各巡视组巡视的乡镇、村不受行政区划的影响,即某乡镇 与隶属于它的村不一定要分在同一组内各巡视组保持统一行动,即不允许一个巡视组再分成若干小组等等二、关于问题的求解本题的第一问,要求设计分三组巡视时使总路程最短且各组尽可能均衡的巡视路线这里有两个目标若记三组的巡视路线长度从小到大分别为,则该两目标的数学表达式为,“,产从以及,山,、一,但是这两个 目标又是相互矛盾的,也就是不可能同时达到最小因此具体求解时,应两者兼顾,用多 目标的方法处理为简单起见,根据实际问题灾情巡视的背景
7、,一种较为合理的考虑是转换成一个目标函数,即一 一一根据前面分析,分组巡视路线的最优解,应当采用增广完全图上的单旅行商路线分段的方法求得但是根据原题图的规模以及边的稀疏性,用这种方法处理反而将使问题变得更为复杂而且考虑到均衡性要求需做的调整工作也将是大量的因此,可以采用先适当进行点的分组,分别求出各组的单旅行商路线,然后在组问进行适当调整的方法求得近似解对于巡视组的划分,我们可以利用原图的最小生成树 所选择的都是权最小边从县城出发的最短路生成树,或者原图的单旅行商路线等等子图作为依据,因为它们都是在某种指标下的最优解,而这类指标与原题的要求又相当接近当然,也可以直接利用地理位置,射线扫描,对边
8、界进行合理划分后向内扩展等直观方法作近似处理 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/数学的实践与认识卷分组以后,由于规模较小,最优巡视路线的设计就变得较为简单一般可借助现成软件求出精确解来既便没有这类软件,采用近似算法或者直接搜索也都能较容易地找出很好的近似最优解这里提供两种近似最优解的参考答案前者的总路程较短但均衡性较差后者的均衡性相当好但总里程稍长假如以己,的 目标来衡量,后者是已知的最好答案第一种方案第一组一召一厅一一一一一口一吕一口一一斤一一一一一总里
9、程为巧味,第二组一尸一一了一一刀一一一一一一一川一一一一一一一一一马一了一总里程川乃第三组一一一一月一吕一刀一一尸一一尸一傀一一一一“一一刀一一一一一总里程味,第二种方案第一组一一一一均一犯一一一一几一一一们一一一一一一一一一总里程一,。,、第二组一一一一刽一一一一一一一一一刀一一一一一召一总里程“月,第三组一一一一一一一一一一一一比一尸一一尸一一一一一一一总里程此,”综观参赛队的答卷,三组巡视总路程和各组路程的极差大体有以下关 系总路程约在拍一叨公里时,极差将达到公里总路程在。公里左右时,极差约为。公里而极差在公里以内时,总路程将略超过以川公里三、有时间约束的最佳路线本题的第二问是添加巡视组
10、停留时间二小时,小时以及汽车行驶速度二。公里小时的条件后、要求在小时内完成巡视的最少分组数以及相应的最佳巡视路线第三问则是在上述时间参数条件下,尽可能在最短时问内完成巡视所需的最少组数以及相应的巡视方案尽管两问形式雷同,但却蕴含着不同的数学内涵在前文中我们曾经提到,原图的单旅行商路线长度是分组巡视总路程的下界而已知的单旅行商路线长度均在洲。公里以上因此各组花在汽车行驶上的时间之和将超过小时巧二洲刊哟加上在各乡镇、村的停留时问,了十、二十均小时其中,为乡镇数,为村数,各组所需时间之和将大于韶小时若分成三组,就不可能在小时内完成巡视于是,所求的最小分组数为若记份为第组的巡视路线长度,勺。、了,分别
11、为该组停留的乡镇和村数,、,则各组所花费的时问伪为与,与,与亏、厂,和第一问的情况类似,所谓最佳的要求仍然是两目标的即要求,】,以及,”,“,1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/丁颂康灾情巡视的最佳路线假若我们仍然以后者作为主要目标来考虑,那么,乡村数的均衡性和各组路程的均衡性就依然是分组的主要依据,参照第一 问解答的方法和所得的结果,并对各组的交界作适当的调整,用计算机搜索的方法容易得到较好的解一个比较好的分组方案为第一组一一一一一吕一一一尸一一一一日一一
12、一一一总路程召吕公里,山弓,狗总巡视时间为,小时第二组一一一一乙一一一王一冈一一一,一一一一一一一挂,二、,住小时第三组一一一一组一州一刀一一一一肠一一招一一一,一刀一一,一已,天,月,小时第四组一一召一洲一肠一袅一阳一一”一搜一一洲一一一一尸一二、,、,“,、,。小时以上各组巡视路线中括一号的点为只经过不停留的点各组的巡视时间均在小时左右极差仅小时以川山川,为标准而言是已知的最好方案之一一般来说,较好的参赛了文章都能得到分四组,且四组巡视时间总和在盯一貂小时之间偏差又较小的方案问题的第三问是在上述时间参数假设下,如果有足够多的巡视人员,要求出完成巡视的最短时间,并给出在最短时间限制下的最佳巡
13、视路线事实上,完成巡视的最短时间受到单独巡视离县城最远的乡镇所需时间的制约采用图上求最短路经的、一。算法,可以求得从县城到各点的距离离县城最远的乡为点,距离为二。公里因此,单独巡视该乡所需时问为二最圣全十小时离县城最远的村为,若单独巡视所需时问要小得多即使人员足够多,分组再细,完成巡视至少需要。小时于是,问题便成为在拐小时内完成巡视所需的最少分组数和巡视方案容易验证,要在。训,小时内完成巡视,有些点如,只能单独作为一组,时间不允许在别的乡村停留而绝大部分乡村可以和其它乡村分在同一组内,并在限定时间内完成巡视我们把能够放在同一组 内巡视的乡村称为一个可行集这种可行集是原图点集的一个子集显然,原题
14、所求的最少分组数便是点集的可行集最小复盖问题同旅行商问题一样,子集复盖问题也属乍尸一完全类因此求该问题的最优解也是在短时间内做不到的采用计算机作近似搜索仍不失为较常用的办法关于该问题的研究,本刊同期发表的华东理工大学俞文鳅教授的文章有详细讨论他的文章还证明 了本题的最小复盖数为参照点在图中从县城出发的最短路树上的位置,采用就近归组的搜索方法,容易得到最优解月组的分组方法及相应的巡 视路线这里不一一列举了在阅卷中发现,有个别 的参赛队,找到了一种分成个组的方案,并且指 明尽管其中有两组的巡视时问超过 了最短时问的要求,但因为超出时问不长小于。小时,考虑 到问题的实际背景,用两个小组七分钟时间的代
15、价换取 了节省一个组的人力物力的效果我们认为,就数学建模竞赛的本意而言,这些同学的构思是可取的四、关于,的讨论本题第四问要求在巡视组数已定的情况下尽快完成巡视,讨论参数和的改变对最佳巡视路线的影响前面我们已经提到,要尽快完成巡视,即要求各组巡视时间的最大值也要最小用数学式子 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/数学的实践与认识表示就是卷,、,、,卜,丁,厂,又、,十斗、飞少冬,三人一这里左是给定的分组数,与,与分别是第组停留的乡镇数和村数,一份是第组巡视路线
16、的长度,在上述,的表达式中,由于和的作用完全相仿,所以为简化讨论起见,对于任意给定的和,不妨记尸即,这里权,可简记为与子,与十它是和告结论“若的线性函数,将随着和告的增大即的减小 而增大于是我们容易得到以下增大而丫不变为了使妈的最大值尽可能小,就要求脚。,狗的最大值尽可能小但是当和的关系确定后,兄,。、了,、是定值尹。十。,其中,。是全县的乡镇数,是全县的村数上述要求就成为各组停留乡村数加权以后之和尽可能均匀用数学式子表示即为,川,门,咬对卜十材咬左一“一左这里司和川分别表示数的下整数和上整数当然,在调整各组停留的乡村数使之达到均衡时,自然会给各组的路线及其长度带来影响这时应当考虑进行适当调整
17、“若不变而增大这种情况下,在,中可能导致今起主导作用那么,和“的结论类似,我们更应使伪即各组的巡视路线尽可能均衡诚然,因为兄今不是常数,而且今的均衡性会带来又的增大,这对于尽快完成巡视会带来负面影响所以对具体情况应作具体分析,比如可以考虑勺的前半部份尸,与十,与对均衡性的修正,对路程较长的组尽量考虑停留较少乡村至于,和的交互作用,对于这样一个原本很难得到最优解的离散最优化问题来说,将变得更为复杂这里就不再进一步讨论了一一卜 咬,八 连凡,之,。乙厂,之,刀,写,之八了,1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/