多目标公共设施选址问题研究(中文)

基于渐进覆盖的多目标公共设施选址问题研究万波(江汉大学,武汉430056)摘要:传统的选址问题设置严格的覆盖标准，即当超过覆盖半径时完全不被覆盖，这种严格的二分法不切合实际情况。为了更贴切地描述覆盖问题，并考虑公共设施选址的多目标性，本文引入渐进覆盖的概念，以成本最小化、系统效用最大化及基本服务质量最大化为目标，建立了基于渐进覆盖的多目标公共设施选址模型(MPFLMGC)。该模型是一个整数规划模型，本文设计了相应的进化算法进行求解，并以武汉市某区为例对模型进行了案例研究，且就算法的有效性进行了讨论。关键词：渐进覆盖；多目标优化；设施选址；进化算法中图分类号：O22文献标识码：AAMulti-ObjectivePublicFacilityLocationProblemBasedonGradualCoveringWANBo,YANGChao,HUANGSong,DongPeng(1.SchoolofManagement,HuazhongUniversityofScience&Technology,Wuhan430074,China;2.JianghanUniversity,Wuhan430056,China)Abstract:Theconventionallocationmodeladoptsasetofrigidcoveringstandards,whichstipulatesacompleteuncoveringwhenexceedingthecoverageradius.Thisassertivedichotomycan’talwayssatisfythepracticalneed.Inordertodescribecoveringproblemexactlyandconsiderthemulti-objectivecharacteristicsofpublicfacilitylocationproblem,amulti-objectivepublicfacilitylocationmodelbasedongradualcoveringissetup,aimingtorealizethecostminimization,systemeffectivenessmaximizationandtooptimizethebasicservicequality.Thismodelisanintegerprogrammingone.Asareal-worldcase,theevolutionaryalgorithmhasbeenusedcorrespondinglytofindsolutionsbasedonadistrictinWuhan,inwhichtheefficiencyofthealgorithmhasbeendiscussed.Keywords:GradualCovering;Multi-objectiveOptimization;FacilityLocation;EvolutionaryAlgorithm1引言传统的选址问题设置严格的覆盖标准，即当需求点在覆盖半径之内时被完全覆盖，如果超过此半径，即完全不被覆盖。如Toregas等最早将集覆盖选址模型应用于解决消防中心和救护车等的应急服务设施选址问题[1]。Moore和ReVelle提出基于分级的带容量限制的覆盖选址模型[2]。这种对覆盖标准的二分法处理起来相对简单，但是不能很好地反应实际情形，因而不切合实际情况。Church和Roberts提出了渐进覆盖的概念，将覆盖水平描述为距离的分段函数，即当需求点与设施点的距离超过覆盖半径时，其覆盖水平会呈阶梯形递减趋势[3]。随后，学者们对渐进覆盖问题进行了研究，主要集中于定义各种函数对覆盖水平与距离的关系进行刻画，如Pirkul等提出线性递减函数[4]，Berman等提出非凸非凹函数等[5]。选址问题涉及成本、旅行距离、设施服务效用等多种因素，需要设立多项目标，寻求一组均衡解，供决策者根据实际情况和决策偏好进行选择。因此，选址问题是一项多目标优化问题。自二十世纪六十年代以来，多目标优化问题得到了学者们的广泛重视。Brimberg和ReVelle以总成本最小和未被覆盖的需求点最少为目标，针对工厂选址问题建立了一个双目标模型，并通过加权法来求解[6]。Doerner等考虑了成本、覆盖范围、风险等因素，研究了海啸多发地带的多目标公共设施选址问题，并利用NSGA-Ⅱ算法求解[7]。Liao等以成本、客户服务水平及客户响应水平为目标，对联合库存—选址问题进行了研究[8]。Liu等以成本、收益为目标，利用粗糙集理论与模糊决策理论对分销中心的选址问题进行了研究[9]。公共设施选址问题是一个多目标决策问题。同时，公共设施选址问题涉及服务质量，为了更好地刻画服务质量，需要利用渐进覆盖的思想。然而，目前关于渐进覆盖的多目标公共设施选址的研究非常少。基于此，本文考虑渐进覆盖问题，以成本最小化、系统效用最大化及基本服务质量最大化为目标，建立了基于渐进覆盖的多目标公共设施选址模型(MPFLMGC)，并设计了相应的进化算法对该模型进行求解。2相关理论收稿日期：2014-10-10基金项目：国家自然科学基金项目(70871044)作者简介：万波(1972-)，男，湖北武汉人，博士，主要研究方向：现代管理理论与方法，信息理论与信息系统。2.1问题背景公共设施是指城市中呈点状分布并服务于社会大众的教育、医疗、文体等社会性基础设施，公共设施的服务质量是与其公平性及系统效益性等目标密切相关的概念。而服务质量与距离（或旅行时间）等因素相关，当需求点在设施的覆盖半径之内时，服务质量得以完全保证；当超过覆盖半径时，服务质量呈递减趋势；当距离继续增大，达到某一临界值时，服务质量降为零。服务质量与距离的这种关系可以用渐进覆盖的思想进行较好的定义，即将服务质量定义为随距离变化的递减函数。公共设施选址是一项系统工程，涉及到方方面面，需要考虑多种因素。如由于受社会经济发展水平的约束，需要考虑设施的成本最小化；为了充分发挥设施的服务效用，使尽可能多的居民享受到高质量的服务，需要考虑系统的效用最大化[10]；为了保证基本的公共服务质量不断提高，需要考虑最低的服务质量最大化等多种因素。这些因素之间往往是互相牵制，甚至相互冲突，考虑了其中一个方面，就会对其它方面造成负面影响。公共设施选址决策就是要权衡多个目标，获得一组均衡解，或者满意解，即Pareto最优解。传统求解多目标优化问题的方法有线性加权法、极大极小点法、交互规划法等等，这些方法可操作性差，且效率低下，越来越不能适应多目标问题求解。遗传算法具有并行，不需要求导，也不需要其它辅助知识，一次产生多个解及易于实现等优点，被视为求解多目标优化问题的有效方法。目前，改进的非劣排序遗传算法（NSGA-Ⅱ）在求解多目标优化问题时显示出强大的优势，被广泛用于多目标优化问题求解。2.2渐进覆盖传统的覆盖问题设置严格的覆盖标准，如图1所示，需求点在覆盖半径___D之内时被完全覆盖，如果超过此半径，即完全不被覆盖。比如，一所小学的覆盖半径为2.5km，如果一个居民点离学校的距离为2.51km，则该居民点完全享受不到该小学提供的服务，这种严格的二分法虽然比较简单，但与实际情况是不相符的。基于此，当距离超过覆盖半径时，学者们提出了各种覆盖函数。Church和Roberts将覆盖水平定义为距离的分段函数，不同段内的覆盖水平不同，如图2所示[3]。这类函数虽然在传统的覆盖函数基础上进行了细分，但仍然为离散型函数，不能刻画现实生活中连续变化的情况。Pirkul和Schilling将覆盖水平定义为距离的线性函数，当距离增大时，覆盖水平呈线性递减关系，如图3所示[4]。这类函数能够刻画连续变化的情况，但这种线性关系过于简单，难以刻画现实生活中复杂变化的情况。Berman和Krass将覆盖水平定义为距离的非凸非凹函数，如图4所示[5]。这类函数比较贴近现实生活中的距离与覆盖水平的关系，可以较好地模拟真实情况。图1传统覆盖函数图图2分段函数覆盖图图3线性函数覆盖图图4非凸非凹函数覆盖图2.3Pareto最优在单目标优化中，人们寻找最好的解，而在进行多目标优化时，由于目标之间无法比较，且存在互相冲突的现象，不一定存在对于所有目标都是最优的解。一个解在某一目标上是最好的，但在其他目标上可距离覆盖100%覆盖___2D___1D距离覆盖100%100%___D覆盖距离覆盖100%距离___3D___2D___1D覆盖100%距离___D能是最差的。因此，这种无法简单进行相互比较的解称为Pareto最优解。Pareto最优的概念是Francis于1881年提出，Pareto在1896年予以推广的。目前，这一概念被广泛运用于多目标优化研究。多目标优化问题可以表述为以下的形式[11]：1122max(),(),,()qqzfxzfxzfx..()0,1,2,,istgxim令S表示决策空间的可行区域，Z表示目标空间的可行区域。1122(),(),,(),qqqZzRzfxzfxzfxxS。其中，qzR是带有q个目标函数的向量。为了了解Pareto最优的概念，本文作如下三个定义。定义1对于最大化情况，一个目标向量z0占优另一个目标向量z1(01zz)，当且仅当z0的分量都不小于z1的分量，且至少有一个z0的分量大于z1的分量。相应的，如果01zz，则解x0占优x1(01xx)。定义2对于给定点0zZ，它是Pareto最优解，当且仅当不存在其它点zZ，使得对于最大化情况有：(1)0kkzz，对于某些1,2,,kq；(2)0llzz，对于所有其它lk。也就是说非劣解z0不被任何其它解所占优。这些Pareto最优解构成的集合称为Pareto最优解集，记为Ps。定义3所有的Pareto最优解集对应的目标函数值所形成的区域称之为Pareto前沿。表示为12()((),(),,())FqsPfxfxfxfxxP。2.4改进的非劣排序遗传算法（NSGA-Ⅱ）自JohnHollan于1975年提出遗传算法以来，基于生物模拟的进化算法(EvolutionaryAlgorithm,EA)得到了深入研究。如Deb提出了非劣排序遗传算法(Non-dominatedSortingGeneticAlgorithm,NSGA)[12]，Deb等在NSGA基础上提出了改进的非劣排序遗传算法，即NSGA-Ⅱ算法，其算法如图5所示[13]。该算法的主要改进之处在于提出了快速非劣排序策略与拥挤距离排序策略，使近似Pareto优化前沿更加逼近Pareto优化前沿，同时使搜索到的近似Pareto最优解具有良好的多样性[14]。快速非劣排序策略的基本思想为将集合中的每一个解与其它的解按照定义2进行比较与分类。第一次获得的非劣解集称为第一Pareto优化前沿，记为F1，继续按照定义2进行比较，从而得到第二Pareto优化前沿F2。依此类推，可以求得第三，第四Pareto优化前沿等等。在Pareto优化前沿中，对于目标值最小化而言，F1优于F2，依次类推，从而形成排序的非支配层，如图6所示。拥挤距离排序策略的作用在于解决同一Pareto优化前沿的解的选取问题。以双目标决策为例，如图6所示，对于i点而言，取与其最近相邻的两点i－1与i＋1为顶点，构成一个长方形，其平均边长，即相邻的两边之长除以目标的维度可得拥挤距离。在比较处于同一个Pareto优化前沿的两个解时，优先选取拥挤距离大的个体，以保证所求解的多样性。例如，图6中i点的拥挤距离大于i－2点的拥挤距离，故在进行同一Pareto优化前沿F1解的选取时要优先选取i点。图5NSGA-Ⅱ的算法示意图图6非支配层和拥挤距离示意图3模型建立与求解算法3.1符号含义本文需要用到的有关符号定义如下：I：需求点的集合，{|1,,}Iin；J：设施候选点的集合，{|1,,}Jjk；t