灾情巡视路线最优化的方案.docx

《灾情巡视路线最优化的方案.docx》由会员分享，可在线阅读，更多相关《灾情巡视路线最优化的方案.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、约束最优路线的模拟退火解法说明：以98年全国高校生数模竞赛中的B题（即“灾情巡察路线”）为例，介绍能解一类较广泛的约束最优路线问题的方法 一模拟退火法。该法对“灾情巡察路线”这类有约束以及“（一般）旅行推销员”、“中国邮递员”等无约束组合优化问 题均能求得较好的近似解，具有适用范围广和可拓展的优点。一、问题描述对于最短路、最大流、中国邮递员、旅行推销员等最优路线问题，常采纳各自不同的方法求解。假设在这些问题中再加 入一些约束条件，那么原方法往往不再有效，如98年高校生数模竞赛中的B题就是如此。我们设计的方法较好地解决了这一问 题。现以98年B题为例，介绍该法及其实现。下面为该题文字局部，并称其

2、四问分别为问题1至问题4：下列图（略）为某县的乡（镇）、村大路网示意图，大路边的数字为该路段的公里数。今年夏天该县患病水灾。为考察灾情、组织自救，县领导打算，带着有关部门负责人到全县各乡（镇）、村巡察。巡察 路线指从县政府所在地动身，走遍各乡（镇）、村，又回到县政府所在地的路线。1 .假设分三组（路）巡察，试设计总路程最短且各组尽可能均衡的巡察路线。2 .假定巡察人员在各乡（镇）停留时间2小时，在各村停留时间廿1小时，汽车行驶速度V=35公里/小时。要在24小时 内完成巡察，至少应分几组；给出这种分组下你认为最正确的巡察路线。3 .在上述关于T, t和V的假定下，假如巡察人员足够多，完成巡察的

3、最短时间是多少；给出在这种最短时间完成巡察的要 求下，你认为最正确的巡察路线。4 .假设巡察组数已定（如三组），要求尽快完成巡察，争论T, t和V转变对最正确巡察路线的影响。二、问题分析及模型的建立由于是分组巡察（不妨设分N组），要直接确定一个组巡察哪些地点是困难的。由于将各组巡察的路线连接起来可看成 一条N次相继从县城动身又回到县城的路线，这样，多组巡察就化成了单组巡察。经分析，我们认为前3问及第4问计算局部 都是组合规划中的约束优化问题，均属以模型min /（X）st.= 0 ,z = 1,2,.,mgf（x）0 ,j = 1,2,，九为基础的约束最优路线模型。下面依据各问的要求，分别对4

4、个问题进行详细争论。对于问题1,假如选取总路程最短的全部巡察路线中最均衡的，一般这一路线仍会很不均衡。故除了要总路程短，另 需“均衡”提出肯定的要求，即组间巡察路线的长度差不大于某给定值L。还有路线能够分成3次从县城0动身再回到0、各 组经过地点的并集为全部顶点的集合只之约束。模型如下：min b + % （/max - /min）st. n = N./max 一 ./min LUe = Ain其中F为巡察总路程，N为要求的分组数（本问N=3）, n是优化过程中路线的实际分组数，小和品扮别为n组中最长和最短组 的巡察路程，R为第i组巡察地点的集合，A是全部顶点的集合。约束条件（品x-fG4用来

5、保证各组路程基本均衡，目标函 数中加入X（f是为了使各组的路程尽可能均衡，这是一个约束多目标规划。权重九的取值应远小于目标函数中F的权系 数1,否那么会因离散问题函数值的跳动现象而导致优化困难。这里，我们取X=l/L。对问题2和3,因在原图中不是任意两顶点间均有边，故在多组巡察时可能存在二组以上经过的公共点，从而使顶点赋权遇 到如下困难：假设先赋点权，那么这些公共点的权会被重复计算；而假设在优化过程中赋点权，那么又有公共点毕竟应当由哪次（组） 巡察的问题。对此，我们采纳Dijkstra法算出任意两点间的最短路程并除以速度V转化为时间，并用其作为两顶点间边的权 构造一新图。第三个约束条件保证了每

6、点至少经过一次，而这时假设路线中含除县城外的重复地点将至少增加1个小时（除县 城为0外，其它点权为1或2小时），因而能保证优化结果中不消失县城以外的重复点。经分析，我们认为这两间同属分组数 和路线双重优化问题，详细模型如下：min F(III)(III)st. n = N/max K TMAXue = A1 W in其中N、n、A、P与模型（H）相同，F为各组巡察时间之和，心为n组中时间最长组的巡察时间，TMAX是巡察允许的最长 时间。对问题2, TMAX=24；对问题3,因人员足够多，故每个地点可由一组单独巡察，因此完成巡察的最短时间是这些单点 巡察的最正确路线中花时间最长的组对应的巡察时间

