数学建模论文城市小区便民服务点的设置与调度优化模型

赛区评阅编号（由赛区组委会填写）：2015高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）及队外的任何人（包括指导教师）研究、讨论及赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号（从中选择一项填写）： 我们的报名参赛队号（12位数字全国统一编号）： 参赛学校（完整的学校全称，不含院系名）： 参赛队员（打印并签名）：1. 2. 3. 指导教师或指导教师组负责人（打印并签名）： 日期： 年_月日（此承诺书打印签名后作为纸质论文的封面，注意电子版论文中不得出现此页。以上内容请仔细核对，如填写错误，论文可能被取消评奖资格。）赛区评阅编号（由赛区组委会填写）：2015高教社杯全国大学生数学建模竞赛编号专用页送全国评阅统一编号（由赛区组委会填写）：全国评阅随机编号（由全国组委会填写）：（此编号专用页仅供赛区和全国评阅使用，参赛队打印后装订到纸质论文的第二页上。注意电子版论文中不得出现此页，即电子版论文的第一页为标题、摘要和关键词页。）城市小区便民服务点的设置及调度优化模型摘要随着经济不断增长，基础设施的需求不断增加，便民服务点作为城市基础化建设的重要组成部分仍需不断完善。由于人力、物力和资金等资源是有限的，如何根据城市的小区实际分布情况及需求合理地设置小区便民服务点，分配各服务点的服务范围，充分利用有限资源为全市市民提供一个生活方便、优质的服务，是有关部门面临的一个实际问题。问题一：分配各便民服务点的服务范围（1）题目要求在全市12个便民服务点位置确定的情况下，按照尽量短时间内到达服务点和工作量均衡的原则为各便民服务点分配服务范围。对此问题本文用算法建立最短路径模型，利用进行求解，得到每个服务点到居民点的最短路径。（2）我们对于120个居民点在最短时间到达服务点的问题，以所用时间最小为目标，建立0-1整型规划模型，借助进行求解，得出各条路径所需最短时间，结合（1）最后得到全市现有每个便民服务点的服务范围如表1。问题二：对于确定需要增加服务点的具体个数和位置的问题由问题一的分配结果可知，在现有便民服务点的设置下：①还有几个居民点不能在平均时间内到达服务点，即到达服务点时间过长②我们根据便民服务点工作量的方差定义工作量不均衡度，结果显示：此时服务点的工作量不均衡度为6.5。为解决到达服务点时间过长和便民服务点工作量不均衡的问题。我们建立最优化模型，求解结果表明：在增加三个服务点的情况下，可以解决居民点到服务点时间过长的问题。在此基础上我们优化分配方案：在增加几个便民服务点的情况下，使服务点的工作量不均衡度降为多少。增加的三个服务点路口标号见表2。关键词：最短路径算法0-1整型规划模型最优化模型问题重述某市为了方便市民生活，打算在市内小区设置便民服务点，为市民就近提供医疗卫生、缴费等公共服务，但由于人力、物力和资金等资源是有限的，如何根据城市的小区实际分布情况及需求合理地设置小区便民服务点，分配各服务点的服务范围，充分利用有限资源为全市市民提供一个生活方便、优质的服务，是有关部门面临的一个实际问题。问题一：为了提高便民服务点的服务效率，同时考虑每个服务点工作量的均衡性，该市打算将居民点划片服务，每个服务点面向一些居民点服务；建立数学模型，为各便民服务点分配服务居民点的范围，使其在所服务居民点范围内的居民尽量在最短时间内到达服务点，同时又要使每个服务点的工作量尽可能的均衡。问题二：根据现有便民服务点的工作量不均衡和有些居民点到达服务点时间过长的实际情况，拟在该市内再增加1至3个服务点，请确定需要增加服务点的具体个数和位置。该市目前有120个居民点和12个便民服务点，居民点和便民服务点的网络分布情况见支持资料1，每个居民点位置、居民人口数和道路连接的数据信息见支持资料2；支持资料1：该市居民点和便民服务点的网络分布示意图。支持资料2：该市居民点位置、居民人口数和道路连接的相关数据表。、问题的分析问题一：问题要求在市内的12个便民服务点位置确定的情况下，按照尽量短时间内到达服务点和工作量均衡的原则为各便民服务点分配服务范围。本文引入赋权图中任意两顶点间的最短路理论中的算法和0-1整型规划模型进行求解。记i€1,2,,120;为市内所有居民点的节点集合，j€1,2,,12;为全市便民服务点的节点集合，c(i€1,2,,120;j€1,2,,12)为便民服务点j到达居ij••••••民点i的最短距离。••• •••引入0T变量x(i€1,2,,120;j€1,2,,12),当居民点i分配给便民服务ij点j管辖是为1,当居民点i不分配给便民服务点管辖是为0。即：••••••A第i个居民点由第j个服务点服务j[0,第i个居民点不由第j个服务点服务由题目可知当c相对较小时，居民点i可能分配给便民服务点j，也可ij能分配给其他可在较短时间内到达居民点的便民服务台，而不分配给/，故有x€1；当c相对较大时，居民点i不能在较短时间内到达服务点j,故ij ij此时路口i不能分配给便民服务点j管辖，故此时x=0。ij根据上述的分配原则及每个路口只由一个便民服务点进行管辖、每个便民服务点至少要管辖一个路口，可首先利用算法计算出12个服务点到120个居民点的最短路径，然后建立0-1规划模型，并借助进行区域划分。问题二：根据问题一（1）的分配方案可知此时每个便民服务点的工作量分别为：表1按问题一的分配方案12个便民服务点的工作量编号123456工作量21946916编号789101112工作量412912612此时便民服务点的工作量不均衡度为6.3图1居民点和便民服务点的网络布情况注：图中圆圈“o*”表示设置了服务点；距离单位：公里由问题一可知现有便民服务点的工作量极其不均衡且有些地方路径过长。针上述问题，题目要求再增加1—3个便民服务点来解决上述问题。本文建立优化模型，然后利用对模型进行增加的平台个数，可得到初步的分配方案，最后再引入工作量不均衡度，通过计算求解可确定增加便民服务点的数目及位置。三、 模型的假设假设每个便民服务点的职能和人力配备基本相同假设每个路口只由一个便民服务点进行管辖；假设每个便民服务点至少管辖一个路口；•假设居民都按最短路径到达各服务点；•工作量：每个便民服务点所管辖范围内的所有居民点人数之和•时间：居民到达服务点所需时间；四、符号说明dij第i个居民点到第j个便民服务点的最短距离ci第i个居民点人数j第j个便民服务点i第i个居民点W总总人数Q新增点候选集xij居民点i是否分配给便民点jqi工作量li距离pj目标值jfc均方差五、模型的建立及求解5.1问题一（1）：服务范围的确定——算法最短路径模型

5.1.1模型建立：算法：根据问题一（1）的分析确定函数为目标函数：€,£•约束条件：,12)x={第i个路口节点到第j个服务平台 （i€1,2, ,120;j€1,2,,12)ij0第i个路口节点不到第j个服务平台x€1, (i€1,2, ,12)ii,x€1,(i€1,2, ,120)•…ijj€1I二-120cxIva,(j€1,2, ,12)12 iiji€1因cx=q (j=1,2,12)…iijii€1max(xd)=L (j=1,2,,12)1„i„120ijij jI需-,c.x..I=p.,(j.€1,2,,12)12 ii ji€1jfcjfc€5.1.2模型求解1.最短路径矩阵A的建立本文选用算法确定市内任意两个路口之间的最短路径矩阵d。算法ij为：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点x到j。所以，我们假设d为节点i到节点j的ij最短路径的距离，对于每一个节点X，我们检查d€d<d是否成立，如ixxjij果成立，证明从i到X再到j的路径比i直接到j的路径短，我们便设置d，d€d，这样一来，当我们遍历完所有节点x，d中记录的便是i到jijixxj ij的最短路径的距离。通过上述算法，利用数学软件计算出各节点的最短路径，组成一个最短路径矩阵d 。120—120图2偏差值及目标最优解的坐标图0005323332503131值数函标目50010001500200025003000350040004500a的值由图可看出在1500附近，目标函数值变动最小，为此我们选择1500为偏差限目标值：3518.575.1.3最终分配方案的确定从最短路径矩阵中，我们可以清楚看到如下问题：（1）在仅满足分配标准时有些路口可以被多个路口管辖；（2）在仅满足分配标准时个别居民点离服务点距离过大；那么此时并不满足模型的要求必须对 进行处理，以得到满足要120-20求的最终分配方案。首先解决（1）中出现的问题，此过程我们利用数学软件进行处理，相应的程序见附录。步骤一：由集合覆盖矩阵A 将120个居民点分为A、B、C三类：120-20A类：已只由一个巡警服务台进行管辖；B类：可被多个巡警服务台进行管辖；C类；还不能被任何巡警服务台进行管辖；步骤二：将A类中的路口直接分配给对其进行管辖的唯一的巡警服务台。步骤三：将B类中的路口按最近原则分配给距离它最近的巡警服务台。然后解决（2）中的问题。将任何服务点都不能在规定时间内到达的居民点按就近原则进行分配。表2最后得到最终的分配方案如下：服务平台管辖范围服务人数（人）最长距离A11,19,64,65,70,71,72,73,74,7,76,77,80,811610056.54864A22,42,43,66,67,68,69,78,791480068.19103A33,18,20,40,44,53,54,6313300115.0042

