金忠旭　郭跃显

[提要] 国内现有物资总库选址多采用一条线路至少设置一个物资总库，虽然这种方法可以极大地缩短设施点处理突发事件的时间，但却容易造成重复建设。本文以时间与成本因素为主要考虑对象的物资总库选址问题，提出以集合覆盖选址模型为基础的单物资总库服务多线路的研究方法，建立物资总库选址模型。以沈阳市现有物资总库布局情况为例，运用遗传算法通过MATLAB进行运算求解，优化该城市现有物资总库数量，从而有效降低建设及运营成本，希望本文所研究内容对相关研究者起到一定借鉴意义。

关键词：物资总库；城市轨道交通；集合覆盖选址；遗传算法

中图分类号：F27 文献标识码：A

原标题：基于LSCP的城市轨道交通物资总库选址模型研究

收录日期：2015年11月30日

一、引言

近年来，城市轨道交通的发展在为人们出行提供便利的同时，也面临着各种突发情况，需要对损坏区域进行及时维修，而要达到维修的及时性，不止维修人员要按时赶赴现场，材料工具更需要及时送到，从设施点到需求点的时间长短将直接影响到维修的效率和事故损失程度，因此时间是决定维修效率高低和损失大小的关键因素，必须对物资总库进行合理布局以缩短设备工具的供应时间。传统的布局方式将时间因素过度敏感化，认为服务设施点数量越多，距离需求点越近，维修的能力就越强，事故造成的损失也就越小，这样做虽然可以有效减少设备的供应时间，但是由于地铁运行状况的特殊性，其事故发生的概率相对较小，而服务设施点的建立和日常管理与维护都需要大量资金，如果建立的服务设施点数量太多就会导致上述成本成倍增长，设施利用率显著降低等。

本文物资总库选址与一般物流配送中心等服务设施选址需要考虑的因素不同。传统物流配送中心多考虑成本因素对其选址的影响程度，而本文物资总库的选址更注重将时间因素与成本因素相结合考虑。因此，本文采用集合覆盖模型对现有物资总库进行选址。通过应用集合覆盖选址模型既可以有效减少物资总库建设数量，节约建设成本与运营成本，又可以通过大批量采购或者配送，降低采购和配送成本，提高运输设备的装载率，极大地缓解城市交通压力。

二、相关研究

关于选址问题，国外学者研究相对较早，Coober（1963）第一次提出了设施选址问题，并将极值方程与启发式算法应用于选址问题中。在此之后，不断总结出的选址模型有重心法、集覆盖法、P-中值模型等。Vladmir讨论了基于P-中值的排队论覆盖选址问题。Toregas等人最早讨论了应急服务设施选址的集合覆盖模型，即对于事先给定的服务覆盖半径，如何确定服务设施点的数量及位置，使得所有的需求点距离其最近的设施点不超过覆盖半径。Toregas和Revelle又分别提出了精确求解LSCP的行和列简化算法。Brotcorne等研究了求解需求点离散、潜在设施点连续的大规模覆盖选址问题的快速启发式算法。Karasakal（2015）在其发表的文章中提出了基于多目标问题的部分覆盖下设施选址问题，并应用改进的SPEA2对其模型进行求解。Iris发表了一篇将遗传算法应用到物流供应链设计问题中的论文，具有良好的参考价值。

国内相关学者在选址问题的研究方面也有突出贡献。沈默等运用了重心法对物流配送中心进行选址研究，分析了重心法选址的优点与缺点，并且将重心法选址模型运用到苏宁配送中心选址方案选择中。苗兴东等结合物理学中相关知识，提出了重心法能利用一个二维封闭图形求解重心，以此来解决物流设施的选址问题并通过一个算例对其进行了具体实践。张彩庆等提出了基于P-中值模型的电网检修分公司选址模型，构建了基于P-中值模型的电网检修分公司静态选址方案和改进的P-中值模型的动态选址方案，为检修公司分部的选址问题提供了一种有效的研究方法和选择依据。王世伟提出了在最坏失效状态下的P-中值选址问题，并列举了几个求解中值问题的常用算法。Li等人在考虑实际工程要求的基础上，研究了用经典集覆盖模型进行地铁设备应急抢修点选址问题。当存在成本或资源约束而不能满足所有的需求点时，则要尽可能覆盖可达到的需求点。肖俊华（2012）发表的论文在考虑总体成本最低的情况下，通过对应急储备库选址的深入研究，提出了集合覆盖模型的构建方法。在应用遗传算法对选址问题进行求解方面，谭前进（2007）等发表的文章论述了以遗传算法为基础的物流配送系统方案设计，阐述了遗传算法在车辆调度中的应用。通过模拟实验，该智能化配送系统适合于任何中小型物流公司调度车辆。张琨（2011）对武汉城市轨道交通网进行了全面的调查和研究，基于成本因素的考虑提出了多线共用物资总库的模式，并对物资总库布局建立了相应的总体规划模型，通过遗传算法与MATLAB软件实现了武汉市物资总库的选址研究。

