基于场景规划的随机型设施定位问题优化研究

王来军，胡大伟，高 扬

(长安大学汽车运输安全保障技术交通行业重点实验室，陕西西安710064)

0 引言

场景规划是一类针对多种可能发生情况进行综合决策的方法，可用于求解随机规划问题.场景规划方法在应用时，通常先由决策者提出几种未来可能发生的情形，这些情形被称为场景，然后再针对这些场景做出问题的决策，决策目标是找出在所有场景下均能运作良好的方案.需要注意的是，决策时所有的场景都是没有发生的，但通常能确定各场景的发生概率.场景规划法有定性和定量两种应用方法.笔者将运用定量的场景规划理论研究、解决随机型的设施定位问题，且该类型问题同时属于容量受限的多设施定位问题.

多设施定位问题(Multi-Facility Location Problem，MFLP)是常见的组合优化问题，其显著特点就是针对一定的需求量需要选择确定多个设施作为服务点［1］.在MFLP中，如果设施点和需求点之间还满足一对多的对应服务关系，则该问题属于多覆盖问题(Multiple Coverage Problems，MCP)［2］.MFLP 研究的重点在于大规模问题，如Jia等［3］(2007年)曾针对医疗供给领域的大规模定位问题进行了研究，并考虑了多覆盖情形.Küɕükdeniz［4］(2012 年)针对一类具体的需求点固定的多设施定位问题进行了研究，提出了一种模糊c-均值丛集算法.

容量受限的设施定位问题(Capacitated Facility Location Problem，CFLP)则是生产规划及通信网络规划领域的常见问题，多用于相关设施的选址，其典型约束就是在满足所有需求的前提下每个设施的供给量是受限制的［5］.

对设施定位问题，如果费用、需求或其它方面涉及不确定或随机因素，则称之为随机型设施定位问题(SFLP).Rawls and Turnquist［6］(2010 年)对紧急情况下SFLP在供应链中的应用进行了研究，Murali等［7］(2012年)研究了大城市基于距离覆盖的医疗点分布问题，该问题主要考虑不同区域医疗需求的随机性［7］.

基于对MFLP、CFLP和SFLP三类问题的分析，笔者针对交通运输系统中的客运枢纽规划问题进行研究，在保证实际应用效果的基础上，充分考虑问题的需求随机性和站场容量约束，提出一类随机型的容量受限多设施定位问题(SCMFLP)，并建立问题模型、设计问题求解算法，最终给出应用结果及相关分析.

1 建立模型

问题描述:对给定区域，给定潜在的设施集合以及需求点集合，假定每个潜在设施点的供给量受到限制且设施位置给定，但各个需求点的需求量并不确定.从这些潜在的设施点中按照一定的范围选择位置来建立满足容量约束的多个设施，使得在各个需求点的需求都能得到满足的前提下，总体费用达到最小.

笔者之所以研究这类问题，是因为现实中常遇到类似的枢纽选址问题，这一点在后面的应用部分有具体案例来说明.基于场景规划理论，针对需求量不确定情形，给出场景集合 E={e1，e2，…，eS}，表示未来系统运行状态存在S种情形或场景.每个场景es(1≤s≤S)都会按照一定的概率发生，而es发生的概率可通过一定途径获得，不妨表示为qs，则所有场景的发生概率满足:=1.对于交通运输系统中的枢纽规划，将上述场景规划方法运用，得到极小化问题模型如下:决策变量中:xsij表示在场景s下需求点i对设施j的分配量;yj是0-1变量，在设施点j建立设施取1，反之为0;Vj表示j的建设容量，其取值可通过约束条件(4)实现.

其它量中，I表示需求点的集合;J表示潜在设施点的集合;cij表示从i到j的单位费用;fj表示在潜在施点j建立设施时的产生的综合费用，它是包括征地费用、建设费用和运营费用等在内的综合性费用度量指标;dsi表示在场景s下需求点i的需求量.

目标函数式(1)中，第一部分表示将要发生的交通运输费用的期望值，第二部分表示实际产生的综合建设费用.约束条件中，式(2)表示给定需求点分配给所有设施点的需求量之和等于自身的总需求量;式(3)是对需要建立的站场总数量进行限制使之在一定的范围之内，其中，Nl，Nu分别表示下限和上限;式(4)表示站场的容量务必大于或等于它所要处理的需求点的需求量之和;式(5)是潜在设施点站场的容量(规模)限制，即任一设施点所建站场的处理能力都是限定的，笔者以分别表示其上下限，为已知量，具体应用时可根据站场级别来处理;式(6)表明决策变量的取值范围，同时表明模型属于混合整数规划.

事实上，具体应用时，如果需求量相对集中，可以简单地选取片区的重心作为需求点，并约定每个需求点单独分配给某个设施点.这点可通过决策变量的设置来实现，从而将模型转换为全整数规划(0-1规划).当每个需求点单独分配给某个设施点时，则模型(1)～(6)可转化为