7、，其值TMAX由程序计算确定。对最少分组数的优化，模型中没有表达，我们是通过主程序与帮助掌握函数协同工作来实现该目的的，即在优化过程 中，假设路线调整觉察最短与次短组的时间之和不大于TMAX,且满意约束，那么纪录该路线后返回，并由主程序将分组数减1 后重新优化，假如重新优化找不到满意约束的可行路线，那么认为找到了最优解；而假设优化函数没有找到满意约束的可行路 线，主程序那么将分组数加1后进行下一轮优化。我们用m和M分别表示求解时尝试的最小和最大分组数,对问题2,取m=4, M=8, 而对问题3,8=20, M=35。对于问题4,其最正确路线是指在分组数N已确定的状况下，巡察时间最长的组所对应的

8、时间尽量短的路线。下面给出 其模型，各参数的含义同模型（III）,关于T、t和V对路线的影响，我们将在结果与分析局部给出。min Znaxst. n = N（【V）i0或rec_n=0且fx2fxi,转步(4)；(6)执行100次内部优化并更改路线，假设某次内部优化后fx2fx。，即比已有的最正确路线差，转步(4)；否那么检查是否与纪录的路线重复，假设重复那么转步(4)；(10)假设fx+fx2fx。，那么纪录器中原最正确路线后移，最正确路线数rec_n:=l,更新优化值fx。:=fx+f%,路线及相关数据记 入第一个位置，转步(4)；(11) rec_n:=rec_n+l,并计算纪录器中最终

9、一条最优路线的帮助掌握函数值fx4；(12)假设fx3fx”，与纪录器中各路线的帮助掌握函数值比拟并据此确定纪录器指针，当前路线插入相应位置，转步(4)；(13)假设纪录器没满，那么路线及相关参数记在已有最优路线之后；转步(4)；(14)假设tkVmaxtk,那么tk:=tk+L t:=FT*t；假设fxo比前一温度有改进，那么same_tn:=0,否那么same_tn:=sam_tn+l；转步(3)； (15)算法终止。此时假设rec_n0,那么找到了最优路线，可从纪录器中猎取最优和次优路线及相关数据。3 .编程提不对分组的处理及模型中的变量M、Pi、心、f而八F和下面用到的次短组巡察时间品

10、均由分组处理函数完成，因此它是解决 分组问题的关键，分组方法是：当自然分组数不大于N时，取自然分组；否那么将最短两组合并，直到组数等于N为止。与总 的设计思想相对应，程序设计应考虑多功能与通用性，以适应起点与终点相同和不同、单组和多组等各种要求。由于有提 升过程，故需一组变量存放当前最正确路线、最优值和路线终点位置等。纪录器参数组可满意人们想猎取多条最优路线的要 求。参数maxfx之值为“无穷大”，也是推断约束是否满意的依据，即满意约束时优化掌握函数值小于maxfx。三个用户函数 分别为目标函数、优化掌握函数和帮助掌握函数。优化掌握函数在未找到可行路线时为罚函数(值大于等于maxfx),否那么

11、 为0或多目标规划中减去实际目标函数值的剩余局部。帮助掌握函数实现两种掌握,一是优先纪录某种(不影响优化过程的) 特性的路线，如优先纪录均衡路线等；其二是有些问题仅要求实现一固定目标，如此题最少分组数的查找，只要两最短组 的时间之和不超过要求的时间，它们即应合并成一组，此时连续优化是多余的，应将分组数减1后重新优化。函数返回值大 于或小于等于-maxfx可区分上述两种状况。止匕外，定义了一称为优化值的变量，它是目标函数值与优化函数值之和。程序 在没有找到和已有可行路线时的处理不同，前者主要是查找可行路线，只关怀优化掌握函数值是否下降，而已有可行路线 时的关注点在优化值的转变。使用优化值而不是目

12、标函数值推断路线的优劣，是由于在很多多目标规中经常只要一个目标 的结果，且把其余局部放在优化掌握函数中可以仅计算路线转变局部的目标函数值，因而在处理多目标规划时可有更好的 性能。程序设有奇偶两种处理方式，其中偶方式为标准多目规划或只计算路线转变局部得不到目标函数值(如第4问)的情 形而设。设计奇偶方式而非固定参数，可以使程序具有对多个任务的处理力量。(三)求解对此题的求解，我们依据各问的要求和约束条件，设计相应的目标函数、优化掌握函数和帮助掌握函数，用Borland C+3.1 编程，在多台486、586及PH机上运行通过，解见结果与分析。对全部问题，编制同一组(三个)用户函数，依据处理方式

