关于桥梁选址问题的数学模型

1关于桥梁选址问题的数学模型摘要本文建立了理论模型，应用求最短路距离的 floyd 算法求出图中各小区之间的最短路径。随机数生成模拟生成泊松分布，用于求解在人数出行率不确定情况下，人流量对各条公路交通便捷所带来的影响。鉴于此问题是典型的非线性规划问题，我们利用求解非线性规划中搜索效率高的遗传算法求解。利用遗传算法进行随机模拟， 对建设费用最低的桥梁位置与便捷交通的桥梁选址问题及对应的公路设计方案给出了近似最优点，即桥址所选位置。公路拥挤度指在相同车流量下，不同干道的公路负荷度。即公路拥挤度越高，则负荷度越大，此公路越拥挤。我们对图中各条已建设好的公路加权，其权值代表该条公路的拥挤度，用权值差异区分图中主次干道的差别，权值数越大代表该公路拥挤度越高。定义小区便捷度指在全局范围内各小区间的最短路径的权值之和。图中的桥梁选址问题转化为求解各小区便捷度问题，求总建设费用最低的桥梁选址问题即求离河岸最近的小区到河的最短建设公路费用，以便捷交通为原则的最佳桥梁位置即求两岸最小便捷度点的连线与河流的交点。我们定义出入点为各小区到河岸所经过的最后一个小区。对于问题一的第一小题我们求得只需在v36，v37，v38 三点中任选一点作与河流垂直的公路，公路与河流的交点即为桥址位置。第二小题求得连接 v17、v40 两点，该连线与河流的交点即为建桥地址且在该两点间建立一条公路。对问题二的(1)只需求从南岸求得离河流最短公路即可，该公路与河的焦点即为所求桥址。 （2）两岸便捷度最小的点的连线与河流的交点即为建桥地址即 v17 与 v40 连线。问题三同时考虑费用最低和交通便捷求解得到应在 v15-v36，v17-v38 的两条连线上建立两座桥即可。问题四利用泊松分布随机模拟每个小区的出行率，求得仍应在 v15-v36，v17-v38 间连线在两个交点建立桥址。关键字交通便捷度 floyd 算法 遗传算法 随机生成数 拥挤度权数 泊松分布2问题的提出B 题：桥梁选址问题设下图中每一个圆点代表一个区，连接各圆点的直线代表公路，粗实线代表交通主干线，曲线代表一条河流。随着城市经济发展,为了便利河两岸的交通，决定在适当的位置造桥。假设河流北侧 A 到 D 段有沿岸公路，河的南侧当前还没有修建沿岸公路。试分别就以下问题讨论：问题一：河流为东西向的水平直线， 与 D 的直线距离为 1， 到河流的直线17v38v距离为 r，各区规模大致相同。总建设费用最低的桥梁位置和与之配套的公路设计方案；以便捷交通为原则的最佳桥梁位置和公路设计方案。问题二：河流为图中曲线，分别讨论总建设费用最小化和以便捷交通为原则的建设方案。问题三：如果计划建两座桥,地址又该如何选择？问题四：如果 的人口数为 ，又该怎样选择合理的桥梁位置？iv47,21,iw图中各点间距离设为： 到 区块、 到 区块、 到 区块各相邻两点15v835v3647v间距离为常数 ， 到 、 到 距离为 ， 到 距离为 。d5617d.95d18v920v12v324v526v728v930v31v23v1v23v45v 456789101v123v145v1617vDA 36v738v39v4041244345v4647v问题的分析公路主干道即指路面质量较平整宽度较大的道路，次干道指从路面宽度和平整度都次于主干道的公路。从主观上考虑，人们更愿意行走宽阔通畅的马路，首先对公路主干线和次干线做人工加权，体现主次干线交通便捷度的差别，从小区出发者根据道路权重的不同而选择所走路线。所选路线不同，其所走路径长度必存在差异。我们用求任意两点间最短路径的 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）问求解雷同，两岸便捷4度最小的点的连线与河流的交点即为建桥地址。问题三：在选造两座桥的前提下，我们假定两岸都选取两个不同的点作为出入点，即在 v13，v14，v15，v16，V17 中和v36，v37，v38，v39，v40，v44 中各取两点，再组合，连线与河流的两个交点为一组备选方案。因此根据排列组合原理可知共有 300 组备选方案（ ）.我们运用遗传算法，可以从 300 种方案中进行256*C寻优，找到近似最优方案。问题四：我们在这里考虑建两座桥的情况。方法跟问题三的雷同，只是引入了人口数 w 对便捷度的影响。问题的假设在问题一至三中假设各小区出行人数概率相等。在河流两岸各小区间行进仅按已建设好的横竖直线路径行进，而不再重新建设公路。假设小区间所走路经是沿图中已建设好的公路行进，不再另建公路。各条公路干道上的交通工具都是汽车，不采用步行或其它交通方式，即保证同条干道对不同个人便捷度的一致性。假设各主干道路况相等，次干道路况也相等，汽车在任何干道上行驶 速度一定（车速不受气候条件及其它因素的影响） 。图中各干道要么平行要么垂直，v45 在 v1，v6，v11 的连线的延长线上，由此确定图中各点的相对位置关系。无论河流是直线或曲线，各段河宽相等，且不考虑河宽的大小。单位长度建桥费和修公路费一定，不受任何外界影响。在问题二，三中也令各区规模大致相同。5数学模型原理原理一：每对顶点间的最短路径弗洛伊德（Floyd）算法解决此问题有两种方法：其一是分别以图中每个顶点为源点共调用 n 次Dijkstra 算法；其二是采用 Floyd 算法。两种算法的时间复杂度均为O(n3)，但后者形式上比较简单。Floyd 算法的基本思想：（1）利用二维数组 A1n-11n-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=0,从而推得distxT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。注：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）351i4736iA（L(X1,Y1)+L(X2,Y2)）X1,X2,Y3,Y4 可根据编码方法返回图中对应的点下标。适应度 :fi=(Max-Fi) / (Max-Fi)1MiFi 的值越小，fi 值越大。 为满足 Fi 的值越小，适应度越大的要求，要取一个适当大的值赋给 Max。选择操作：由“赌盘算法”原理，在 0，1 之间产生等概率随机数，对个体选择并配对，适应度大的个体被选择的概率大，适应度差的个体相对而言就更有可能被淘汰。交叉操作：对配对的个体做两两交叉操作。此题的交叉规则是：随机在个9体编码上选取相间的两位数字（如一，三位或二，四位）进行两个体间的互换。且要满足交叉概率 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 仍为最优点。 ）,连接该两点，该条直线与河流的交点处即为所选桥址。所建公路即为该两点间的直线段。10问题二（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,之间修建公路，桥址选择与公路建设规则与上题一致。11问题四：引入人口数 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：12模型评优1、利用 floyd 求出各点间的最短路径，该算法时间复杂性较小，为 2()On2、对离散空间的寻优有较好的性能，所以较广泛的应用于