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

1、赛区评阅编号（由赛区组委会填写）：2015高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公

2、正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号（从A/B/C/D中选择一项填写）： 我们的报名参赛队号（12位数字全国统一编号）： 参赛学校（完整的学校全称，不含院系名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日 （此承诺书打印签名后作为纸质论文的封面，注意电子版论文中不得出现此页。以上内容请仔细核对，如填写错误，论文可能被取消评奖资格。）赛区评

3、阅编号（由赛区组委会填写）：2015高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅记录（可供赛区评阅时使用）：评阅人备注送全国评阅统一编号（由赛区组委会填写）：全国评阅随机编号（由全国组委会填写）：（此编号专用页仅供赛区和全国评阅使用，参赛队打印后装订到纸质论文的第二页上。注意电子版论文中不得出现此页，即电子版论文的第一页为标题、摘要和关键词页。）城市小区便民服务点的设置与调度优化模型摘要随着经济不断增长，基础设施的需求不断增加，便民服务点作为城市基础化建设的重要组成部分仍需不断完善。由于人力、物力和资金等资源是有限的，如何根据城市的小区实际分布情况与需求合理地设置小区便民服务点，分

4、配各服务点的服务范围，充分利用有限资源为全市市民提供一个生活方便、优质的服务，是有关部门面临的一个实际问题。问题一：分配各便民服务点的服务范围（1）题目要求在全市12个便民服务点位置确定的情况下，按照尽量短时间内到达服务点和工作量均衡的原则为各便民服务点分配服务范围。对此问题本文用Floyd算法建立最短路径模型，利用MATLAB进行求解，得到每个服务点到居民点的最短路径。（2）我们对于120个居民点在最短时间到达服务点的问题，以所用时间最小为目标，建立0-1整型规划模型，借助LINGO进行求解，得出各条路径所需最短时间，结合（1）最后得到全市现有每个便民服务点的服务范围如表1。问题二：对于确定

5、需要增加服务点的具体个数和位置的问题由问题一的分配结果可知，在现有便民服务点的设置下：还有几个居民点不能在平均时间内到达服务点，即到达服务点时间过长我们根据便民服务点工作量的方差定义工作量不均衡度，结果显示：此时服务点的工作量不均衡度为6.5。为解决到达服务点时间过长和便民服务点工作量不均衡的问题。我们建立最优化模型，求解结果表明：在增加三个服务点的情况下，可以解决居民点到服务点时间过长的问题。在此基础上我们优化分配方案：在增加几个便民服务点的情况下，使服务点的工作量不均衡度降为多少。增加的三个服务点路口标号见表2。关键词：Floyd最短路径算法 0-1整型规划模型 最优化模型 MATLAB

6、LINGO一、 问题重述某市为了方便市民生活，打算在市内小区设置便民服务点，为市民就近提供医疗卫生、缴费等公共服务，但由于人力、物力和资金等资源是有限的，如何根据城市的小区实际分布情况与需求合理地设置小区便民服务点，分配各服务点的服务范围，充分利用有限资源为全市市民提供一个生活方便、优质的服务，是有关部门面临的一个实际问题。问题一：为了提高便民服务点的服务效率，同时考虑每个服务点工作量的均衡性，该市打算将居民点划片服务，每个服务点面向一些居民点服务；建立数学模型，为各便民服务点分配服务居民点的范围，使其在所服务居民点范围内的居民尽量在最短时间内到达服务点，同时又要使每个服务点的工作量尽可能的均

7、衡。问题二：根据现有便民服务点的工作量不均衡和有些居民点到达服务点时间过长的实际情况，拟在该市内再增加1至3个服务点，请确定需要增加服务点的具体个数和位置。该市目前有120个居民点和12个便民服务点，居民点和便民服务点的网络分布情况见支持资料1，每个居民点位置、居民人口数和道路连接的数据信息见支持资料2；支持资料1：该市居民点和便民服务点的网络分布示意图。支持资料2：该市居民点位置、居民人口数和道路连接的相关数据表。二、问题的分析问题一：问题要求在市内的12个便民服务点位置确定的情况下，按照尽量短时间内到达服务点和工作量均衡的原则为各便民服务点分配服务范围。本文引入赋权图中任意两顶点间的最短路

8、理论中的Floyd算法和0-1整型规划模型进行求解。记为市内所有居民点的节点集合，为全市便民服务点的节点集合，为便民服务点到达居民点的最短距离。引入0-1变量,当居民点分配给便民服务点管辖是为1，当居民点不分配给便民服务点管辖是为0。即：由题目可知当相对较小时，居民点可能分配给便民服务点，也可能分配给其他可在较短时间内到达居民点的便民服务台，而不分配给，故有;当相对较大时，居民点不能在较短时间内到达服务点，故此时路口不能分配给便民服务点管辖，故此时。根据上述的分配原则及每个路口只由一个便民服务点进行管辖、每个便民服务点至少要管辖一个路口，可首先利用Floyd算法计算出12个服务点到120个居民

