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

赛区评阅编号（由赛区组委会填写）：2015高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号（从A/B/C/D中选择一项填写）：我们的报名参赛队号（12位数字全国统一编号）：参赛学校（完整的学校全称，不含院系名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日（此承诺书打印签名后作为纸质论文的封面，注意电子版论文中不得出现此页。以上内容请仔细核对，如填写错误，论文可能被取消评奖资格。）赛区评阅编号（由赛区组委会填写）：2015高教社杯全国大学生数学建模竞赛编号专用页赛区评阅记录（可供赛区评阅时使用）：评阅人备注送全国评阅统一编号（由赛区组委会填写）：全国评阅随机编号（由全国组委会填写）：（此编号专用页仅供赛区和全国评阅使用，参赛队打印后装订到纸质论文的第二页上。注意电子版论文中不得出现此页，即电子版论文的第一页为标题、摘要和关键词页。）1城市小区便民服务点的设置与调度优化模型摘要随着经济不断增长，基础设施的需求不断增加，便民服务点作为城市基础化建设的重要组成部分仍需不断完善。由于人力、物力和资金等资源是有限的，如何根据城市的小区实际分布情况与需求合理地设置小区便民服务点，分配各服务点的服务范围，充分利用有限资源为全市市民提供一个生活方便、优质的服务，是有关部门面临的一个实际问题。问题一：分配各便民服务点的服务范围（1）题目要求在全市12个便民服务点位置确定的情况下，按照尽量短时间内到达服务点和工作量均衡的原则为各便民服务点分配服务范围。对此问题本文用Floyd算法建立最短路径模型，利用MATLAB进行求解，得到每个服务点到居民点的最短路径。（2）我们对于120个居民点在最短时间到达服务点的问题，以所用时间最小为目标，建立0-1整型规划模型，借助LINGO进行求解，得出各条路径所需最短时间，结合（1）最后得到全市现有每个便民服务点的服务范围如表1。问题二：对于确定需要增加服务点的具体个数和位置的问题由问题一的分配结果可知，在现有便民服务点的设置下：①还有几个居民点不能在平均时间内到达服务点，即到达服务点时间过长②我们根据便民服务点工作量的方差定义工作量不均衡度，结果显示：此时服务点的工作量不均衡度为6.5。为解决到达服务点时间过长和便民服务点工作量不均衡的问题。我们建立最优化模型，求解结果表明：在增加三个服务点的情况下，可以解决居民点到服务点时间过长的问题。在此基础上我们优化分配方案：在增加几个便民服务点的情况下，使服务点的工作量不均衡度降为多少。增加的三个服务点路口标号见表2。关键词：Floyd最短路径算法0-1整型规划模型最优化模型MATLABLINGO2一、问题重述某市为了方便市民生活，打算在市内小区设置便民服务点，为市民就近提供医疗卫生、缴费等公共服务，但由于人力、物力和资金等资源是有限的，如何根据城市的小区实际分布情况与需求合理地设置小区便民服务点，分配各服务点的服务范围，充分利用有限资源为全市市民提供一个生活方便、优质的服务，是有关部门面临的一个实际问题。问题一：为了提高便民服务点的服务效率，同时考虑每个服务点工作量的均衡性，该市打算将居民点划片服务，每个服务点面向一些居民点服务；建立数学模型，为各便民服务点分配服务居民点的范围，使其在所服务居民点范围内的居民尽量在最短时间内到达服务点，同时又要使每个服务点的工作量尽可能的均衡。问题二：根据现有便民服务点的工作量不均衡和有些居民点到达服务点时间过长的实际情况，拟在该市内再增加1至3个服务点，请确定需要增加服务点的具体个数和位置。该市目前有120个居民点和12个便民服务点，居民点和便民服务点的网络分布情况见支持资料1，每个居民点位置、居民人口数和道路连接的数据信息见支持资料2；支持资料1：该市居民点和便民服务点的网络分布示意图。支持资料2：该市居民点位置、居民人口数和道路连接的相关数据表。3二、问题的分析问题一：问题要求在市内的12个便民服务点位置确定的情况下，按照尽量短时间内到达服务点和工作量均衡的原则为各便民服务点分配服务范围。本文引入赋权图中任意两顶点间的最短路理论中的Floyd算法和0-1整型规划模型进行求解。记1,2,,120;i为市内所有居民点的节点集合，1,2,,12;j为全市便民服务点的节点集合，(1,2,,120;1,2,,12)ijcij为便民服务点j到达居民点i的最短距离。引入0-1变量(1,2,,120;1,2,,12)ijxij,当居民点i分配给便民服务点j管辖是为1，当居民点i不分配给便民服务点管辖是为0。即：1,0ijijxij第个居民点由第个服务点服务，第个居民点不由第个服务点服务由题目可知当ijc相对较小时，居民点i可能分配给便民服务点j，也可能分配给其他可在较短时间内到达居民点的便民服务台，而不分配给j，故有1ijx;当ijc相对较大时，居民点i不能在较短时间内到达服务点j，故此时路口i不能分配给便民服务点j管辖，故此时ijx。根据上述的分配原则及每个路口只由一个便民服务点进行管辖、每个便民服务点至少要管辖一个路口，可首先利用Floyd算法计算出12个服务点到120个居民点的最短路径，然后建立0-1规划模型，并借助lingo进行区域划分。问题二：根据问题一（1）的分配方案可知此时每个便民服务点的工作量分别为：4表1按问题一的分配方案12个便民服务点的工作量编号123456工作量21946916编号789101112工作量412912612此时便民服务点的工作量不均衡度为6.3图1居民点和便民服务点的网络布情况050100150200250020406080100120140123459962289710610913141516171819202182324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687889909192939495969798101001011021031041051110710812110111112113114115116117118119120注：图中圆圈“○*”表示设置了服务点；距离单位：公里由问题一可知现有便民服务点的工作量极其不均衡且有些地方路径过长。针上述问题，题目要求再增加1—3个便民服务点来解决上述问题。本文建立优化模型，然后利用lingo对模型进行增加的平台个数，可得到初步的分配方案，最后再引入工作量不均衡度，通过计算求解可确定增加便民服务点的数目与位置。5三、模型的假设●假设每个便民服务点的职能和人力配备基本相同；●假设每个路口只由一个便民服务点进行管辖；●假设每个便民服务点至少管辖一个路口；●假设居民都按最短路径到达各服务点；●工作量：每个便民服务点所管辖范围内的所有居民点人数之和；●时间：居民到达服务点所需时间；四、符号说明dij第i个居民点到第j个便民服务点的最短距离ic第i个居民点人数j第j个便民服务点i第i个居民点W总总人数Q新增点候选集ijx居民点i是否分配给便民点jiq工作量il距离jp目标值jfc均方差6五、模型的建立与求解5.1问题一（1）：服务范围的确定——Floyd算法最短路径模型5.1.1模型建立：Floyd算法：根据问题一（1）的分析确定函数为目标函数：1201211minijijijdx约束条件：10(1,2,,120;1,2,,12)ijijijxij第个路口节点到第个服务平台第个路口节点不到第个服务平台1,(1,2,,12)iiix1211,(1,2,,120)ijjxi1201|-|,(1,2,,12)12iijiwcxaj1201(1,2,12)iijiicxqj1120max()(1,2,,12)ijijjixdLj1201||,(1,2,,12)12iijjiwcxpj12120211[()]/1212iijjiwjfccx75.1.2模型求解1.最短路径矩阵A的建立本文选用Floyd算法确定市内任意两个路口之间的最短路径矩阵ijd。Floyd算法为：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点x到j。所以，我们假设ijd为节点i到节点j的最短路径的距离，对于每一个节点x，我们检查ixxjijddd是否成立，如果成立，证明从i到x再到j的路径比i直接到j的路径短，我们便设置ijixxjddd，这样一来，当我们遍历完所有节点x，ijd中记录的便是i到j的最短路径的距离。通过上述算法，利用数学软件MATLAB计算出各节点的最短路径，组成一个最短路径矩阵120120d。8图2偏差值与目标最优解的坐标图5001000150020002500300035004000450029503000305031003150320032503300a的值目标函数值由图可看出在1500附近，目标函数值变动最小，为此我们选择1500为偏差限目标值：3518.575.1.3最终分配方案的确定从最短路径矩阵中，我们可以清楚看到如下问题：（1）在仅满足分配标准时有些路口可以被多个路口管辖；（2）在仅满足分配标准时个别居民点离服务点距离过大；那么此时并不满足模型的要求必须对120-20A进行处理，以得到满足要求的最终分配方案。首先解决（1）中出现的问题，此过程我们利用数学软件MATLAB进行处理，相应的程序见附录。步骤一：9由集合覆盖矩阵120-20A将120个居民点分为A、B、C三类：A类：已只由一个巡警服务台进行管辖；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.0042A44,49,52,56,57,58,59,60,61,62,991560052.10555A55,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,9