A44,49,52,56,57,58,59,60,61,62,991560052.10555A55,22,30,47,4&50,51,55,1340052.50731A66,32,33,34,35,36,37,45,46,891630040.04293A77,15,2&29,31,106,1091440098.17466A8&13,21,23,24,25,26,27,82,1460050.93686A99,14,83,84,85,86,87,88,90,921540055.85048A1010,16,38,39,91,93,94,95,9&100,103,1470047.01612All11,96,97,101,102,104,10&113,115,117,1201330072.03523A1212,17,41,105,107,110,111,112,114,116,11&1191560074.349544图3居民点和便民服务点的最短路径网络用设计增加的平台个数5.2问题二：确定增加平台的个数及位置用设计增加的平台个数5.2.1模型的建立及求解优化模型建立：根据问题一确定函数为：=为120i€1j€1约束条件：1选择第个路口节点到第 个服务平台不选择第 个路口节点到第 个服务平台i€1,2,_,12j€1,2, ,120)X=1 (i=1,2, ,12)ii••••••C€1,2,,12)(j，1,2, ,120)( ) (i，1,2, ,12j，1,2, ,120)ijij2当x三0时,至否则为jj••••••a<13533 得到的最优目标函数值要小于1353321133„120<(1,2,・・・，12)1，1根据平局工作量公式及工作量不均衡度公式，利用分别对分配方案中巡警服务台的工作量不均衡度进行计算。从49至64范围内取出若干个偏差限及所对应的目标函数值，得坐标图如下：图4偏差值及目标最优解的坐标图