9、点的最短路径，然后建立0-1规划模型，并借助lingo进行区域划分。问题二：根据问题一（1）的分配方案可知此时每个便民服务点的工作量分别为：表1 按问题一的分配方案12个便民服务点的工作量编号123456工作量21946916编号789101112工作量412912612此时便民服务点的工作量不均衡度为6.3图1 居民点和便民服务点的网络布情况注：图中圆圈“* ”表示设置了服务点；距离单位：公里由问题一可知现有便民服务点的工作量极其不均衡且有些地方路径过长。针上述问题，题目要求再增加13个便民服务点来解决上述问题。本文建立优化模型，然后利用lingo对模型进行增加的平台个数，可得到初步的分配方

10、案，最后再引入工作量不均衡度，通过计算求解可确定增加便民服务点的数目与位置。三、模型的假设 假设每个便民服务点的职能和人力配备基本相同； 假设每个路口只由一个便民服务点进行管辖； 假设每个便民服务点至少管辖一个路口； 假设居民都按最短路径到达各服务点； 工作量：每个便民服务点所管辖范围内的所有居民点人数之和； 时间：居民到达服务点所需时间；四、符号说明第个居民点到第个便民服务点的最短距离第个居民点人数第个便民服务点第个居民点总人数新增点候选集居民点是否分配给便民点工作量距离目标值均方差五、模型的建立与求解5.1问题一（1）：服务范围的确定Floyd算法最短路径模型模型建立：Floyd算法：根据

11、问题一（1）的分析确定函数为目标函数： 约束条件： 模型求解1.最短路径矩阵A的建立本文选用Floyd算法确定市内任意两个路口之间的最短路径矩阵。Floyd算法为：从任意节点到任意节点的最短路径不外乎2种可能，1是直接从到，2是从经过若干个节点到。所以，我们假设为节点到节点的最短路径的距离，对于每一个节点，我们检查是否成立，如果成立，证明从到再到的路径比直接到的路径短，我们便设置，这样一来，当我们遍历完所有节点，中记录的便是到的最短路径的距离。通过上述算法，利用数学软件MATLAB计算出各节点的最短路径，组成一个最短路径矩阵。图2 偏差值与目标最优解的坐标图由图可看出在1500附近，目标函数值

12、变动最小，为此我们选择1500为偏差限目标值：3518.575.1.3最终分配方案的确定从最短路径矩阵中，我们可以清楚看到如下问题：（1） 在仅满足分配标准时有些路口可以被多个路口管辖；（2）在仅满足分配标准时个别居民点离服务点距离过大；那么此时并不满足模型的要求必须对进行处理，以得到满足要求的最终分配方案。首先解决（1）中出现的问题，此过程我们利用数学软件MATLAB进行处理，相应的程序见附录。步骤一：由集合覆盖矩阵将120个居民点分为A、B、C三类：A类：已只由一个巡警服务台进行管辖；B类：可被多个巡警服务台进行管辖；C类；还不能被任何巡警服务台进行管辖；步骤二：将A类中的路口直接分配给对

13、其进行管辖的唯一的巡警服务台。步骤三：将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.0042A44,49,52,56,57,58,59,60,61,62,991560052.1055

14、5A55,22,30,47,48,50,51,55,1340052.50731A66,32,33,34,35,36,37,45,46,891630040.04293A77,15,28,29,31,106,1091440098.17466A88,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,98,100,103,1470047.01612A1111,96,97,101,102,104,108,113,115,117,1201330

15、072.03523A1212,17,41,105,107,110,111,112,114,116,118,1191560074.34954EMBED Equation.DSMT4 图3 居民点和便民服务点的最短路径网络5.2问题二：确定增加平台的个数与位置用lingo设计增加的平台个数模型的建立与求解优化模型建立：根据问题一确定函数为：约束条件： 当 时，否则为 得到的最优目标函数值要小于13533 (j=1,2,12)根据平局工作量公式与工作量不均衡度公式，利用lingo分别对分配方案中巡警服务台的工作量不均衡度进行计算。从49至64范围内取出若干个偏差限与所对应的目标函数值，得坐标图如下：