13、参数fxmode之值推断处理：对问题1, fxmode=l；对问题2和3, fxmode=3；对问题4, fxmode=2o目标函数是明显的， 现按单问题形式将其它两函数介绍如下：问题1优化掌握函数为：f = maxfx (ri+ r2)+ r3 maxfx+1000(fmin-L )；帮助掌握函数为：f =*fmin ,起优先纪录均衡路线的作用。其中n是路线中缺少地点的数目，掌握必需巡察每个地点；R=N-n为要求与实际分组的差值，掌握必需分成N个组，在下 面的各问题中n、R的意义和作用完全相同；而/max A1m 那么用于实现均衡的基本要求。0,其它问题2和3优化掌握函数为：f = 3 ma

14、xfx (ri+ r2) + r3 maxfx+1000 ( ftlx-TMAX)；帮助掌握函数为：f = (l-n) ( f*- fmin) - r4 maxfx；这里，/掌握每组巡察时间不超过要求；JL /nin + FminlMX主要用于优化最少分 0,其它410,其它组数。帮助掌握函数在本模型中具双重功能，一是在优化过程中遇到巡察时间最短的两个组的时间之和不超过要求的时间 时返回-maxfx,使优化函数纪录该路线并返回，实现优化分组数的目的；其次是优先纪录均衡路线。问题4 .优化掌握函数为：f = 3 maxfx ( rl + r2)；帮助掌握函数为：/=F ,使最正确路线中总时间短的

15、路线优先纪录(F为总路程)。四、结果与分析为使纪录的路线不重复，且结果输出时能按原图输出等，我们编制了原图与新图路程数据切换、路线是否相同的检查、 相邻两点用其间的最短路线替换，以及将编号转化为原地点名等多个帮助函数。为防止内存溢出，路程数据只存储矩阵的 上三角局部。为使解尽量好，还采纳了多轮算法，即先以任给初始路线进行假设干次优化，再把结果中最好的路线作为初始 路线进一步优化，假如找到了更好的路线，那么再以该路线为初始路线进行优化，直到没有改进时为止。全部计算的纪录器 均设为10组，一般都有多条最正确路线。(-)运行结果问题1为实现均衡要求，我们令L=70,即与完全均衡时相比，路程差不超过1

16、小时的路程。运行结果为：总路程568. 7公里, 平均每组巡察189. 57公里，组间最大路程差值58. 00公里，与平均值的最大差值为3L 67公里。选1条如下：第1组(157. 9公里)：；第2组(194. 9公里)：0f25.20fL19f18fI15fI.1617.22fK.212324fN26.P.()；第3组（215 9公里）：0.C3-D4.8fEf11fG.1314fII-129F10.Ff9.E.7.6520.问题2至少需要4组巡察，最短时间23小时，4组合计时间87. 066小时，组间最大时间差3. 45小时，歹打条如下:第1组（21. 5小时）：0.2.5.6.7. E.

17、9.F .10fFf9-Ef8.4D33.C.0；第2组（19. 6小时）：01.BfA.34.35.33313230fQ29Rf0；第3组（23. 0小时）：0”2-5.6.7.EfllfGf-14.13.Jf12025fN26f P.0；第4组（22. 9小时）：0.Pf28.2724.232217.16.11518fKf21f 25fM.0.其中用括号”片括起来的局部为经过而不巡察的路段，问题3亦是如此。问题3巡察最短时间TMAX=6. 429小时，至少需要22组巡察，22组合计时间130. 231小时，组间最大时间差值有两种。各选一 条且其次条只列出与第一条有差异的第8组和第12组：最

18、长时间为6. 429小时（第16组），最短时间是4. 777小时（第4组），最大组间时间差值为1. 651小时:第 1 组（6. 383 小时）：02-5-6.7fE.7-6.5f2-0；第 2 组（5. 583 小时）：025.67fEfHfG.11fE-7.6.5.2；第3组（6.309小时）:第3组（6.309小时）:0 M2521fKf17 16. 1 -15. If18fK2125fM - 0；第 4 组（4. 777 小时）：0P.26fNf26. P-0；第 5 组（5.717 小时）：0.P326fN.23.24.27 26fP-0；第 6 组（6.120 小时）：0fPf26