此处决策变量为 xij，yj，Vj.其中，xij同前面的含义完全不同，它表示是否将需求点i整体分配给设施j，如分配，值为1，反之为0.同模型(1)～(6)相比，由于目标函数的计算难度降低、约束条件减少，模型(7)～(12)的计算量将大大减少，但代价是前期相对更大的调研量.

2 算法设计

SCMFLP问题属于NP-Hard问题.求解此类问题，通常可以采用拉格朗日松弛等方法［8］，如Benat［9］(2003 年)等.但如果要求解规模较大的实际问题，近似算法则更实用，如 Ahuja［10］(2002年)等.笔者选择了一种启发式算法—遗传算法，来求解本文的问题.选择遗传算法，除了算法自身的优点外，主要是因为模型的约束条件可通过遗传算子的针对性设计而得到完全满足.根据问题特点，设计遗传算子如下.

(1)编码.笔者采用符号编码方式，即如果一个设施点被选中建立站场，则标识为符号“1”;否则，标识“0”.这种编码策略非常简单明了，且可以有效地缩小遗传搜索空间，降低算法的计算复杂性.具体形式如下所示.

图1 染色体编码图例Fig.1 Illustration of coding

注意，染色体“1”的数量必须加以控制，以免不满足(3)或(9)而产生无效染色体.

(2)交叉.为避免交叉导致染色体无效，可采取一定措施.如图2将染色体分成3段，限定1，3段基因位中符号“1”的个数为1～2个，限定2段为2～3个.此时，各段中符号“1”的个数是限定的，所以交叉时只需将分段点作为交叉点，就可以保证交叉后个体编码中各段、进而整体中符号“1”的个数保持不变，即保持染色体有效.

图2 染色体分段交叉示例Fig.2 Illustration of sectional crossing

(3)变异.采用“成对变异”策略［11］.比如图 3中，当4号基因位发生变异时，则非4号基因位(这里随机选取7号基因位)发生相反变异.

图3 染色体变异图例Fig.3 Illustration ofmutation

(4)适应度.适应度函数形式如下:

式中:M为某个给定充分大正数;f为目标函数.f的计算是基于一定分配原则进行的.分配原则就是将客源需求点的需求量分配给站场要建立的设施的规则.通常，可采用就近原则，对于模型(1)～(6)，分配量满足:

式中:k表示对站场j而言的分配轮次，初次分配时令 k=1，Vj，0=0.在同代计算中，每个站场的被分配次数不尽相同，取值最小为0，表示它没有被分配客源，最大为达到该站场容量上限时的数值或所有客源均被分配完时的数值.

对于模型(7)～(12)，分配量满足:

不同于式(14)，式(15)中不含有分配轮次k，因为需求点被一次性分配给某站场.

(5)全局收敛性.为了保证算法的全局收敛性，采用了最优保留策略以及进化策略［11-13］.

3 应用案例

3.1 模型及场景选择

案例为中国西部某城市的国家级客运枢纽选址规划问题，且规划区有两个特点:①规划区经济发展不均衡，出行人口影响因素多，出行量变化规律性较差.②出行人口分布广，且规划区地形成狭长状，根据宏观政策和行政区域划分，拟规划建设3～7个客运枢纽站场.

根据特点①，本案例选择随机优化策略.根据特点②，并考虑到前期数据调查的充分性，选择模型(7)～(12).

场景选择方面，根据行政区域划分结合人口数量统计，设定30个需求点，然后对需求点的需求量(日均出行人口数量)，给出三类场景，相关数据见表1.表1中，场景S1对应正常预测所得的需求量，S2和S3分别对应经济发展增速和放缓情况下的需求量.

表1 三类场景下的需求量数据表Tab.1 Demand data under three scenarios

3.2 数据及参数处理

本案例数据均源自实际统计，并经过了合理的单位换算或取整等简单处理.基于当地政府部门的总体建设规划，结合当地的地形地貌等，本案例中给出了10个潜在设施点(规划客运站场).假定广义距离(可达距离结合路况等)同单位交通运输费用成正比，所以用广义距离乘以一定的系数λ，可得到从30个需求点i到10个设施点j的单位交通运输费用.广义距同实际距离数据间进行了1∶1 000的比例缩放.假定站场每年使用350 d，每人次单位广义距离出行费用0.5元，则系数λ=350×0.5.详细的广义距离表可参见文献［11］.

进一步地，假定潜在设施点的建站规模或等级同投资费用成正比，但是如果是对已有站点进行改造或扩建，则另行对待.

在算法参数的设置方面，根据地形地貌及当地物价，10个潜在站场的固定建设费(含土地征用、建设或改扩建、运营等全部费用)及算法相关参数设置见表2.根据投资费用及改扩建情况可确定站场等级.

表2 算法及站场相关参数设置Tab.2 A lgorithm and station parameters setting

3.3 算法步骤

鉴于案例的规模并不太大，采用基本遗传算法.事实上，笔者尝试对算法加入了一些改进措施［12］，但对求解速度和最终结果无影响.本文算法步骤类似于文献［11］.

3.4 结果及分析

按照上述步骤，建立了基于VB环境的计算程序，并对3种场景情形的问题进行了求解，得到主要结果如表3和图4所示.

