自行车交通系统服务网点布局规划王、王、李

2009 高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 海军航空工程学院参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 数模组 日期： 2010 年 8 月 18 日赛区评阅编号（由赛区组委会评阅前进行编号）：2009 高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：评阅人评分备注1免费自行车交通系统服务网点布局规划摘要:本文通过建立综合评价准则，对现有网点和自行车布局进行了排序与评价，并依据此准则对网点和自行车的分布进行了合理的优化。首先，综合分析影响网点和自行车布局的相关因素，概括起来分为人口流量、人口密度、人均自行车占有率以及网点相互距离四个因素。针对问题一，将这四个因素作为评价的指标，并对四个指标进行规范化处理，化为无量纲数，然后根据各指标的重要程度，赋给相应的权值，各指标加权后求和得到最终的综合评价指标，计算求得现有网点和自行车分布最佳的是 14 号网点。针对问题二，在问题一评价准则的基础上，我们采用逐步筛选的方法。首先对题中所给的区域进行了分块处理，将整块区域分成 240 块 的小方格区域，对2m30于每个方格内在任意位置设立自行车网点都是等效的，并且每一个方格内最多可以设立一个自行车网点。除去现有的 17 个网点数，这样问题就等效为余下的 223 个小方格区域中再筛选出 83 个方格作为自行车的新增网点。第一步筛选根据网点设置所需的客观条件，去掉不能设立自行车网点的方格，第二步对剩余方格区域作进一步筛选，建立了以总的评价准则为目标函数的非线性规划模型，求得新增 83 个网点的合理分布。对于问题三，由于需要考虑到网点建设成本和资金的限制，本文分析了约束条件的变化情况，对约束条件进行了修改，采用非线性规划模型进行求解。求解时，首先根据资金约束条件，计算出所有可能的网点数和自行车总数，并把这些量当作已知量来处理，网点数最大为 220 个。为了进一步简化问题，对求得网点数作出筛选，去掉过小和过大的，只考虑在 个范围内的情况，这样计算量能够有效减少。1503关键字：权重；综合评价；分块处理；非线性规划21 问题的提出随着经济的不断发展，城市居民人均拥有的汽车辆也越来越多，从而导致了交通、环境等问题，为了解决这种问题，市政部门通过建立公共自行车（免费单车）交通系统。这种便民利民实事工程以本着“随租随用，用后速还，信用保证，限时免费，连租连免，通租通还，损坏赔偿，便民安全”的原则，维护租用双方合法权益，确保城市市公共自行车（免费单车）交通系统的正常运营，方便市民及中外游客出行。某城区现有人口 15 万，地域面积约 22.9 平方公里 (长 4.68 公里，高 4.89公里) ，含两座小山和一个湖泊。已知该城区规划中的地铁站有 5 个，预计高峰时间人流量在 4000-5000 人/站，其余时间 10002000 人/站。大型社区有两个，社区 C有 1.4 万人，社区 C有 2.8 万人，其余地区，除山地、湖泊和河流区域外，可以认为人口是均衡分布的。大型超市有三个，预计高峰时间人流量在 3000 人/座，其余时间 1000 人/座。为了最大可能方便居民使用，应优先考虑交通枢纽和地点人流量，根据现实中调查可以推断：早晨在社区周边的网点车辆数较多，下午下班时在地铁站和超市附近网点的车辆数较多。十字路口的人流量一般较大。网点之间的距离一般控制在 300 米1000 米之间。目前该地区现有 17 个网点，600 辆免费自行车，统计车辆数如附表 1 所示。我们需要解决以下问题1. 设定一个评价标准来衡量现有网点与车辆分布状况。2. 在规划中要在图中增加到 100 个网点和 3600 辆车，如何决定网点位置跟每个网点的车辆数，才能使在你的评价指标下达到最优。3. 但目前市政资金有限，只能拿出 110 万元左右，已知建设一个网点需5000 元，投入一辆自行车的成本约 300 元，现希望尽可能实现主要居民区网点平均间距 500 米的公共交通体系，并最大程度服务居民，则需要在此地区建立多少个，如何分布网点并确定每个网点的车辆数。2 模型假设（1）研 究 区 域 封 闭 ， 即 假 设 不 会 有 其 他 区 域 的 自 行 车 流 入 ， 本 区 域 自 行车 也 不 会 流 出 ；（2）公 共 自 行 车 不 会 有 被 偷 、 损 坏 等 意 外 情 况 发 生 ；（4）每个使用自行车的人使用自行车的几率是一样的；（5）除了超市、交通枢纽人口集中的地区，其他地区的人口流量相同。3 符号说明为叙述方便，约定符号如下：第 个网点周围的人口密度；i3：第 个网点周围的人口流量；iq：第 个网点的人均自行车占有率；in：第 个网点的逼近度；is：第 个网点的第 项指标；ijx17,2i 4,321j：第 个网点的综合评价标准；if：第 项指标的权重；jw：第 个网点到其余网点距离的最小值；mind：第 个网点到第 个网点的距离，其中 ；kkki：第 个网点的自行车数量；iK：第 个网点周围的人口数量；iP：第 个方格区域分配的自行车数量；iy240,1i：0-1 整型变量。iz4 问题的分析自行车服务网点的确定主要依据其所产生的社会效益，即要尽可能的满足人们的使用需求，因此自行车网点的设置需要对影响自行车需求的因素进行分析，概括起来可分为四个方面，即人口流量、人口密度、自行车的人均占有率以及网点的相互距离。对现有网点和自行车布局进行评价，可以以这四个因素作为评价指标。对于问题一，通过对题目的分析我们知道解决这些问题的核心是要建立一个免费自行车交通系统服务网点的综合评价模型。目前国内外综合评价方法有数十种之多，包括模糊数学方法、系统工程方法、技术经济方法等等。这些评价方法各有其特点，但大体上可分为两类，其主要区别在确定权重的方法上。本题采用的方法是主观赋权，采取综合咨询评分确定权重，然后将数据规范化处理得到无量纲的数据再进行综合评价。对于本题，在评价之前必须要解决两个问题，一是量化评价标准，找出影响网点布局的主要因素然后进行量化等其他处理；二是权重的确定，根据调查结果对不同的评价标准给出相应的权重，这个过程主观成分比较大，但会在后面的结果中进行修正。对于问题二，需要把已有的网点增加到 100 个同时需要增加 3600 辆车，为了不盲目寻找多增加的 83 个点，通过转换思路，我们先在图上确定有限个可能成为网点的点，然后通过筛选得到需要的网点。通过将地图按照一定的规则划分，得到有限个可能建立网点的小区域，然后对该区域的评价标准进行综合评价从而最终找出需要的网点位置。4对于问题三，由于市政资金存在限制，对于自行车网点的选择就需要在满足位置适当的基础上还要考虑资金状况。因此，在问题二建立的模型的基础上，通过增加资金这一约束条件解决网点的选择问题。5 模型的建立与求解5.1 问题一的求解要评价现有网点与自行车车辆分布状况，由题目给出的已知条件知，需要从网点的选址状况和自行车数量分配的合理性两方面进行分析。网点的选址好坏取决于网点的方便程度，因此网点的布局主要依据网点周围人口分布情况，包括人口密度和人口流量。此外考虑到人们借车、还车方便以及效益的最大化，各网点之间的距离应保持在适当的范围。为了制定合理的评价准则，需要综合分析以上各因素，即人口密度、人口流量、网点相互距离以及网点的自行车数量。5.1.1 人口密度的分布题中所给的区域，人口分布不均，不仅地形比较复杂，存在高山、湖泊以及河流，人口密度受地形因素的影响较大，而且社区的类别对人口密度也产生影响。对于大型社区而言，人口相对集中，人口密度大。为了计算方便，不考虑人口在高山、湖泊以及河流区域的分布，其他地区除大型社区外人口分布是均匀的。大型社区 和 的人口密度1C22,1kSPck其中 分别表示该大型社区 和 的人口数量， 分别表示大21,cPC21,cS型社区 和 的面积。其他地区（除山地、湖泊和河流区域外）的人口密度。 210cZPS其中 为该区域内的总人口， 为该区域的总面积。ZP运用 软件图像处理命令对面积进行计算，求得所给区域的两个大型Matlb社区 和 ，面积分别为 和 ，面积合计为 ，1C22m762379826m104.两座高山和所有水域的总面积为 。该区域的总面积为 ，6108.9大型社区 和 人口数分别为 1.4 万和 2.8 万。则大型社区 和 的人口C密度 和 （单位为万人每平方公里）分别为1c2 45.60.71c29382其他地区（除山地、湖泊和河流区域外）的人口密度为 50.1.9450设 表示第 个网点附近的人口密度， 的值与网点所处的位置有关，当ii i5网点位于大型社区时，该网点处的人口密度即为该社区的人口密度，当网点位于除山地、湖泊的其余地区，人口密度为一定值。人口密度在该区域内总的分布情况为 处 在 其 他 地 区处 在 大 型 社 区处 在 大 型 社 区,5380. 2291,4.1Ci5.1.2 网点的相互距离网点之间的相互距离也是评价网点布局好坏的一个很重要的标准。出于最大限度服务人们的目的，建设网点时应依据有限时间内免费租赁，随处借还的原则。在题目的要求中，网点之间的相互距离大约为 ，这就能保证m103在较短的时间内免费使用自行车骑行到附近的另外的相邻网点，而网点之间的距离越小，居民就可以更加方便的选择目的网点，使得目的网点尽可能靠近目的地而避免了多走冤枉路的情况。根据以上分析，网点之间的最佳距离应控制在 之间，在该范围的前提下，网点相互距离越小对于人们来说越方m103便。定义任意两网点 和 之间的距离为 ，以 表示网点 到其ikkidmindi余网点距离的最小值， ikinm考虑到其他评价指标的影响效果是越大越好，为了与其他因素保持一致，我们定义最小距离的倒数 表征网点 与到他网点的逼近程度，作为评价的一isi个指标。 min1ids由于超出 的范围，网点的布局即认为不够合理，对于相互距离103存在小于 300 米和大于 1000 米的网点，通过给最小距离取一个较大值 ，使得D为一个较小的常值，计算时取 。通过 计算，可以得到网点is 10DMatlb之间的相互距离如下表 1。表 1 网点 到其余网点的逼近情况i网点 逼近量 s网点 逼近量 is1 0.001000 10 0.0019222 0.001000 11 0.0037863 0.001000 12 0.0014204 0.002777 13 0.0018935 0.002777 14 0.0013026 0.001329 15 0.0018937 0.001302 16 0.0010248 0.001922 17 0.0010009 0.0010005.1.3 人均自行车占有率服务网点自行车的配置数量应该根据自行车的需求量来确定，对于布置在地铁站、社区和超市这些人口比较集中区域的网点，自行车的数量应该多分配，6总之要尽可能满足网点周围人们对于自行车的需求。在不考虑网点容量与成本的前提下，网点的自行车数量越多越好。我们用人均自行车占有率来表征该网点自行车的分布情况，人均占有率越高,自行车数量越多，表明该网点的自行车数量能最大程度的满足人们需求。由于网点是向所有人开放的，自行车的人均占有率难以作出准确的计算。为此我们对问题进行了简化，假定网点存在一定的服务范围，对于该范围内的居民，网点将提供服务，不在此范围内的不做考虑。同时在服务范围的设置上，以 300 米为半径划定一个圆形区域，人均占有率的计算只涉及该区域内人口的分布状况。300m网点服务区域R图 1 网点的服务区域各网点服务范围的面积为 。2522 1086.304.S由于在该圆形区域内，可能存在社区和其他地区共存在的现象，而两者的人口密度是不一样的，需要加以区分计算。设 分别表示该圆形区域,kSi内大型社区 、大型社区 以及其余地区的面积， 分别对应于三1C 3,者的人口密度。则该网点所在服务范围内的人口数量为 31kikiP网点的自行车数量,在不同的时间段内值是不同的。对于大型社区附近的网点，自行车的数量上午和下午都维持在一个相对稳定的值，而其他各网点的数量都存在较大的波动。因此取上午和下午两个时间段自行车数量的均值作为各网点的自行车数量终值 ，即 iKpiaiiK21其中 、 分别表示网点 上午和下午的自行车数量。则对于网点 ，人均aiKpi ii自行车的占有率为 。iiPn5.1.4 人口流量的分布人口流量的分布集中在交通枢纽和超市等地点，并且呈现随时间变化的特点。一般而言，在上下班的高峰时间，地铁站、十字路口等交通枢纽的人流量会出现激增，而超市的人流量在节假日达到峰值。根据所给数据可知，地铁站和超市在高峰时间和其余时间内的人流量存在较大的差值。考虑到人流量的这种变化，分别对超市和地铁站高峰时间和其余时间的人流量加权，得到一个总的流量值。网点周围超市和地铁站的个数会对人流量产生影响，超市和地铁站数越多，网点附近的人口流量越大。仍取 300 米为半径的圆形区域作为网点的服务区域，计算时只考查该圆形区域内超市和地铁站的数目，当多个网点的区域发生重叠时，认为人流量平均分配，以均值作为各网点的人流量值。网点 附近的人口i7流量为 212kkmpicQq其中 、 分别表示网点附近超市和地铁站高峰时间和其余时间的kpQ2,1m人流量； 和 分别为高峰人流量的权值系数和其余时间人流量的权值系数，1两者满足 ，计算时取 ； 和 分别表示网点圆形区232,1k1c2域内超市和地铁站的数目。5.1.5 评价准则的建立该区域现有自行车服务网点有 17 个，这些网点即为评价的对象。评价指标有四个，即人口流量 、人口密度 、人均自行车占有率 以及网点 到到其iqiini他网点的逼近度 。记 表示第 个网点第 项指标，则四个指标构成的矩阵为isjxj。采用 评价中向量规范化方法对各指标进行规划化处理，求4NijxXTop得规范指标矩阵。可以建立以人口密度、人口流量、人均占有率以及逼近度四个因素为评价指标的多目标评价准则。设规范化指标矩阵 ，则4NijxX,12ijijij ,Ni 4,321j根据已知条件，四个指标中各指标对网点和车辆分布状况所起的作用大小难以确定，因此人为地对每个指标赋予一个权值，权值大小反映该指标对决策的影响程度。设评价指标的权重向量为 ，各指标加权后求和Tw),(4321得 ,7,41 jixwfjji 的值包含了人口密度、人口流量、网点逼近度以及人均占有率四方面的if成分，其大小能够作为衡量各网点的评价标准。对于 值较大的，该网点的布if局和自行车数量的分配相对合理，反之，网点和自行车的分布状况需要改进，可以考虑对相应的网点进行重新选址或对该网点的自行车数量加以调整。不管是网点的选址，还是自行车数量的配置，关键是能否为人们提供便利，满足人们对于自行车的需求。然而不同的人对于自行车的需求是不一样的，对于上下班、出行的这部分人来说，使用自行车的可能性大，即对自行车的需求量大。因此自行车的配置数量首先应该考虑流动人口的数量，即人口流量的大小，我们确定权重向量为 。Tw81,435.1.5 综合评价结论通过对各因素的分析，可以求得每个网点四个指标的值，进一步做规划化处理，得到规范指标矩阵 。如表 2 所示。417ijxX表 2 规范化后的各个网点的评价指标i人口密度 1人口流量 2x人均占有率 3x网点相互距离 4x1 0.468164 0.285714 0.169975 0.016582 0.468164 0.285714 0.145693 0.01653 0.124136 0.142857 0.366309 0.01654 0.124136 0.142857 0.274731 0.04585 0.124136 0.142857 0.274731 0.04586 0.124136 0.285714 0.274731 0.02197 0.42504 0.285714 0.133729 0.02158 0.124136 0.285714 0.274731 0.03179 0.124136 0.142857 0.274731 0.016510 0.124136 0.428571 0.274731 0.031711 0.124136 0.142857 0.274731 0.062412 0.124136 0.285714 0.274731 0.023413 0.124136 0.142857 0.183154 0.031214 0.42504 0.285714 0.133729 0.021515 0.124136 0.142857 0.183154 0.031216 0.124136 0.285714 0.183154 0.016917 0.124136 0.142857 0.274731 0.0165对规范化评价指标加权处理后，求得到各网点的最终评价结果如表 3 所示。表3 评价名次网点 综合评价值 排序 网点 综合评级值 排序1 0.0751 4 10 0.1120 22 0.0748 5 11 0.0502 113 0.0239 14 12 0.0706 84 0.0153 15 13 0.0057 175 0.0502 10 14 0.1221 16 0.0459 13 15 0.0486 127 0.0707 6 16 0.0692 98 0.0706 7 17 0.0800 39 0.0153 165.2 问题二的求解自行车服务网点的选址是一个复杂的问题，如何在为人们提供最大便利的基础上，合理的对网点加以布局，能够减少不必要的网点，有效节约成本。根据评价指标，网点的布局由四个因素决定，其中人口流量起主要作用，因此实际选址时，一般考虑将网点选在交通枢纽、超市等人口流量大的地区。但是考虑到尽可能使更多的人受益，应该适当增加网点数量，使网点的分布趋于均匀。网点的选址可以通过对某个地点自行车的需求量和所处地理情况进行调查，来确定合适的地点。在上述数据未知的条件下，难以准确的求得网点最佳布置点。在这个问题的处理上，我们将问题分为理想化和实际化，所谓理想化就是假设该区域内的任何地方均可建立自行车网点，而实际化则是考虑实际生活中，由于各类建筑以及高山、湖泊等的限制，使得该区域一部分地方不能建网点。因此可以根据这种方法，不断去掉不能建立自行车网点的区域，然后在满足条件的地点依据评价准则求得最优的网点布局位置。5.2.1 区域分块处理9将题中所给的区域反映到平面二维坐标系中，区域中的每一个点都对应一个坐标值。利用网格线将该区域划分为一个个 的小区域，使得整m30个区域被一个 的网格覆盖。该网格由 240 个小方格组成，在Km98.46.选择网点布局时，认为布置在每个小格子内所有网点都是等效的，同时考虑到网点之间的距离应该保持在 内，所以每个格子内只能设立一个自行103车服务点，但位置不受限制。为了计算方便，我们假设自行车网点都设在方格的中心位置。除去现有的 17 个网点，这样问题转化为在剩余 223 个小区域中再筛选 83 个最佳区域的问题。首先运用理想化和实际化的方法，对 240 个小区域进行第一步筛选，筛选方法应遵循以下几点：1.由于高山、湖泊地区不考虑人口的分布，自行车网点不可能设在这些区域，对于方格内存在高山和湖泊的，将这些小区域排除。2.考虑到自行车的使用应具备道路的条件，根据所给地图，将方格内没有标识道路的，去掉对应的区域。3.方格内已经设立网点的区域，不做重复考虑，也就是只需再找出 83 个小区域。根据上述方法对 223 个方格进行筛选后，还剩下 131 个方格 ，对这些点按顺序进行标号。5.2.2 非线性规划模型的建立在第一步筛选后，需要在剩余的网格中进一步选出 83 个方格作为自行车网点的设置点。通过对问题一的求解，已经建立了一个总的评价准则，我们以此做为目标函数建立一个线性规划模型对自行车网点布局进行求解。设第一步筛选后还剩下的方格数为 ，每个方格都有可能设立自行车网点，M以 表示每个方格分配的自行车数量，每个方格的面积 ，iy 22Km09.3bS第 个方格内自行车的人均占有率 为iniiPy其中 表示该方格区域内的人口密度。iP网点的逼近度 根据问题一中的定义，以该点到其他点的最短距离 的is mind倒数表示。 min1ids人口流量确定将方格区分为两类，一类为方格内存在超市和地铁站的，另一类则不存在。对于存在超市和地铁站的方格，为 类方格，该方格内的人口流量根据区域内超市和地铁站的流量确定。 方格内不存在超市和地铁站的为类方格,该区域内人口流量视为定值 ，则人口流量的分布情况为。 0Q类 方 格类 方 格021 kqimipi人口密度的分布不同地区存在差异，根据问题一的分析，各方格区域内的人口密度为10其 他 地 区处 在 大 型 社 区处 在 大 型 社 区,5380. 2291,4.1Ci问题一建立的综合评价函数为 41jijixwf其中 分别表示网点 的人口流量 、人口密度 、人均自行车占4,321jxi iiqi有率 以及网点的逼近度 四个指标规范化后的值， 表示第 个指标的权重。inis jj则对于第 个方格，综合评价函数为 MiiiiMiiiii snqf 12121212 848引入一个 01 变量 表示各方格内网点的设立情况，对于方格内设立自行z车网点的 取值 1，没有设立网点的 取值 0。iziz综合以上分析，得到该数学规划问题的目标函数 MiifcF1max根据题中所给的要求，可以分析得到该非线性规划问题满足以下约束条件。（1）筛选出的方格数目等于增加的自行车网点数量 83，即Miz183（2）各方格分配的自行车数量和与自行车总数相等，即 iiy160（3）对于选中的方格，任意两个之间的距离应小于 1000 米。设 表示第 方ikli格和第 个方格之间的距离。则需满足k10minjiikik xBlxl其中 为一个充分大的常数，计算时可取 。B建立如下非线性规划模型 Mi MiiMiiiMiiii syqzF1 12121212 8483ax 1110 ,21,010min368s.t1或i kiikkiMiizNy Mkxlxlz 5.2.3 模型的求解运用 软件可以求得 0-1 整型变量 和自行车分配数量 的值，Lingoiciy表示方格 被选择作为设立自行车网点。根据前文假设，自行网点设立1ici在方格的中心位置，考虑到实际情况下，方格的中心位置由于建筑物等因素的限制，不适合建立自行车网点，为此在已被选中方格区域中，对自行车网点位置进行适当的调整，让自行车网点尽可能靠近地铁站、十字路口这些交通枢纽分布。最终得到新增 83 个网点的分布情况见图 1 所示。图 1 100 个网点的分布情况由上图可知，新增 83 个网点后，该区域内网点分布比较均匀，基本上已经构成了一个覆盖全部地区的自行车服务网络，既充分考虑了交通枢纽、超市和社区人口集中地点自行车需求量大的实际，又兼顾了人口分布相对较少地区对自行车的使用需要，布局更加合理。表 4 新增 83 个网点自行车的分布情况如下表所示。网点 数量 网点 数量 网点 数量 网点 数量 网点 数量1 87 33 60 63 40 80 32 113 123 93 34 59 64 39 82 28 114 12125 86 35 58 65 39 85 24 118 819 67 36 56 66 36 86 24 119 819 6 37 56 67 36 87 24 120 821 66 43 52 68 36 88 24 121 822 65 45 49 69 36 90 20 122 823 65 50 46 70 36 103 16 123 824 64 51 46 71 32 104 16 124 825 63 52 46 72 32 105 16 125 826 63 56 43 73 32 106 16 129 427 61 57 43 74 32 107 16 130 428 61 58 42 75 32 108 16 131 429 61 59 43 76 32 109 12 132 430 61 60 43 77 32 110 12 134 531 61 61 42 78 32 111 1232 61 62 39 79 32 112 125.3 问题三的求解免费自行车交通系统服务网点的最终目的是服务人民大众，为了更好的实现这个目的，城市的管理者会考虑到增加网点的数目和每一个网点自行车的数量，这样会满足不同居民的不同需求。但是管理者同样会面对一个问题，那就是在增加网点数目和自行车数量的同时投资金额也会同时增加。在本题中，市政能提供的资金为 110 万元，建设一个网点需要的金额为 5000 元，投入一辆自行车的成本为