城镇消防站布局问题的探讨

城镇消防站布局问题的探讨 杨贤涛（中国人民武装警察部队学院研究生一队 河北廊坊 ）摘要：消防站布局问题在城市规划中具有重要作用，在考虑消防站覆盖范围和经济条件的情况下，将整个地区的消防站抽象为0-1整数线性规划模型，利用隐枚举法解决消防站的布局问题。具有科学性和合理性，避免了依靠经验选址的弊端。关键字：消防站布局 整数线性规划 隐枚举法Abstract: The fire station location play an important role in urban planning. Considering this fire station jurisdiction and the citys economy, this paper abstracts the 0-1 integer linear programming mode from the whole areas fire station, then uses implicit enumeration to solve the problem of fire station location. This method is scientific and rational. It avoids the drawbacks of relying on experience in site selection. Keywords: fire station location, integer linear programming, implicit enumeration1引言城市消防规划在城市建设和发展中具有重要意义,其中,消防站布局规划尤为重要,其内容包括消防站的选址和消防站责任区的划分。由于中国早期的城市建设大多对消防规划关注不够, 消防站选址大多仅依据经验进行, 再加上地方政策等诸多原因, 因此,目前中国的部分城市中，存在着不同程度的消防站布局不合理、站址选择较随意的问题。某些地区消防延时相当突出，而其他地区消防站却设置过多，增加城市财政负担。本文打算运用整数线性规划的方法，对城市消防站进行最优化布局，实例证明该方法是可行的。2整数线性规划理论线性规划（Linear Programming）是运筹学的重要分支之一。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥作用。它具有适应性强、应用广泛、计算技术比较简单的特点，是现代管理科学的重要基础和手段之一。1 线性规划的数学模型由：决策变量（Decision variables）、目标函数（Objective function）及约束条件（Constraints）构成，称为三个要素。0-1整数线性规划是一种特殊形式的整数规划。0-1规划在工厂选址问题、运输问题、投资问题、加工问题、开发新产品问题等方面有着广泛的应用,0-1规划方法为管理人员作决策时提供了科学的依据,是实现管理现代化的有力工具. 本文利用隐枚举法对0-1线性规划模型求解。30-1线性规划的基本模型在实际管理中,很多问题无法归结为线性规划的数学模型,但却可以通过设置逻辑变量建立起整数规划的数学模型. 例如消防站选址决策问题:随着经济的发展,城镇规模扩大，消防设施日益完善。某县计划新建几个消防站，以满足当地的消防需求。而此县有n个地点满足条件。必须在其中选取合适的地点建设消防站。在进行消防站布局时，必须要考虑到消防站必须能够覆盖整个县，而且，一旦发生火灾，最近的消防站能够在15分钟内抵达。同时，还要考虑到，当地的经济能力有限，而建设和运行一个消防站需要大量资金支持。所以，消防站的数量不能太多。因此，管理层认为应该在财务分析的基础上做出决策。对于这样的问题，可以利用0-1整数线性规划来解决，确立目标函数，建立数学模型。0-1线性规划模型的基本形式是：求解0-1型整数规划最朴素的原理和方法便是穷举法，即检查变量取值为0或1的各种组合，注意比较相应的目标值以求得问题的最优解，但这就需要比较2n个结果，当n的数值很大时，这几乎是不可能的。因此有必要设计一些方法，只检查变量取值组合的一小部分，便能够求得问题的最优解，这样的方法称为隐枚举法。2隐枚举法不需要列出所有组合，只需关心目标函数值的最优可行组合，按目标值从优到劣依次列出组合，逐个检验其可行性；最先满足所有s.t的组合为最优解，劣于最优解的组合即使可行，也不列出检验而隐去。4.实例分析说明某县有六个重要乡镇，该县政府计划兴建消防站，因此希望决定建立最少的消防站数以确保每个乡镇至少有一个消防队伍能在15分钟的车程内到达。各乡镇间与其他乡镇的车程时间以下表1所示，试建立最优化模型使得消防站数为最小。车程时间终点乡镇1乡镇2乡镇3乡镇4乡镇5乡镇6起始点乡镇101020303020乡镇210025352010乡镇320250153020乡镇430351501525乡镇530203015014乡镇620102025140表1决策变量为：1,如果消防站建在该乡镇 Xj= 0,如果消防站没有建在该乡镇j=1,2,6目标函数为：Min Z = X1 + X2 + X3 + X4 + X5 + X6由上表，可以统计出各乡镇之间车程在15分钟的情况，具体见表2：车程在15分钟以内的乡镇约束条件乡镇1乡镇1, 乡镇2X1+X21乡镇2乡镇1, 乡镇2, 乡镇6X1+X2+X61乡镇3乡镇3, 乡镇4X3+X41乡镇4乡镇3, 乡镇4, 乡镇5X3+X4+X51乡镇5乡镇4, 乡镇5, 乡镇6X4 + X5 + X61乡镇6乡镇2, 乡镇5, 乡镇6X2 + X5 + X61表2在表2中，X1+X21表示的含义是在乡镇1和乡镇2中必须建立至少一个消防站，以保证乡镇1一旦发生火灾，在15分钟内一定有消防队伍赶到火场，以下的不等式表示的含义与之类似。由此可以建立数学模型为：Min Z= X1+X2+ X3 +X4 + X5 +X6S.T. X1+X21 X1+X2 +X61 X3 +X41 X3 +X4 + X51 X4 + X5 +X61 X2+ X5 +X61 Xj=0, 1 j=1,2,6解题时先通过试探的方法找一个可行解，容易看出（x1,x2,x3,x4,x5,x6）=(1,1,1,1,1,1)就是合于条件的，算出相应的目标函数值z=6。 我们求最优解，对于极小化问题，当然希望z6，于是增加一个约束条件： X1+X2+ X3 +X4 + X5 +X66 后加的条件称为过滤条件。将7个约束条件按的顺序排好（如表3所示），对每个解，依次代入约束条件左侧，求出数值，看是否适合不等式条件，如果某一条件不适合，同行以下各条件就不必再检查。在计算过程中，若遇到z值已小于条件右边的值，应改变条件，使右边为迄今为止最大者，然后继续运算。通过设置和改进过滤条件，可以大幅度减少计算量。解题步骤如下：点条件满足条件？是（）否（）Z值（0，0，0，0，0，0）00（0，0，0，0，0，1）10（0，0，0，0，1，0）10（0，0，0，0，1，1）20（0，0，0，1，0，0）10（0，0，0，1，0，1）20（0，0，0，1，1，0）20（0，0，0，1，1，1）30（0，0，1，0，0，0）10（0，0，1，0，0，1）20（0，0，1，0，1，0）20（0，0，1，0，1，1）30（0，0，1，1，0，0）20（0，0，1，1，0，1）30（0，0，1，1，1，0）30（0，0，1，1，1，1）40（0，1，0，0，0，0）1110（0，1，0，0，0，1）2120（0，1，0，0，1，0）2110（0，1，0，0，1，1）3120（0，1，0，1，0，0）21211112表3（a）至此，z值已不能改进，即得到最优解，解答如下：X1=0X2=1X3=0X4=1X5=0X6=0Z=2也可以继续计算，但在此题中，继续计算已经没有意义，现将后续的计算过程列在表3（b）中：改进过滤条件，用 X1+X2+ X3 +X4 + X5 +X62 代替，继续进行。点条件满足条件？是（）否（）Z值（0，1，0，1，0，1）3（0，1，0，1，1，0）3（0，1，0，1，1，1）4（0，1，1，0，0，0）211110（0，1，1，0，0，1）3（0，1，1，0，1，0）3（0，1，1，0，1，1）4（0，1，1，1，0，0）3（0，1，1，1，0，1）4（0，1，1，1，1，0）4（0，1，1，1，1，1）5（1，0，0，0，0，0）1110（1，0，0，0，0，1）2110（1，0，0，0，1，0）2110（1，0，0，0，1，1）3（1，0，0，1，0，0）20（1，0，0，1，0，1）3（1，0，0，1，1，0）3（1，0，0，1，1，1）4（1，0，1，0，0，0）211110（1，0，1，0，0，1）3（1，0，1，0，1，0）3（1，0，1，0，1，1）4（1，0，1，1，0，0）3（1，0，1，1，0，1）4（1，0，1，1，1，0）4（1，0，1，1，1，1）5（1，1，0，0，0，0）1220（1，1，0，0，0，1）3（1，1，0，0，1，0）3（1，1，0，0，1，1）4（1，1，0，1，0，0）3（1，1，0，1，0，1）4（1，1，0，1，1，0）4（1，1，0，1，1，1）5（1，1，1，0，0，0）3（1，1，1，0，0，1）4（1，1，1，0，1，0）4（1，1，1，0，1，1）5（1，1，1，1，0，0）4（1，1，1，1，0，1）5（1，1，1，1，1，0）5（1，1，1，1，1，1）6表3（b）5 结论本文通过使用0-1整数线性规划的隐枚举法对消防站布局优化问题提出了解决方法，为消防站的选址原则提供了科学依据，不再只是依靠经验，在解决消防站布局优化问题时，当整数变量的个数较多时，可以利用MATLAB软件对0-1线性规划模型进行程序化，从而省去了繁琐的计算。在实际进行消防站布局时，还要考虑其他主客观因素，如当地的地价，是否有消防重点单位，