16、图4偏差值与目标最优解的坐标图由图可看出在1500附近，目标函数值变动最小，为此我们选择1500为偏差限最优目标函数值2618.287增加3个服务点，标号与坐标分别为：20 （244,134）109 （19,56）116 （248,76）最后，利用lingo运用搜索法得到：至少从候选集Q中选出3个路口来设置便民服务点，才能解决到服务点时间过长的问题。此时共有1938种可能的分配方案。表2满足题目二要求的3个便民服务点的路口标号X( 18, 20) 1.000000 X( 20, 20) 1.000000 X( 22, 99) 1.000000 X( 25, 106) 1.000000 X( 2

17、6, 106) 1.000000 X( 27, 106) 1.000000 X( 28, 106)1.000000 X( 48, 99) 1.000000 X( 75, 20) 1.000000 X( 76, 20)1.000000 X( 77, 20) 1.000000 X( 78, 20)1.000000 X( 79, 20)1.000000 X( 80, 20)1.000000 X( 81, 20)1.000000 X( 82, 106)1.000000 X( 99, 99) 1.000000 X( 106, 106)1.000000 X( 109, 106)1.000000 表3 方案

18、一中15个服务点的管辖范围服务平台管辖范围服务人数（人）最长距离A11,19,64,65,70,71,72,73,74,76,77,80,811310056.54864A22,42,43,66,67,68,69,751330060.79228A33,18,40,44,53,54,631310069.64803A44,49,52,56,57,58,59,60,61,62,99980052.10554A55,22,30,47,48,50,511350052.50731A66,32,33,34,35,36,37,45,461330040.04293A77,15,28,29,31,106,109104

19、0084.98434A88,13,21,23,24,25,26,27,821160050.93683A99,14,85,86,87,88,90,921070034.13871A1010,16,38,39,94,93,91,95,98,100,1031310046.08345A1111,96,97,101,102,104,108,113,115,117,1201040072.03523A1212,41,105,107,110,111,1121310032.949472018,20,75,76,77,78,79,80,81,1320036.779439922,48,99690052.8131610

20、625,26,27,28,82,1061200027.26469五、模型的评价与推广1.优点：采用离散定位模型作为城区巡警服务台优化布局方法的应基础,结合相关的影响因素，能很好地解决实际问题。本文把实际问题抽象成集合模型、规划和图论，完整准确的描述了实际问题。本文所用算法，效率好精度高解决实际问题方便快捷。2.缺点：本文对工作量的定义只考虑路口发案率，没有不同区人密度对便民服务点工作量的影响。本文较少考虑不同区的路口发案率相差加大，导致服务点工作量难以均衡。3.模型推广：本模型不仅对便民服务点适用，而且可以广泛运于消防站、医院等应急服务设施的布局。六、参考文献1 谢金星，优化模型与LINDO/

21、LINGO软件，北京：清华大学出版社，2006年。2 王沫然，MATLAB与科学，北京：电子工业出版社，2008年。3 方世昌，离散数学，西安：西安电子科技大学出版社，2009年4 吴美文，基于离散定位模型的城市消防站优化布局方法*，系统仿真技术，2006年1月第2卷第一期：58-62页。5陈驰任爱珠，消防站布局优化的计算机方法J，清华大学学报：自然科学版，2003,43（10）：13901393。6陈艳艳郭国旗，城市消防站的优化布局J.消防科技，1999，（1）：26287吴军，消防站优化布局方法与技术研究，消防科学与技术2006年1月第25卷第1 期七、附录附录1(floyd算法求最短路径

22、及距离)建立带权邻接矩阵A：p=xlsread('C:UsersadminDesktopbook1.xls');x=p(:,1);y=p(:,2);i=p(:,3);j=p(:,4);A=zeros(120,120);for k=1:120 a=i(k); b=j(k); A(a,b)=1; A(b,a)=1;endfor m=1:120 for n=1:120 if(A(m,n)=1) A(m,n)=sqrt(x(m)-x(n)2+(y(m)-y(n)2); else A(m,n)=50000; end endendfor m=1:120 for n=1:120 if(m=n

23、) A(m,n)=0; end endend xlswrite('C:UsersadminDesktopÁÚ½Ó¾ØÕó.xls', A);>> D,path=floyd(A);>> xlswrite('C:UsersadminDesktop×î¶Ì·¾ØÕó.xls', D);>> T=D(1:120,1:12);>> xlswrit

24、e('C:UsersadminDesktop·þÎñµãµÄ¾àÀë.xls', T);附录2（用lingo划分区域）：model:sets:department/1.120/;type/1.12/;a/1.120/:c;benefit(department,type):d,x;endsetsmin=sum(benefit(i,j):d(i,j)*x(i,j);for(benefit:bin(x);for(department(i): sum(type(j):x(i,j)=1);for(type(i):x(i,i)=1);for(type(j):(14800-sum(a(i):x(i,j)*c(i)<1450);for(type(j):(14800-sum(a(i):x(i,j)*c(i)>-1450);for(type(j):sum(a(i):x(i,j)*c(i)=q(j);for(type(j):max(department(i):x(i,j)*