由图可看出在1500附近，目标函数值变动最小，为此我们选择1500为偏差限最优目标函数值2618.287增加3个服务点，标号及坐标分别为20（244,134）109（19,56）116（248,76）最后，利用运用搜索法得到：至少从候选集Q中选出3个路口来设置便民服务点，才能解决到服务点时间过长的问题。此时共有1938种可能

的分配方案。表2满足题目二要求的3个便民服务点的路口标号表3方案一中15个服务点的管辖范围服务平台管辖范围服务人数（人）取长距离Al1,19,64,65,70,71,72,73,74,76,77,80,811310056.54864A22,42,43,66,67,68,69,751330060.79228A33,1&40,44,53,54,631310069.64803A44,49,52,56,57,5&59,60,61,62,99980052.10554A55,22,30,47,48,50,511350052.50731A66,32,33,34,35,36,37,45,461330040.04293A77,15,2&29,31,106,1091040084.98434A8&13,21,23,24,25,26,27,821160050.93683A99,14,85,86,87,88,90,921070034.13871A1010,16,3&39,94,93,91,95,9&100,1031310046.08345All11,96,97,101,102,104,10&113,115,117,1201040072.03523A1212,41,105,107,110,111,1121310032.949472018,20,75,76,77,7&79,80,81,1320036.779439922,48,99690052.8131610625,26,27,28,82,1061200027.26469五、模型的评价及推广优点：采用离散定位模型作为城区巡警服务台优化布局方法的应基础,结合相关的影响因素，能很好地解决实际问题。本文把实际问题抽象成集合模型、规划和图论，完整准确的描述了实际问题。本文所用算法，效率好精度高解决实际问题方便快捷。缺点：本文对工作量的定义只考虑路口发案率，没有不同区人密度对便民服务点工作量的影响。本文较少考虑不同区的路口发案率相差加大，导致服务点工作量难以均衡。模型推广：本模型不仅对便民服务点适用，而且可以广泛运于消防站、医院等应急服务设施的布局。六、参考文献谢金星，优化模型及软件，北京：清华大学出版社，2006年。王沫然，及科学，北京：电子工业出版社，2008年。方世昌，离散数学，西安：西安电子科技大学出版社，2009年吴美文，基于离散定位模型的城市消防站优化布局方法*，系统仿真技术，2006年1月第2卷第一期：58-62页。陈驰任爱珠，消防站布局优化的计算机方法[J],清华大学学报：自然科学版，2003,43(10)：1390~1393。陈艳艳郭国旗，城市消防站的优化布局[J].消防科技，1999,(1)：26〜28吴军，消防站优化布局方法及技术研究，消防科学及技术2006年1月第25卷第1期七、附录附录1(算法求最短路径及距离)建立带权邻接矩阵A：('C:\\\\1');(:,1);(:,2);(:,3);(