选址问题

科院第九组黄江浩蔡翔周蓉浅谈选址问题摘要选址问题是人类一直在探讨的问题，图论的思想常常被使用着。我们使用Lingo软件，采用Dijkstra算法，满足了社区到煤气收费站的平均距离最小的要求，并成功得出M、Q、W三处作为煤气收费站的结论。在处理派出所选址问题时，继续使用Lingo软件，但却是应用Floyd算法。对程序的处理，是采取手动更改数据，即对拟建的派出所数目，是以人工的方式把数据进行逐次增加的，初始值为1。每次运行程序后，验证一次结果。最后确定在K、Q、W处设立派出所。其分别管辖社区见附录表一。关键词：探讨图论选址Dijkstra算法Floyd算法1.问题重述问题背景：一个好的选址，可以极大的方便人们的出行，对生产生活都有不小的帮助。在商业里，一个品牌广泛经营连锁店，正确的厂地选址会大大提高产量的输出效率；在工厂中，一个机械手的正确移动，会大大增加对零件加工的效率；在生活中，水、电、煤气收费站的准确选址，不仅方便公司对水费、电费、煤气费的收取，而且也方便了城市居民的生活。然而，错误的选址，或则无头绪的、无原则的胡乱选址不仅会使生产生活效率大大降低，也会大量浪费社会资源，不利于社会的可持续发展。所以，选址问题是很有必要研究的。一个好的选址设计，就是一项优秀的工程设计，应该符合人性的需要。2.题目要求：2.1问题（一）：为了方便某城市里的24个社区的居民缴纳煤气的使用费用，也为了煤气公司的自身考虑，避免因居民缴费的路途长远而不能及时的收回煤气费。煤气生产公司现在要拟建三个煤气缴费站，能使得居民与最近的煤气收费站之间的平局距离最小。2.2问题（二）：人民警察服务人民。为保障人民的生命财产安全，市公安局计划在该城区建立若干个派出所，同时局领导明确表示，若在某个分居所管辖范围内出现了突发事件，要求该局尽量能在3分钟内有警察能赶赴现场去处理事件。那么，既要安民，又需要合理的分配目前比较紧张的警力资源，市公安局应该如何进行选址，要设立多少个派出所才能达到局领导的要求呢？2.3问题（三）：为官之道在于养民。某市领导十分的关怀城市居民的生活，不定期的组织公务人员对该市的24个社区进行巡视，积极收集和听取人民对市政府工作的意见，从而做出政策和工作上的适当调整。而位于W社区的市政府，会由领导带队分三组出发巡视。然而巡视不是游玩，为了尽快完成巡视，而后能早日完成政策上的调整和工作上的更新，如何安排巡视路线，才能最快的走访完每一个社区？3.模型的假设3.1对模型的总体假设：假设1：该市在进行城市规划建设时，不改动已有24个社区间的道路。3.1.1对问题（一）的假设：假设1：煤气缴费站设立在社区内；假设2：居住在某社区的全体居民，都会独立地去该社区所属的煤气收费站进行缴费；假设3：忽略社区面积的大小，仅仅以社区之间的距离做为计算的数据。即不以居民从家到煤气收费站的距离作为数据标准。3.1.2对问题（二）的假设：假设1：每个派出所在其管辖范围内，不论何时，且不论出现了多少突发事件，该派出所自身都有充裕的警力去处理；假设2：一旦出现突发事件即开始计时，警车马上就出动，不考虑期间任何事件的准备时间。假设3：警车出动期间，在到达突发事件地点前，道路时刻通畅且不会因为任何意外情况的发生而导致中途停车；假设4：不考虑警车的启动和制动所需花费的时间，车速假定可突增至50km/h，也可突减至0km/h；假设5：警车从出发至事发地地点的整个过程中，速度一直保持不变，即保持题目所给定的条件——警车的时速为50km/h。三．符号说明i、j、n均表示24个社区编号ijD表示从社区i到社区j的最小距离iN表示i社区的人口minS表示社区所有人走的总路程jXP表示在社区j被选定为收费站jX表示某一社区“j”表示社区编号若jX与jXP相互关联，则jX返回值1；若jX与jXP不关联，则jX返回值0；C参数常量，其取值与jX有关；mP表示社区m为警局所在地四．模型的建立与求解4.1问题（一）4.1.1模型分析本问类似于货郎担问题，我们考虑用图论的思想来解决该题。但由于模型的自身受很多因素影响，所以难以确定一个最优解。我们采用Dijkstra解法，把每一种存在的情况都进行了计算并储存数据，然后进行数据比较，从中选择出我们所需要的比较接近最优解的解。我们使用Lingo软件。首先，从24个社区里面任意选择三个社区作为假定的煤气收费站jXP(124)j。其次，将每一个社区与三个选定的社区间的距离做一个比较，并记录其最小值minS待用。然后，直接在Lingo软件上反复比较，取出相对的最合适的解，即确定了收费站的选址。4.1.2模型的建立4.1.2.1确定目标函数依据题目要求我们，选择能使得居民与最近煤气收费站之间的平均距离最小这个条件，我们确定的目标函数就是要解决这个问题。挑选出让相应社区里所有人走的总路程最小的三个社区。对于这样一个总路程，我们定义为，该社区的人口总数乘上该社区到选定的煤气收费站所在社区的距离。再利用C的返回值为1或者0这个约束条件，通过判断C的值是否为1，来确定所设立的这条路径是否行得通。据此，我们建立如下函数：2424min11**ijiijSDNC4.1.2.2确定约束条件ⅰ.已知该城市有24个社区。故，对代表社区的字符i和j要进行一个上限约束：124124ijⅱ.以i代表某社区，iXP则表示在社区i被选定为收费站。实际要求我们只设立三个煤气收费站，所以iXP的个数只能为三个，即：3jXjRP124R4.1.2.3综上所述，得到问题（一）的最优化模型2424min11**ijiijSDNC124124..3(124)jXjRijstPR4.1.2.4模型的求解[1]分析模型，开始使用Lingo软件。使用Lingo软件编写程序，从所给24个社区中假定三个社区作为煤气收费站，记为jXP。⑵将每一个社区到已选定的三个煤气收费站所在社区的所有人走的总路程，做一个比较，并记录其值，留作比较数据时备用。⑶使用Lingo软件，一边计算一边统计结果。把要被赋值的jX与其有关的函数jXP联系比较，若jX与jXP相互关联，则jX返回值1；若jX与jXP不关联，则jX返回值0；⑷直接在使用Lingo软件所得到的数据中，找到我们所求得三个社区代表的编号。该值确定为M、Q、W。4.1.3问题（一）的结果分析收费站M、Q、W的所属情况，我们有一个统计，列表如下：收费站M（94）收费站Q（72）收费站W（122）H（8）D（6）A（10）J（11）Q（22）B（12）K（13）R（14）C（18）L（11）S（8）E（10）M（11）T（7）F（15）N（8）V（15）G（4）P（9）I（7）U（10）W（28）Y（13）X（18）注：括号内的数字表示人口总数。（单位：千人）从表中数据可以看出，到M和W处缴费的社区数量最多，均有九个，而前往Q处缴费的社区仅为六个；还可以看出，在W处缴费的人数位居三个收费站之首，高达122000人。我们建议在W处安排更多的对外工作窗口，用以提高煤气公司自身的工作效率和减少居民缴费时排队等候的不便情况的发生。4.2问题（二）4.2.1模型的讨论为了保障社区人民的生命财产安全，该市现在要建立若干派出所。出于对目前警力资源的考虑，我们希望，在能达到题目要求的前提下，建立的派出所越少越好。由于建立的派出所的数目未定，我们假定将拟建n所警局。已知，警车时速为50km/h，则三分钟内最快可以行使25个单位。所以，对突发事件地点到派出所之间的距离要有一个约束，即不得超过25个单位长度。本问解法大体上类似于第一问。我们继续使用Lingo软件进行编程。首先，从24个社区里面任意选择n个社区作为假定的派出所。其次，将每一个社区与n个选定的警局所在社区间的距离做一个比较，在程序中满足其间距不大于25个单位的路径定义为通路，并返回数值1。最终，在程序求得的数据中，找出n的值，并记录下警局所在社区的编号。但是，经过实际程序的编写，我们发现，由于目前对知识的掌握还有限，很难对模型实现编程运算，故而采取手动输入的方式，对要建立派出所的数目进行约束。从1开始，逐次增加，直到满足题意为止。最终确定当n等于3时，即可满足要求。4.2.2模型的建立4.2.2.1确定目标函数欲求派出所的合理安排，即求派出所在以最大25个单位为中心向外辐射时，能以尽可能少的数量网罗住所有社区，则目标函数如下：2424min11*ijijSDC(*25)ijijDC约束条件：4.2.2.2确定约束条件ⅰ.已知该城市有24个社区。故，对代表社区的字符i和j要进行一个上限约束：124124*25ijijijDCⅱ.以m代表某社区，若mP表示派出所设定在社区m,则其取值为1，并对mP约束如下：(124)mjRPnnRR4.2.2.3综上所述，得到问题（二）的最优化模型2424min11*ijijSDC(*25)ijijDC约束条件：124124*25(124)ijijmjRijDCPnnRR4.2.4模型的求解分析派出所K管辖范围派出所Q管辖范围派出所W管辖范围HDAJQBKRCLSEMTFNUGPVIYWX路线图如下：从图中可以看出，社区T、U可由派出所Q、W共同管辖。这样可能存在责任的分散，由假设1做依据，建议强制规定由其中一个派出所管辖。5.模型结果的误差分析本文解决的是选址问题。对于前两问，为了计算的方便，也是为了建立模型的需要，我们设定了若干个假设条件后，使得模型变得十分的理想化。我们主要是根据图论的思想，进行的是选点计算。故而，将煤气收费站和派出所，可能建立在各个社区之间的道路上的情况给简化了，即没有考虑。所以，在实际建设中，可能会存在很大的空白规划。6.模型评价6.1模型的优点理想化模型的建立，抓住各个社区之间的距离等主要因素，忽略城市规划等等次要因素，使得计算量大大减少又不至于太过偏于实际。6.2模型的缺点过于理想化，在实际的城市建设中，可取性不大，仅能用于理论参考。7.模型的改进7.1模型的改进：㈠模型存在的不足①过于理想化，没有考虑把建设地址修建在各个社区之间的路上。㈡改进对建立模型，最好还能加入更多的条件，比如环境条件等等。在实际建设中，还应结合当地的地理位置、地势等等因素进行综合考虑。8.附录8.1第一问程序：sets:A/1..24/:N;B/1..24/:X;links(A,B):D,C;endsetsdata:N=1012186101548711131111892214871015281813;D=0342428333539544950654554566837322034424124164634037484133375228516343525747576454474754221844243701191728363826472736325520271910181715232828481102028394749375838474366916821291926343933419200819272917381827234623302869131927193533172880111921183010192438313836141421111911393728391911030102941213035294249472525321523225452364727193003326111815211950575533334030388492838492921103303942314045195259573535422533255051263717182926390248126453340452382329371865634758383041114224021121823576466443247414919454327381810211831821091437414846241631212910545236472719301540