桥梁选址问题的数学模型

关于桥梁选址问题的数学模型摘要本文建立了理论模型，应用求最短路距离的floyd 算法求出图中各小区之间的最短路径。随机数生成模拟生成泊松分布，用于求解在人数出行率不确定情况下，人流量对各条公路交通便捷所带来的影响。鉴于此问题是典型的非线性规划问题，我们利用求解非线性规划中搜索效率高的遗传算法求解。利用遗传算法进行随机模拟， 对建设费用最低的桥梁位置与便捷交通的桥梁选址问题及对应的公路设计方案给出了近似最优点，即桥址所选位置。公路拥挤度指在相同车流量下，不同干道的公路负荷度。即公路拥挤度越高，则负荷度越大，此公路越拥挤。我们对图中各条已建设好的公路加权，其权值代表该条公路的拥挤度，用权值差异区分图中主次干道的差别，权值数越大代表该公路拥挤度越高。定义小区便捷度指在全局范围内各小区间的最短路径的权值之和。图中的桥梁选址问题转化为求解各小区便捷度问题，求总建设费用最低的桥梁选址问题即求离河岸最近的小区到河的最短建设公路费用，以便捷交通为原则的最佳桥梁位置即求两岸最小便捷度点的连线与河流的交点。我们定义出入点为各小区到河岸所经过的最后一个小区。对于问题一的第一小题我们求得只需在v36，v37，v38三点中任选一点作与河流垂直的公路，公路与河流的交点即为桥址位置。第二小题求得连接v17、v40两点，该连线与河流的交点即为建桥地址且在该两点间建立一条公路。对问题二的(1)只需求从南岸求得离河流最短公路即可，该公路与河的焦点即为所求桥址。（2）两岸便捷度最小的点的连线与河流的交点即为建桥地址即v17与v40连线。问题三同时考虑费用最低和交通便捷求解得到应在v15-v36，v17-v38的两条连线上建立两座桥即可。问题四利用泊松分布随机模拟每个小区的出行率，求得仍应在v15-v36，v17-v38间连线在两个交点建立桥址。关键字交通便捷度 floyd算法 遗传算法 随机生成数 拥挤度权数 泊松分布问题的提出B题：桥梁选址问题设下图中每一个圆点代表一个区，连接各圆点的直线代表公路，粗实线代表交通主干线，曲线代表一条河流。随着城市经济发展,为了便利河两岸的交通，决定在适当的位置造桥。假设河流北侧A到D段有沿岸公路，河的南侧当前还没有修建沿岸公路。试分别就以下问题讨论：问题一：河流为东西向的水平直线，与D的直线距离为1，到河流的直线距离为r，各区规模大致相同。总建设费用最低的桥梁位置和与之配套的公路设计方案；以便捷交通为原则的最佳桥梁位置和公路设计方案。问题二：河流为图中曲线，分别讨论总建设费用最小化和以便捷交通为原则的建设方案。 问题三：如果计划建两座桥,地址又该如何选择？问题四：如果的人口数为，又该怎样选择合理的桥梁位置？图中各点间距离设为：到区块、到区块、到区块各相邻两点间距离为常数，到、到距离为，到距离为。 D A 问题的分析公路主干道即指路面质量较平整宽度较大的道路，次干道指从路面宽度和平整度都次于主干道的公路。从主观上考虑，人们更愿意行走宽阔通畅的马路，首先对公路主干线和次干线做人工加权，体现主次干线交通便捷度的差别，从小区出发者根据道路权重的不同而选择所走路线。所选路线不同，其所走路径长度必存在差异。我们用求任意两点间最短路径的floyd算法分别求出河流南岸或北岸任意两小区间的最短路径，假设小区间所走路经是沿图中已建设好的公路行进，不再另建公路。分析小区河流图发现小区分布较集中在河岸AD两侧，如桥梁选址在AD线段之外则各小区到桥梁的总长度之和很可能会增大，且在河岸北侧AD两点间已有一段沿岸公路，可节省公路造价费用，故假设桥梁选址在AD两点之间，且不妨假定小区v13，v14，v15，v16，v17和v36，v37，v38，v39，v40，v44作为南北岸小区群通往河岸的出入口。 求河流两岸各出入点的便捷度（某点的便捷度指同一侧各点到该点最短路径之和），即求得v13，v14，v15，v16，v17和v36，v37，v38，v39，v40，v44的便捷度。问题一（1）在这里我们假设只造一座桥。在求总费用最低的桥梁位置时，假设河流宽度相等，则无论桥梁选址如何，桥梁的建设费用都相等，此时问题转化为比较通往桥梁的公路的建设费用最低。要使公路建设费用最低只需求得小区到桥址的最短距离即可。因河流北侧AD段有沿岸公路，可节省建路费用，那么只要找到沿河南岸离河最近的小区即可，建造最短公路。因河为东西水平直线，则河南岸的v36,v37,v38三个小区与河岸距离最近且相等，故在该三个小区中任取一个，建设公路垂直连接河岸的交点即为桥梁所选地址，因此桥梁有三个等价的最优备选地址 。（2）在以交通便捷为原则时，分别选出南北两岸离河岸最近一侧公路上v13，v14，v15，v16，v17和v36，v37，v38，v39，v40，v44中便捷度最小的小区，以便捷交通为原则的最佳桥梁位置即选取南北两岸出入点中便捷度最小的各一个点，连接他们的直线与河流的交点即为便捷交通的桥梁位置。与之配对的公路设计方案即为在所选两小区间建立连接公路。问题二： 如河流为图中曲线，（1）由上面讨论之得建桥费用相等，则对总建设费用最低的方案在原理上等价于选择两岸城市小区到此条河流间最近的距离，因在北岸已有现成公路与河流相连又相邻，故问题又转化为(2)以便捷交通为原则建设即与问题一的第（2）问求解雷同，两岸便捷度最小的点的连线与河流的交点即为建桥地址。问题三：在选造两座桥的前提下，我们假定两岸都选取两个不同的点作为出入点，即在v13，v14，v15，v16，V17中和v36，v37，v38，v39，v40，v44中各取两点，再组合，连线与河流的两个交点为一组备选方案。因此根据排列组合原理可知共有300组备选方案（）.我们运用遗传算法，可以从300种方案中进行寻优，找到近似最优方案。 问题四：我们在这里考虑建两座桥的情况。方法跟问题三的雷同，只是引入了人口数w对便捷度的影响。问题的假设在问题一至三中假设各小区出行人数概率相等。在河流两岸各小区间行进仅按已建设好的横竖直线路径行进，而不再重新建设公路。假设小区间所走路经是沿图中已建设好的公路行进，不再另建公路。各条公路干道上的交通工具都是汽车，不采用步行或其它交通方式，即保证同条干道对不同个人便捷度的一致性。假设各主干道路况相等，次干道路况也相等，汽车在任何干道上行驶 速度一定（车速不受气候条件及其它因素的影响）。图中各干道要么平行要么垂直，v45在v1，v6，v11的连线的延长线上，由此确定图中各点的相对位置关系。无论河流是直线或曲线，各段河宽相等，且不考虑河宽的大小。单位长度建桥费和修公路费一定，不受任何外界影响。在问题二，三中也令各区规模大致相同。数学模型原理原理一：每对顶点间的最短路径弗洛伊德（Floyd）算法解决此问题有两种方法：其一是分别以图中每个顶点为源点共调用n次Dijkstra算法；其二是采用Floyd算法。两种算法的时间复杂度均为O(n3)，但后者形式上比较简单。Floyd算法的基本思想：（1）利用二维数组A1.n-11.n-1, Aij记录当前vi到vj的最短路径长度，数组A的初值等于图的代权邻接矩阵;（2）集合S记录当前允许的中间顶点，初值S=;（3）依次向S中加入v0 ,v1 vn-1，每加入一个顶点，对Aij进行一次修正：设S=v0 ,v1 vk-1，加入vk，则A(k)ij = min A(k-1)ij，A(k-1)ik+A(k-1)kj。A(k)ij的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。A(n-1)ij就是vi到vj的最短路径长度。Floyd算法的正确性和计算复杂性：1 贪心选择性质Floyd算法是应用贪心算法设计策略的一个典型例子。它所做出的贪心选择是从V-S中选择具有的最短特殊路径的顶点u，从而确定从源点u的最短路径长度distu。在这条路径上，分别记d(v,x),d(x,u)和d(v,u)为顶点v到顶点x，顶点x到顶点u，顶点v到顶点u的路长，那么distx=d(v,x)d(v,x)+d(x,u)=d(v,u)=0,从而推得distxdistu，此为矛盾。这也就证明了是从源点到顶点的最短路径长度。 2.时间复杂性 对于具有n个顶点的的无向图，用邻接矩阵表示这个图，总的执行时间为 O（n3）.原理二:（随机现象）对随机现象进行模拟，实质上利用计算机随机地产生一系列数值，它们的出现服从一定的概率分布，我们称这些数为随机数。利用均匀分布的随机数可产生具有任意分布的随机变量的样本，从而可以对随机变量的取值情况进行模拟。 原理三：（遗传算法）遗传算法程序设计原理和方法：遗传程序设计是在可能空间中寻找合适的计算机程序的自适应搜索算法，其搜索过程从本质上属于随机搜索算法，但其空间遍历性比传统的启发式搜索要好。遗传操作使得路径可随机跳跃至不同的子空间，从而在全局空间中以若干搜索集的并集方式从时序过程方面逼近全集。思想：在问题的搜索空间中随机产生一个适应于给定环境的初始群体， 构成群体的个体都根据题目要求折算一个适应值（具有实际意义）和适应度（一个0-1间的小数，值越大在该代群体中的性能越好），依达尔文适者生存原则， 用遗传算子处理各适应度的个体，使群体的平均适应值（具有实际意义）朝着优化的方向迭代，经过规定代数的迭代后，使群体中个体所代表的解趋近于问题的最优解，完成全局寻优的过程。符号假设d - 公路单位长度w1- 主干道权值w2- 次干道权值r - v17到v38之间的直线距离Wi- i点的人口数Bi-当日i点出行过河人数Si- i点作为出入点的便捷度S(i,j)- j点到i点的最短路径M -遗传运算的群体大小T- 遗传运算的终止进化代数Pc -遗传算法交叉概率Pm -遗传算法变异概率F（） - 遗传运算的个体适应值函数f -遗传运算的个体适应度u - 以交通便捷为原则的权数 t -当前进化代数P(t) -第t代的群体 L(i,j)- i,j的直线距离A -单位长度公路的修建费用模型的建立Flody算法求最短路： 式中p是已知点到的通路，为通路上所有边的权值。 便捷度函数f=min(S(i,j),S(i,k)+min(S(i,l),S(i,m)点j,k，和点l,m分别为河两岸的备选出入点，S(i,j)为点i到点j的最短路径权值，min(S(i,j),S(i,k)为对点i到备选点j,k的两个最短路径权值求最小值，所得最小值代表的最小路线为当出入点选取j,k时，i点过河的最优路线。该函数用来度量选取点j,k,l,m的整体便捷度的好坏。f值越大，该方案的便捷度好，反之，亦然。公路建设费用函数g= A（L(i,j)+L(l,k)）L(i,j)为点i,j的空间最短距离，即连接两点的直线段的长度。A为单位长度公路的修建成本。函数g表示在i,j和l,k之间修建公路需要的最低费用。目标函数F=u(min(S(i,j),S(i,k)+min(S(i,l),S(i,m) +（1-u）A（L(X1,Y1)+L(X2,Y2)）（u为权数）目标函数F为函数f,g的加权求和，对方案的交通便捷度和修路成本大小进行综合评估。F值越小，方案就被认为越合理。反之，亦然。 该题遗传算法寻优过程： 步骤一:初始化.设置进化的进化代数计数器t=0，设置终止进化代数T。随机生成M个个体作为初始群体P（0）。步骤二：个体评价。计算群体P（t）中各个个体的适应度。步骤三：选择运算。将选择算子作用于群体。步骤四：交叉运算。将交叉算子作用于群体。步骤五：变异运算。将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P（t+1）。步骤六：终止条件判断。若tT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。注：1.个体编码方法：设一个四位的十进制数，第一，三位的取值为0到4，（0，1，2，3，4表示v13，v14，v15,v16,v17）第二。四位的取值为0到5(0,1,2,3,4,5表示v36，v37，v38，v39，v40，v44)。以第一。二位为一个组合，三，四位为一个组合，并且一，三位的取值不同，二，四位的取值也不能相同。如：0011，表示分别在v13和v36，v14和v37之间建桥，桥址即在两点连线与河流曲线的交点上；0001，表示既在v13和v36，又在v13和v37之间建桥，不符合要求，舍弃。2.适应值函数（评估函数）：Fi= F（X1Y1X2Y2）=u(min(S(i, X 1),S(i,X2)+min(S(i,Y1),S(I,Y2)+（1-u）A（L(X1,Y1)+L(X2,Y2)）X1,X2,Y3,Y4可根据编码方法返回图中对应的点下标。适应度 :fi=(Max-Fi) /(Max-Fi)Fi的值越小，fi值越大。 为满足Fi的值越小，适应度越大的要求，要取一个适当大的值赋给Max。选择操作：由“赌盘算法”原理，在0，1之间产生等概率随机数，对个体选择并配对，适应度大的个体被选择的概率大，适应度差的个体相对而言就更有可能被淘汰。 交叉操作：对配对的个体做两两交叉操作。此题的交叉规则是：随机在个体编码上选取相间的两位数字（如一，三位或二，四位）进行两个体间的互换。且要满足交叉概率Pc的前提下。 变异操作：对单个个体进行编码变换。此题的变异规则：随机在个体编码上选取一位数字，在取值的范围内对该数字进行替换，要保证替换后的编码符合编码的组合规则（即相间位置上的数字不能相同）。且在满足变异概率Pm的前提下。 计算结果分析问题一（1）求总费用最低的桥梁位置时，最优公路设计方案为丛河南岸v36，v37，v38三点中任取一点作到河岸的垂线公路即可，桥址即为该点在河岸上射影。（2）在以交通便捷为原则时，先对主次干道进行权重赋值（w1=1,w2=2）,并设题中所给条件中的常数d=1,由floyd求最短路算法得到 S13=273.5,S14=260.5,S15=249.5,S16=242,S17=233.5S36=49.4721,S37=50.4721,S38=57.4721,S39=40.4721,S40=36.4721, S44=52.4721从两岸的点集合中选出便捷度最优的点，分别为点v17和点v40（由多次程序运算得，只要保证w1w2，则在两点集合中v17和v40仍为最优点。）,连接该两点，该条直线与河流的交点处即为所选桥址。所建公路即为该两点间的直线段。问题二（1）求总费用最低的桥梁位置时，以v36,v37,v38,v39,v40,v44为圆心做与河流曲线相切的圆，选取切圆半径最小的点为出入点，所建公路即为该出入点与该切圆对应得切点间的直线段。所选桥址即为该切点。（2） 此题与问题一的第二小题类同，同样取v17，v40两点，连接该两点即找到桥址和所需建设的公路路径，如图所示。问题三：设置运行参数Pc=0.6,Pm=0.05,M=20,T=100,u=0.5,d=2,r=10,A=100试算多次得出近似最优解的编码为4 2 2 0，即代表v15-v36,v17-v38,之间修建公路，桥址选择与公路建设规则与上题一致。问题四：引入人口数Wi （i=1,247）后,我们根据泊松分布原理利用计算机模拟当天各点出行过河的人数Bi（i=1,247）.令B1:B2:B34:B35=b1:b2:b34:b35B36:B37:B46:B47b36:b37:b46:b47用bi给点i到同点集的各出入点的最短路径加权。S(i,j)=S(i,j)*bi（用新得到的S(i,j)代入目标函数试算，求最优解。）当相关联的bi值互等时，问题四的解即为问题三的解，即问题三是问题四的特例。设置运行参数：Pc=0.6,Pm=0.05,M=20,T=100,u=0.5,d=2,r=10,A=100并用泊松分布求bi(i=1,246,47),试算多次得出当前近似最优解的编码仍为4 2 2 0，则所求解同问题三。下图中横坐标代表进化代数，纵坐标代表每代群体的平均适应值。问题3：问题4： 模型评优1、 利用floyd求出各点间的最短路径，该算法时间复杂性较小，为2、 对离散空间的寻优有较好的性能，所以较广泛的应用于组合优化问题。3、 搜索具有自适性全局优化性能，可以避免局部最优。模型推广1、本模型如适当的增加出入点的数量，则能更逼近最优解。2、如该模型结合启发性算法，能更好的解决连续空间的最优搜索并提高优化性能，加快优化搜索。4、 该模型可以推广到规模更大的非线性规划问题。参考书周明 孙树栋 遗传算法原理及应用 北京 国防工业出版社1999.6李庆阳 王能超 易大义 数值分析 北京 清华大学出版社 2001.8张晓莉 刘振鹏等 数据结构与算法 北京 机械工业出版社 2002.10教材组 运筹学 北京 清华大学出版社 1990.1王晓东 算法设计与分析 北京 清华大学出版社 200213 / 13文档可自由编辑打印