第三届BiZ-WiZ杯华中地区大学生数学建模邀请赛优秀论文.doc

第三届BiZ-WiZ杯华中地区大学生数学建模邀请赛免费自行车交通系统服务网点布局规划摘要本文针对某城区免费自行车交通系统服务网点布局规划的问题，在设定的标准体系下将问题分为两部分。第一部分以题设的17个网点为参照点，筛选出所有可能存在的网点坐标，第二部分根据交通枢纽和地点人流量的分布的状况，设计出最佳自行车网点布局方案。对于问题一，根据为城区居民最大限度提供方便的原则下设定了以下四个标准：1, 用尽可能少的网点覆盖尽可能大的面积。2，在网点数一定下，网点自行车总使用次数越大越好。3，各网点使用自行车的使用频率相差越小越好。4，对于一个网点来说，各个时段车辆数相差越小越好。 对于问题二，在上述设定的标准下，首先以给出的地图建立坐标系，以十七个已给出的网点为参照点，根据距离约束条件（网点之间的距离一般控制在300米1000米之间）和最大流量，采用基于集覆盖选址模型(LSCP)的动态规划法确定100个网点，然后通过最大流算法求出每个网点最优自行车数量。对于问题三，采用最小费用最大流算法和集覆盖选址模型(LSCP)求出在资金条件约束下最优的网点和车辆布局方式。 选取网点时，采用基于集覆盖选址模型(LSCP)的动态规划法用c+编程以及lingo对所有点根据费用最小的原则进行线性筛选，最后确定网点的地点。对各个网点该如何分配自行车数目时，根据交通规划的流通量原则，采用c+程序实现的最小费用最大流算法先求出每条线路上交通量，最后确定自行车的数目。关键字：集覆盖选址模型(LSCP)，动态规划，最大流，最小费用最大流，线性筛选1. 问题重述某城区推行免费公共自行车服务，已知地区基本信息如下（如图所示）此城区现有人口15 万，地域面积约22.9平方公里(如图长4.68公里，高4.89公里)，含两座小山和一个湖泊（如图）。已知规划中的地铁站有5个，图上AE点，预计高峰时间人流量在4000-5000人/站，其余时间10002000人/站。大型社区有两个，社区C有1.4万人，社区C有2.8万人，其余地区，除山地、湖泊和河流区域外，可以认为人口是均衡分布的。大型超市有三个，预计高峰时间人流量在3000人/座，其余时间1000人/座。现建设网点依据有限时间内免费租赁，随处借还的原则，最大可能方便居民使用，应优先考虑交通枢纽和地点人流量，根据现实中调查可以推断：早晨在社区周边的网点车辆数较多，下午下班时在地铁站和超市附近网点的车辆数较多。十字路口的人流量一般较大。网点之间的距离一般控制在300米1000米之间。目前该地区现有17个网点，600辆免费自行车，统计车辆数如下表所示编号上午7:00车辆数下午5:30车辆数17070260903403043010530106301075045830109307010301011302012308013201014506015201016205173060请你解决以下问题1. 设定一个评价标准来衡量现有网点与车辆分布状况。2. 在规划中要在图中增加到100个网点和3600辆车，如何决定网点位置跟每个网点的车辆数，才能使在你的评价指标下达到最优。3. 但目前市政资金有限，只能拿出110万元左右，已知建设一个网点需5000元，投入一辆自行车的成本约300元，现希望尽可能实现主要居民区网点平均间距500米的公共交通体系，并最大程度服务居民，则需要在此地区建立多少个，如何分布网点并确定每个网点的车辆数。2. 问题分析 评价一个城区免费自行车交通系统服务网点和车辆分布状况的标准，主要是考查在网点和自行车数目的限制下是否能最大可能方便居民使用；评价优劣标准可以为以下四点：1、在满足交通要求下网点越少越好；因为这样可以减小建设网点的费用。2、在网点数一定下，网点自行车总使用次数越大越好；网点数一定时，自行车的使用次数越多说明利用率越大。3、各网点使用自行车的使用频率相差越小越好；可以使得整体利用率更优化。4、对于一个网点来说，各个时段车辆数相差越小越好。保证每个点车数目一定利于管理。 该问题就是要求怎么在最少资金下使得以上四个条件尽可能的满足。可知此题要解决三个问题。怎样评价布点方式的优劣？每个网点应该放多少自行车？怎样在资金条件约束下尽可能的使得自行车的使用次数更多，从而达到最大限度方便居民的目标。3. 模型假设1， 建立的坐标为整数坐标系，即假设每个点的坐标都是整数点。2， 交通流量不同日子的变化不大。3， 自行车的磨损和更换费用不在考虑之列。4， 各线路都有法律规定的最大交通流量，具体数字为当地法规而定。5， 各网点线路假设为直线。4. 模型建立及结果3.1初步处理 根据问题分析，在城区地图建立坐标系。根据比例计算，可以测算出超市S1、S2、S3，地铁A、B、C、D、E，网点117的坐标，如下图所示：五个地铁站的坐标为（以左上角为原点）：A1681802B21142606C21243638D19334299E37242666三个超市的坐标（以左上角为原点）：S121043327S225061069S33281336817个免费自行车网点的坐标（以左上角为原点）：1634437921329325732828312742667419952526440963865125372697132383885202493764319710389525351138453427122245292613153044114259710221516518521675586217263732373.2网点的选取与筛选在以给出的地图建立坐标系，以十七个已给出的网点为参照点，根据距离约束条件（网点之间的距离一般控制在300米1000米之间）和最大流量，采用基于集覆盖选址模型(LSCP)的动态规划法确定100个网点，然后通过最大流算法求出每个网点最优自行车数量。1.距离约束条件与动态布点算法分析以已知的17个网点为参考点，用C+语言编写程序。先将题目已经给的17个点的坐标存储到集合D中，以第一个点也就是网点1开始，在x方向上向两边搜索，当某点(x,y)对于所有i满足(x-xi)2+(y-yi)=3002,其中i=1,2.17，且对某一j满足(x-xj)2+(y-yj)Nb则标0否则标1，用二进制状态压缩进k中，在这种情况下的最小花费FI,j,k:=minfl,u,k and (si(i-1)+w1,fr,j-u,k and(si(i-1)。 y:=fj/(aj*cj+bj);g:=cj*y*ai+y*bi;fi:=max(fi,g)即可求出在初步筛选点后最终确定的100个网点。4，集覆盖选址模型(LSCP)。 此模型是Toregas在1971年发表的。利用这个模型可以做到在覆盖所有点的情况下是车辆数目到最小。而且可以保证每二个点之间至少有一辆车通行。在此题中LSCP模型和动态规划算法相结合即可求出最优的网点分布。3.3网点的自行车分配的车辆数如图3.2如图3.2，每二个点之间的括号外面的数即为交通流量。括号里面的数即为最大流算法求出来的各路的最大交通流量。每个点的自行车数量即为括号里面的数字。对于此题只需将求出的满足条件的一百个点使用最大流算法即可得出每个点的自行车数量。如何确定二点之间有线路？对于此题来说就是二点距离如果满足约束条件即300到1000即认为有线路。此题中的最大交通流量根据当地交通部门的法律法规而来。 5.算法优劣分析动态规划优点是可以保存子问题的计算结果，从而减少时间复杂度。缺点是空间复杂度过高，尤其是对于现实中网点过多，从而导致算法计算难度加大。LSCP模型面临的是对于实际问题时只能近似得到最优解。最大流算法可以很好的解决每个网点自行车数目量数的问题，不过时间复杂度过高。对于点比较多的时候需要计算时间比较长。6.参考文献1万勇，李兵。线性代数。上海：复旦大学出版社，2006 2谭浩强。C+程序设计。北京：清华大学出版社，19983 Thomas H.Cormen, 潘金贵(译)算法导论. 北京：机械工业出版社，20064 Stanley B.Lippman。C+ primer。北京：人民邮电出版社，20025 Toregas。集覆盖选址模型(LSCP)。1971附录一：结果以17个现有网点为参考点初步筛选出满足条件的点634 4379 1329 32572828 31272667 41992526 44093865 12532697 1323 CI/ 点位于CI社区中3885 20243764 31973895 25353845 34272245 29261530 4412597 1022 CI1651 852755 8622637 3237634 0634 301634 1137634 1438634 1739634 2040634 2341634 2642634 2943634 3244634 3545634 3846634 4680773 4112 CII/ 点位于CII社区中781 563850 4889894 150894 1287894 1588894 1889894 2190894 2491894 2792894 3093894 3394 CII894 3695 CII894 45291015 10121033 3961 CII1033 4262 CII1041 4121041 7131110 47381154 01154 14371154 17381154 20391154 23401154 26411154 29421154 3544 CII1249 44711275 11621293 3810 CII1293 4111 CII1301 8631370 48881402 1691414 15871414 18881414 21891414 24901414 27911454 3530 CII1509 4320 CII1509 46211535 13121553 30571553 3960 CII1650 01670 48751674 17371674 20381674 23391674 26401678 3330 CII1702 3699 CII1769 4169 CII1769 44701772 11271778 2721793 5861795 14621813 29061918 3908 CII1926 3499 CII1930 47241934 18871934 21881934 24891938 31791949 251950 8772029 43192032 1277 CI2041 4172055 16122142 37082178 40582180 6832181 48892186 33482190 45732194 20372194 23382207 1032 CI2212 1702275 26272292 1427 CI2315 17622351 4362402 35572402 38582441 47382454 21872460 02473 7482519 28022535 24762562 15912575 19122599 2662662 37072699 5492701 48882745 22602760 12763 45932779 26512822 8232822 17412836 34622837 39512894 3212910 1110 CI2928 20222931 43422957 14732985 28702986 47942989 24353011 37063017 5953053 663082 32873101 40943115 8883119 17843153 45443170 1260 CI3172 21973193 3463195 26543239 30303256 35323271 48883275 38493288 15363310 6603323 42963346 03360 19633374 10403378 24163413 32753438 46383449 28143483 2673492 13163497 40513520 36753529 17153566 21823569 8123603 48893608 43903643 5213646 13738 28953742 38773772 15393773 46413795 2623811 41693834 9533908 6623942 48893946 03976 44203981 36953992 17434010 30224048 22764050 39874060 4034085 14574108 10764115 27394118 33024145 46684182 7854182 19764210 1434215 42384254 35704268 24804286 16804306 29714323 38624328 12804334 5264348 48894381 22014384 44864402 9894414 32514459 27124474 04476 19134488 41134527 2964529 15034542 36554554 7304572 24334587 47074603 30144617 11994657 43614675 2138509 690473 4100418 4889388 965374 150374 1287374 1588374 1889374 2190374 2491374 2792374 3093374 3394374 3695374 4529331 447224 4268213 3949210 722158 4738128 1115114 0114 1437114 1738114 2039114 2340114 2641114 2942114 3243114 354471 2978 4477附录二：程序代码1.距离约束条件算法源代码include using namespace std;struct resultint a;int b;result r300;int station=634,4379,1329,3257,2828,3127,2667,4199,2526,4409,3865,1253,2697,1323,3885,2024,3764,3197,3895,2535,3845,3427,2245,2926,1530,441,2597,1022,1651,852,755,862,2637,3237;int main()int bax, bay, bbx, bby;int min, max, mi, ma;int a, b, i, j, n, f;cinbaxbbxbaybby;cinminmax;mi = min*min;ma = max*max;n = 17;for(i=0, j=0; in; +i)ri.a = stationj+;ri.b = stationj+;bax = r0.a;for(a=bax; abbx; +a)for(b=bay; bbby; +b)for(i=0, f=0; in; +i)if(ri.a-a)*(ri.a-a)+(ri.b-b)*(ri.b-b)=mi)f = 0;break;if(ri.a-a)*(ri.a-a)+(ri.b-b)*(ri.b-b)=0; -a)for(b=bay; bbby; +b)for(i=0, f=0; in; +i)if(ri.a-a)*(ri.a-a)+(ri.b-b)*(ri.b-b)=mi)f = 0;break;if(ri.a-a)*(ri.a-a)+(ri.b-b)*(ri.b-b)=ma)f = 1;if(f)rn.a = a;rn.b = b;+n; for(i=0; in; +i)coutri.a ri.b;if(ri.a=2013&ri.b=922)cout CIendl;else if(ri.a=705&ri.b=3307)cout CIIendl;elsecoutendl;return 0;2.最大流量算法源代码/flow数组返回最大流每条路径上的流量/max_flow 返回最大流/s,t 代表起点和终点 随意选二个点作为起点和终点/对于这题我想二点间的最大通量就是该点自行车数#include #include #define maxLen 100int gmaxLenmaxLen, flowmaxLenmaxLen, n, s, t, premaxLen; int bfs() int quemaxLen, p, q, v, i; for (i = 0; i n; i+) prei = -1; que0 = s; pres = s; p = 0, q = 1; while (p q) v = quep+