19、fNf23f2217- K-21f 25fM-0；第 7 组（5.391 小时）：0-M.52.0；第 8 组（5. 354 小时）：0.1fAf33f A-10；第 9 组（6.H1 小时）：0Rf29fQf 30f Q-28f P-0；第 10 组（5. 994 小时）：0f2f3fDf 4f D-3-0；第 H 组（6. 366 小时）：025-6fLf2025-M-0；第 12 组（4. 983 小时）：01fBfCf0；第 13 组（6.154 小时）：02-5.6L.19fJf13914913. J.19.L.6.5.290；第 14 组（6.317 小时）：0fP-29fRf0；

20、第 15 组（6.103 小时）：02-56fL-19fJf19fL-65f2-0；第 16 组（6. 429 小时）：0.2-5.67fEf9fF12fH.12fF9.E.7.6.5.2-0；第 17 组（6.317 小时）：0-口fA-3435332.31.R-0；第 18 组（6. 149 小时）：0.2-56.7.Ef9f Ff9f E7.6.5.2-0；第 19 组（5.491 小时）：0M.25.21fKf18fK.2125fM-0；第 20 组（6.023 小时）：25321fKf18. K.2125fM-0；第 21 组（5. 937 小时）：0.2-567fEf9F912f

21、GH9E765-2-0.第 22 组（6. 223 小时）： g256.7fEf9fF-10.F.9.Ef8f E7.65.20.最长时间为6. 429小时（第16组），最短时间是4. 354小时（第8组），最大组间时间差值为2. 074小时：第 8组（4. 354小时）：0-A-33f Af1f0；第 12组（5. 983小时）：OflfBfCfO.问题4受篇幅限制，仅给出结论：无论是T、t还是V,都有增加时巡察总路程增加，而削减时巡察总路程变短的趋势。运 行结果符合分析结论，且以县城为参照点，路线大体上分成左上、左下和右（含左上几个点）三局部。（二）结果分析由于我们手中没有其它程序和结果可

22、供比拟，故仅能以屡次运行的状况进行分析。对问题1,假设将其理解为“查找最短路线中的最均衡的路线”，那么计算结果为：总路程值533公里，第一组12公里，其次组23.8 公里，第三组497. 2公里。走法为：第 1 组：010；第2组：0-1-0；第3组:0-P-31-33334353230fQf28272642423221716115K21-25 20fLf19Jf11fGf1314fHf12fFf10fFf9fEf8f4-Df7-6fM 52 3fCf0.这明显与“尽量均衡”的要求相去甚远，与我们在“问题分析及模型的建立”中的预见相符。假如用多目标规划而不 加差值约束，当总路程与组间最大差值权

23、重比调整为1：0.4时，计算结果与模型（II）相同。但权重的选取没有一般标准, 很难精确把握，不如模型（II）简洁易行，故最终选用模型（II）。对其它问题我们认为处理得较好，屡次运算的结果几乎没有差异。五、评价与推广由于模型的建立是以一般约束优化模型为基础，依据详细问题确定目标函数和约束条件而形成的，因而具有一般性，能较 好地解决其它最正确路线寻求问题，如旅行推销、中国邮递员问题等，最大流问题亦可作为有约束的分组问题进行处理。此 外，只要在对分组的处理作少量修改，使各组可以有不同的起点和终点，即可解决多址选址问题中的局部类型问题，具有 可拓展性。此外，采纳模拟退火法，可使结果更接近全局最优解，

24、从屡次运行的状况看，各次运行的最优值与其中最好结 果的偏差一般不超过百分之一，这说明我们的算法是稳定的，通用性好，模型的有用性强。但程序的运行速度较慢，用至 少6轮的多轮算法在Pentium II 266机器上运行，问题1和2的计算时间在几分钟到近半小时不等，而问题3和问题4的计算一 般需要1个多小时，有时长达3小时左右，这是本方法的主要缺点。参考文献1 w. H.Press著傅祖芸赵梅娜丁岩等译.C语言数值算法程序大全（其次版）电子工业出版社北京1995年10月378-385 2钱颂迪等运筹学其次版清华高校出版社北京1990年1月264-2703数学编辑委员会（华罗庚苏步青等）中国大百科全书（数学）中国大百科全书出版社北京上海1988年11月8664 Edward Minieka著李家潼赵关旗译网络和图的最优化算法中国铁道出版社北京1984年267-271Leon Cooper and Mary W. Cooper著张有为译动态规划导论国防工业出版社北京1985年180-184