本文在参考上述思想方法与理论的基础上，对模型的选取进行了深入研究。考虑到物资总库优化选址属于服务设施点数量、位置选择均未知的多物流节点选址问题，重心法和P-中值模型无法满足其要求，而集合覆盖模型是解决在时间要求的覆盖半径内以最少数量的设施点服务所有需求点的问题，从而完成对设施点的选址。同时，对物资总库选址相关论文的研究中并未见采取集合覆盖模型的选址方法。因此，本文从单设施点服务多需求点的思想出发，提出了基于集合覆盖方法的物资总库选址模型。

三、建立选址模型及遗传算法设计

（一）选址模型关键因素分析。物资总库选址是受多重因素影响的综合性选址问题。不同位置、不同目标的物资总库在选址时需要考虑的影响因素有所不同，由于本文所研究的选址问题是应用集合覆盖选址模型对物资总库进行选址，其主要影响因素重点分析了以下两点：

1、时间因素。本文重点研究在时间因素影响下进行物资总库选址的问题。城市轨道交通属于公共基础设施范畴，主要作用是为人们出行提供便利，改善人们生活质量，如遇到紧急事故，一条线路出现问题将会影响另一条线路的正常运行，在链式反应的作用下，整个城市的轨道交通都可能陷入瘫痪，其造成的经济损失将无法估量。因此，应将维修的及时性放在首位，在要求的时间内将事故妥善处理好，从而避免更大的经济损失。根据国外研究统计，在发生事故20min内如果能得到及时处理，所造成的经济损失与40min后才得到处理，经济损失比值约为1∶8。故本文以20min作为集合覆盖模型时间覆盖半径，即每个设施点所服务对象是以20min能到达为基准，否则该设施点将失去对其服务的能力。

2、经济因素。经济因素主要包括物资总库的建设费用、建设数量等。具体来说，应该考虑物资总库所在地地价，同时如果建设过多的物资总库，虽然为需求点提供服务速度快、时间短，但是建设费用、运营费用会随着物资总库数目增加而增多，一般情况下，物资总库是建设在车辆段内部。所以总体来说物资总库的数量并不是一味的越多越好。在满足覆盖所有需求点的要求下，应尽量建设少的设施点。

（二）模型建立及描述。集合覆盖（LSCP），是指在备选设施点和需求点的数量已知情况下，用尽可能少的设施点来覆盖所有需求点，从而确定一个满意的设施点集合，要求其满足所有的需求点至少覆盖1次，同时总体建设成本最低，其基本模型如下：

其中目标函数（1）式要求达到建立的服务设施点数量最少；约束（2）式表示对任意一个需求点i，至少有一个设施点j可以为其提供服务；（3）式是变量取值约束条件。

物资总库选址只包括两类站点，一类是需求站点，文中称为需求点；一类是服务站点，文中称为物资总库。本文以各个物资总库的建设及运营成本Cj以及物资总库与各需求点之间的时间距离Tij作为主要参考数据，建立物资总库集合覆盖选址模型，模型假设如下：

假设1：物资总库和需求点均为点状形式存在的离散点；

假设2：任意物资总库和需求点的时间距离可通过调查或计算产生；

假设3：各物资总库的容量无限制。

目标函数（4）表示模型以总成本最低为目标；约束（5）表示每个需求点i至少由1个设施点j为其提供服务；约束（6）表示yij=1时需满足的前提条件是需求点i到服务设施点j的时间距离不大于时间覆盖半径？兹，否则为0；约束（7）为二元整数决策变量。

（三）模型求解算法。遗传算法是一种较新的全局随机搜索算法，其基本思想源自于达尔文的“适者生存”理论和生物遗传学观点，具有较强的可操作性，鲁棒性高，应用范围广。遗传算法自出现以来就在函数优化问题中得到了广泛应用，由于其只需函数值的相关信息，不需要设计空间或函数的连续，因而适合于求解各类函数优化问题。同时，遗传算法能在设计空间的较大范围内寻找最优解，因而更有可能获得全局优化解。目前，遗传算法已用来解决连续变量优化问题、混合离散变量优化问题、组合优化问题等。但是遗传算法的应用难点在于对研究者的编程能力有一定要求，而这一问题在MATLAB 7.0软件之后得到了妥善解决，在MATLAB 7.0中增添了GADS的GUI界面，它使用MATLAB矩阵函数为实现广泛领域的遗传算法建立了一套通用工具，这套工具是用M文件写的命令行形式的函数，是完成遗传算法大部分重要功能的程序的集合。用户可通过这些命令行函数，在GUI界面上根据实际分析的需要，选择不同形式的初始种群数量、遗传算子等。其基本实现步骤如下：