表3的结果是进行了多次计算得到的稳定结果.事实上，当对表2的部分遗传参数进行调整时，虽然运算速度变化较大，但最终的最优解和最优目标值都是确定的.表3表明，最终的决策方案为分别在2，4，6，8这4个潜在场址建立3个1级站和1个2级站，站场建设费用结合表2可知总计:2千万+3.5千万+4千万+2千万=11.5千万，其中2号场址属于扩建，所以虽然是1级站但投资费用仅为2千万.基于此，容易得到总体交通费用(出行费用)大小为:23.07千万 -11.5千万=11.57千万.

表3 优化的结果Tab.3 The results of optim ization

图4中，小黑点代表需求点(客源)，小圆圈代表潜在设施点(站场)，五角星代表从潜在设施点中优选的拟建或拟改扩建的站场.与最优费用相比较，随机给出一种可行解，如在2，3，5，6，9 建站，对应的总费用29 069.15万元;对初始群体进行平均，对应的总费用为28 553.28万元.可见，本文的模型和算法合理实用，优化效果明显.

图4 拟建站场示意图Fig.4 View of the planned stations

注意，由于目标函数主要包括两部分:出行费用、建设费用，在实际操作中应该注意要控制两部分费用的相对大小，以便保持两部分费用对总体优化效果影响的均衡.比如，在仿真过程中，给系数λ乘以5，仿真结果没有变化，但当乘以500时，即使优化模型及其它参数没有任何变化，但优化结果发生了变化，选择的站场变化为1，4，6，8，站场的建设费用也增加了.出现这种状况是因为此时的出行费用数以千亿计，站场建设所差的一两千万对总体优化的影响已经非常微弱.

另外，笔者对3种场景下的确定型优化问题进行了求解，即假定仅仅发生某个场景.结果表明，除了第二种场景外，最终费用都比随机优化要少，这是合理的，因为计算中没有考虑站场容量不足所导致的“损失”，即没有考虑其它场景发生时总体需求没有得到全部满足时带来的相应损失，这个损失类似于存贮问题中的缺货损失.

4 结论

针对随机型的多设施容量受限的设施定位问题，采用场景规划方法对其进行了研究.首先，运用场景规划方法对该问题的需求随机性进行了处理，并据此建立了两类优化模型，通过约束条件的限制体现了站场总体规划思想，使得模型更能反映实际情况.笔者对模型的各部分含义进行了分析、讨论，对比两类模型的优缺点.进一步地，针对所建模型的NP属性和构造特点，设计了求解模型的符号编码遗传算法，该编码方法非常直观地体现了问题的特点并使得问题的求解规模得到有效控制.最后，通过具体的案例应用及结果分析，表明了笔者所建优化模型的正确性和求解算法的有效性.研究结果对解决实际的枢纽规划问题具有重要参考价值.

［1］ ANDREASK，ANDREASD.Facility location models for distribution system design［J］.European Journal of Operational Research，2005，162(1):4-29.

［2］ In MIRCHANDANIPB，FRANCISR L，Discrete location theory［M］.New York:Wiley-Interscience，1990:263-304.

［3］ JIA H，ORDONEZ F，DESSOUKY MM.Solution approaches for facility location of medical supplies for large-scale emergencies［J］.Computers and Operations Research，2007，52:257-276.

［4］ Küɕükdeniz T，ALP BARAY，ECERKALE K，et al.Integrated use of fuzzy cmeans and convex programming for capacitated multi-facility location problem［J］.Expert Systems with Applications，2012，39:4306-4314.

［5］ KLOSE A，GORTZ S.A branch-and-price algorithm for the capacitated facility location problem［J］.European Journal of Operational Research，2007，179:1109-1125.

［6］ RAWLSC G，TURNQUISTMA.Prepositioning of emergency supplies for disaster response［J］.Transport Research Part B，2010，44:521-534.

［7］ MURALIA P，Ordóñezb F，DESSOUKY M.Facility location under demand uncertainty:Response to a large-scale bio-terror attack［J］.Socio-Economic Planning Sciences，2012，46:78-87.

［8］ FAN Y，LIU C.Solving stochastic transportation network protection problems using the progressive hedging-based method［J］.Networks and Spatial Economics，2010，10(2):193-208.

［9］ BENAT S.An improved branch＆ bound method for the uncapacitated competitive location problem［J］.Annals of Operations Research，2003，122(1/4):43-58.

［10］ AHUJA R K，ORLIN JB，PALLOTTINO S，et al.A multi-exchange heuristic for the single-source capacitated facility location problem［R］.MIT Sloan School of Management，Working Paper No.438702，October 2002.http://ssrn.com/abstract_id=337621.

［11］王来军，胡大伟，史忠科.开放型设施定位问题的理论模型和应用研究［J］.西北大学学报:自然科学版，2007，27(4):556-560.

［12］胡大伟，陈诚，王来军.带硬时间窗车辆路线问题的混合遗传启发式算法［J］.交通运输工程学报，2007，7(5):112-117.

［13］杨丽娜，刘刚，王秋生.一种改进的遗传算法及其应用［J］.郑州大学学报:工学版，2005，26(3):98-101.