第一步：确定适应度函数及约束条件。本文采用的适应度函数为所提供的目标函数式（4），将待优化的函数在MATLAB界面点击New Script，编写函数式为相应的M文件形式。从而在GUI界面Fitness function处填写@function name。

第二步：确定编码方式。采用序号编码方式（Double vector），编码位串长度为需求点的个数，基因的数值为设施点的编号，基因的位置为需求点的编号。例如，有4个服务设施点，8个需求点，染色体{1，3，4，2，4，1，2，1}表示设施点1为需求点1、6、8配送设备工具，设施点2为需求点4提供配送，设施点3为需求点2提供配送，设施点4为需求点3、5提供配送服务。

第三步：确定初始种群。遗传算法是对群体进行的进化操作，需要准备一些表示起始搜索点的初始群体数据。本文将初始种群数设定为M=40。

第四步：设计遗传算子。选择算子作为实施“适者生存”的演化方式，采用最佳个体保存法，本文直接复制种群中的两个最佳染色体到下一代，再按轮盘赌方式进行剩余个体选择操作，这样可以保证遗传算法的收敛性；交叉算子使用Scattered（分散）方式，这是一个缺省的交叉函数，它创建一个二进制向量，如果这个向量某位是1，则这个基因从第一个父辈中来，并且设定本文的交叉概率PC=0.8；变异算子采用常用的高斯变异，其中将Scale和Shrink设置为缺省值即可。

第五步：终止条件。遗传算法是一种反复迭代的随机搜索方法，在每次迭代中，记下适应值最大的染色体，直到已经达到了算法规定的最大迭代次数或在规定的连续迭代次数内最好的染色体不再发生变化时算法终止。当算法终止时，最好的染色体即是该选址问题的最优解。本文设定最大迭代次数。

四、应用算例

沈阳市地铁线路有40个需求点，现有的物资总库数目为12个，各个物资总库的建设及运营成本如表1所示。为整合仓储资源，节约日常运营成本，合理优化仓储网络布局，对物资总库数量进行削减。首先通过实地调研与考察，由于地铁线路固定，任意两地间的行驶时间变化不大，因此各个位置点的相关时间参数如表2所示。假定模型覆盖时间半径？兹=20（min）。图1所示为优化前的需求点与物资总库布局示意图。（表1、表2、图1）

由表3可知，优化后的物资总库足以满足现有需求点的调运方案，并由此会节约的成本为8，560万元。（图2）

五、总结

本文在进行物资总库选址时，由于考虑到城市轨道交通的特殊性，时间因素是影响其选址的重要因素，同时又必须考虑建设及运营成本对选址的影响，故本文在两者共同影响下，应用集合覆盖选址方法，建立了物资总库的选址模型，并借助遗传算法寻求最合理的选址结果，通过算例对模型的应用进行了实验，结果显示优化后的物资总库布局可降低总成本数额为8，560万元。

由于本文是在假设各服务设施点容量无限制的情况下，重点研究时间与成本因素对选址的影响，同时由算例的结论可以知道，某一需求点可由多个设施点为其提供服务，因此将来的拓展方向将是考虑在多目标同时影响的条件下通过多目标决策与其他启发式算法等对物资总库选址做进一步优化，并且对多设施点均可提供服务问题，做出优先级的排序，使其更符合现实需要，创造更大的应用价值。

主要参考文献：

[1]Cooper S.L.Location-allocation Problems[J].Operation Research，1963.11.

[2]Vladmiir Charles.The queuing probabilistic location set covering and some extension[J].Socio-economic Planning Science，1994.28.

[3]Toregas Revelle，L.Bergman.The local of emergency services facilities[J].Operations Research，2011.19.

[4]Toregas Revelle.Optimal location under time or distance constrains[J].Papers of the Regional Science Association，2012.28.

[5]Toregas Revelle.Binary logic solutions to a class of location problems[J].Geographical Analysis，2011.5.

[6]Brotcorne Laporte.Fast heuristics for large scale covering location problems[J].Computers & Operations Research，2002.29.

[7]Karasakal Silav.A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage[J].2015.

[8]Iris Asan.A review of genetic algorithm applications in supply chain network design[J].Computational intelligence systems in industrial engineering—with recent theory and applications. Atlantic Press，2012.

[9]Li Man. Research on the location allocation model for subway emergency service facilities under network operating conditions[C].IEEE Press，2011.