网站地图
Baumol-Wolfe模型

Baumol-Wolfe模型是针对动态选址问题的模型。

从19世纪60年代中期开始,选址问题的研究多了起来,很多问题的输入条件为确定的值。有些研究通过建立多目标规划模型来得出满意的设施位置。选址问题有两类基础问题,很多研究都是在这两类问题基础上设置不同的条件进一步扩展的,这两类基础问题分别是:中值问题;覆盖问题,这两类问题最初研究的都是静态确定型选址问题

Hakimi所提出的第一个与应用领域无关的设施选址问题就是P-中值问题。这种方法可以用来找出P个设施位置,使需求点和设施之间的以需求量为权重的运输距离之和最小。此模型可以在有限的待选点中选择设施位置。在上面的模型中,这些待选点位于网络的结点上。有研究人员研究了待选点位于网络边上的情况,关于这一问题Hakimi已经证明了,在网络中选定P个设施位置,对于P-中值问题,在网络顶点处至少有一个最优解。这样,可以将待选点位于网络边上的问题简化成待选点只位于网络顶点处的问题,这种简化不会影响求解结果和目标值的最优性。

P-中值问题被归类为NP-complete问题。将待选点限定在网络顶点能够很大程度简化问题。

正如Church和ReVelle所说,评价一个设施选址结果的很重要的标准是到达这些设施的距离最小化。平均运输距离增大,设施的可达性就减小,从而降低了设施的有效性。当客户需求对服务水平不敏感时可以采用另外一种评价设施位置有效性的方法,即将需求量作为权重,将需求量与需求点和设施之间的距离一起使用,来计算需求点和设施之间的有权重的运输距离之和,以此作为评价设施可达性的标准。

P-中值问题的应用范围很广泛,适用于以平均运输距离最小为选址目标的情况。但是对于某些设施,如:在城市中选择诸消火栓或急救中心这类紧急服务设施时,在选址中必须考虑使需求点能够在最短距离或时间内到达设施获得服务。如果一个需求点能够在一定的时间内得到服务,我们称它被覆盖了(covered),此类问题也称为覆盖问题。覆盖问题分为两类,分别是集合覆盖问题和最大覆盖问题。集合覆盖问题的目标是用最少数量的设施去覆盖所有的需求点。而最大覆盖问题则研究在给定数量的设施下,覆盖尽可能多的需求点。最大覆盖问题并没有考虑需求量,认为所有需求点的需求量相等,目标函数仅是设施覆盖的需求点数量最大。

基本的最大覆盖问题没有服务距离的限制,如果增加服务距离条件,当需求点不能在要求的服务距离S内得到服务,那么必须在服务距离T(T>S)内得到服务时,问题就变为“有强制范围条件的最大覆盖问题”(maximal covering with mandatory closeness problem)。此问题的目标是使被覆盖的需求点距离它最近的设施不超过T距离,同时保证尽可能多的需求点位于S距离范围内。Orhan和 Esra专门针对如何确定T和S进行了研究。

在前面讨论的覆盖问题中都假设,如果一个需求点被覆盖了,那么它就能从设施处得到服务。但是Daskin和Stern]提出了EMS(Emergency Medical Service)车辆定位的覆盖问题,在这个问题里上面的假设条件就不能成立。若EMS车辆已经响应了一个需求,就不能同时响应另一个需求。针对设施有忙期或不作用期的问题模型也有很多。Batta和Mannur认识到,在EMS车辆配置中有多个响应组的需求问题很难解决,他们分析了具有一般性的确定性的集合覆盖模型和最大覆盖模型,在这些模型中考虑了多个响应组和需求相关的覆盖要求,并对每一问题的求解方法也进行了研究。Tavako和Lightner对Fayetteville市的EMS车辆选址问题进行了研究并得出了满意的结果。

在上面两种基本问题的基础上增加不同的条件又产生了多种新的问题。将基本选址模型进行扩展可以将固定成本或建设成本包括在内。再扩展还可包括设施的容量限制。没有容量限制的固定成本设施选址问题(uncapacitated fixed facility location problem),与P-中值问题相似,在P-中值模型的目标函数中加入固定成本,并将选定设施数量约束从约束条件中去掉。由于此类问题的求解难度,很多研究人员提出了启发式算法,如禁忌搜索方法、领域搜索方法。Elena和Justo研究了多目标的无容量限制的选址问题。Sankaran和Raghavan 对P-中值问题进行了扩展,将设施的容量限制考虑在了选址问题中。Mukundan和Daskin 则从利润最大化的角度考虑了同样的问题。

设施选址问题往往不仅要选择设施位置,还要考虑分配的问题,即需求点应怎样由设施提供服务。这就是选址-分配问题(location-allocation)此问题也是建立在基本选址模型基础上的。不但能够确定设施位置,同时还能得出设施和需求点之间的流量。这类问题Scott进行了综述,它是将标准运输问题与选址问题结合起来,来选择设施位置。Sherali等研究了选址-分配问题的全局优化方法。

前面所提到的模型都是以方便需求点到达设计为目的的,而有些设施,如垃圾处理厂、核电站等,大家期望这种设施越远越好。对于此类设施就产生了一类称为“易受谴责(obnoxious)设施”选址的问题[35]。处理这类情况的问题包括:反中值问题(antimedian problem),目标是使设施与需求点之间的平均距离最大化;反中心问题(anticenter problem),目标是使设施与需求点之间的最小距离最大化;p-分散问题,目标是使任意两个设施之间的最小距离最大化。

在静态确定型的选址问题中还有一种是中心问题(center problem),其目标是Minimax,使需求点与设施之间的最大距离最小化,即优化最坏的情况。这种问题通常在军队和公共部门中使用。它与中值问题和覆盖问题有所不同,但可归类为静态确定型选址问题。

设施选址问题是属于战略层的决策问题,设立一个新设施将会是一项时间跨度较大的项目,因此期望所建立的设施在建成后的一段时间内都能够很好地实现既定目标。在设施生命期内,周围环境的变化可能会使原来适合建立设施的地点变得不合时宜,因此选址模型需要考虑到将来的变化。使选定的设施位置在将来一段时间内仍保持最优性。也就是说,决策者不仅要选一个在当前时间需求情况下最优的设施位置,而且在将来情况发生变化后仍然最优的设施位置。

Ballou第一个提出了动态选址问题,他提出静态、确定型选址模型在应用上没有考虑到时间的变化,并研究了如何选择一个仓库使其在规划期内实现利润最大化。他的方法是在决策期内的每个阶段,求解出最优仓库位置,建立一个“好位置”集合,然后使用动态规划方法来求出决策期内一系列最优位置集合。Sweeney和Tatham在Ballou的基础上提出了改进方法。由于这些方法都没有考虑到设施建设所需要的时间,所以Wesolowsky研究了一个无约束的有限规划时期的单设施选址问题,他在其中加入了再选址成本。Drezner和Wesolowsky研究了一个成长型城市的设施选址问题,这个城市的人口数量随时间在发生变化(可预测的),这就意味着随着时间变化,需求量也在发生变化,只是这些变化是确定型的。他们的目标是找出一个设施位置,使其在规划时期内的成本最低。

Scott[研究了动态选址-分配问题,此问题研究多设施在多个规划期间的选址。Wesolowsky和Truscott 进一步研究了多阶段选址-分配问题,在他们的研究中设施可以根据预测的需求变化改变位置。他们提出了一个整数规划模型,约束条件为每一阶段允许变化位置的设施数量,还提出了一个动态规划模型。Sheppard的研究扩展了此类问题的应用范围,他提出了各种模型,适用于工业或公共领域里的多种情况,不但能够确定多个设施的位置,而且能够确定设施的规模和建设/扩建时间。Drezner研究了改进的p-中值问题(progressive P-median problem),在T个规划期内选择P个设施,他的研究没有考虑设施再选址。Balakrishnan在前人研究的基础上提出了一种改进算法,来求解多规划期的设施选址问题。

另外一种能考虑时间跨度的设施选址方法是Daskin等提出的。作者认为由于未来环境的不确定性,求解动态设施选址问题很困难。他们认为应对不确定性的最好方法就是尽可能延迟决策,收集尽量多的信息,随着时间的推进提高预测的准确性。在各决策阶段中,第一个决策阶段是唯一一个需要即时实施的决策,所以作者认为动态选址决策的目标不应该是决定所有阶段的设施位置或再选定位置,而是找出所有选址规划阶段中第一个阶段的最优位置或近似最优位置。

静态、确定型模型假设输入的参数值是确定的,或在一定时间内是确定的;动态选址研究的是在将来一定规划期内针对可预测变化的设施选址问题,因此输入参数也可认为是确定的。但现实世界内却有诸多不确定性,下面回顾随机型选址问题的研究。

研究随机选址问题的方法可以分为两大类,一类是概率方法(probabilistic approach),一类是场景规划方法(scenario planning approach)。在两种方法中都会假定某些参数是不确定的,这些参数包括:运输时间、建设成本、需求位置、需求数量。选址目标是选定健壮(robust)的设施位置,使其在不确定的环境下能够较好地实现系统目标。概率方法主要是使用概率分布函数来表达模型的参数。场景规划方法并不是直接使用函数表达式来表示模型参数,而是将概率分布函数使用生成的一系列变量数值用在模型中,与模拟方法有相似之处。Mulvey等讨论了概率方法和场景规划法和优、缺点比较。下面分别对概率方法和场景规划方法进行讨论。

在1961年,Manne首先提出了输入条件为随机变量的选址问题。他的研究前提为,需求量是不确定的,未满足的需求可再次订货;设施容量可以扩大。问题的目标为总扩张成本最低。这项研究结果表明,需求的不确定性对模型的其它方面没有影响,但所求出的设施容量变大了。Bean等研究了需求随机增长情况下,在无限时间范围内的设施容量扩大问题。在此研究中允许非固定的、连续或离散的需求,但是未满足的需求不允许再订货,只有当现有商品消费完时才能再订货。Berman和Odoni还有Berman和LeBlanc研究了运输时间变化时重新选择P个设施中的一个或多个设施位置的问题。这项研究的网络状态定义如下,当有至少一条边的运输时间发生变化时,称网络状态发生变化。在两篇文章中都使用了马尔柯夫变化矩阵来求解网络的变化状况。Mirchandani研究了运输特征、供应/需求模式为随机情况的P-中值问题和无能力限制的仓库选址问题,他所关注的应用领域是消防设施选址问题。在他的研究中还考虑了服务需求拥挤的情况,当并发服务需求过多时,有些需求点的需求可能会得不到满足。

使用概率方法研究设施可得性的问题也有很多。Daskin将确定型的最大覆盖模型扩展应用到EMS车辆问题中,他考虑了车辆处于忙时的需求情况。假设各车辆处于忙状态的概率是不相关的,并且各车辆处于忙状态的概率是相同的。作者提出了单点替代启发式算法(single node substitution-based heuristic)来求解此问题。ReVelle和Hogan提出了两种新模型来研究集合覆盖问题中的车辆可得性问题。Beraldi等提出了一种解决随机EMS车辆的选址问题,他提出的模型不但能确定EMS服务设施的位置,而且能够得出在各选定位置处应配置车辆的数量。

EMS问题激发了大量的相关研究,研究人员已经将其研究成果广泛应用于各种随机选址问题。Belardo等研究了处理海上漏油事故的设施位置问题,此类设施的功能是当海上有漏油事故发生时,从设施处派出设备来控制事故和收集、移走泄漏到水域中的油料。Hanink研究使用投资组合理论来解决多设施选址问题。Gregg等提出了一种选择公共图书馆位置的方法,通过随机规划方法建立需求不确定条件下的选址模型。

前面讨论的模型中都包含了一系列随机参数,很多研究使用排队论的方法将这些参数包含在选址问题中。下面将讨论对这些参数进行处理的方法。

Larson的超立方体模型(hypercube model) 第一个将排队论方法应用到设施选址研究中。Larson研究了与车辆选址和紧急服务设施响应区域设计相关的问题,将跨区响应、随机到达、随机服务时间考虑在内。他把紧急服务系统看作是多服务台的排队系统来建立模型。Berman等进一步研究了在拥堵网络中的车辆选址问题。作者提出当设施处于忙状态时,需求要排队等候。需求到达设施时,若设施处于忙状态,对需求会有不同的处理方法,一种是设施忙状态时需求被放弃,一种是设施忙状态时需求排队等候。针对这两种不同的情况,作者建立了两种模型,若排队等候则遵从先进先出原则(FIFO)。两种模型都看作是M/G/1排队系统。Marianov等用M/D/<f>c</f>排队系统研究了航空网络中心的选址问题。Brandeau和Chiu着将随机排队中心问题、随机排队中值问题,以及其它一些单设施选址问题进行统一化。作者考虑了排队和运送两种原因造成的延迟,将系统看作是M/G/1排队系统。

场景规划方法在应用时,先由决策者提出几种未来可能发生的情况,称这些情况为场景(scenario),在这此场景基础上做出决策,决策目标是找出在所有场景下均能运作良好的方案。场景规划法有定性和定量两种应用方法。Mobasheri在他的研究中用场景规划方法取代了预测方法来评价未来的发展趋势和变化,这项研究以现状和将要发生的变化为基础,定性描述未来状况,使企业能够制定应对环境变化的战略。在Mulvey的研究中,通过给问题输入各种参数,使用场景规划方法定量描述一系列未来状况。设施选址中的场景规划方法采用的是定量的方法。Vanston等讨论了场景规划方法并提出了包含12个步骤的场景生成方法。Ghosh和McLafferty使用场景规划方法研究不确定环境下的零售店选址决策,目标是使零售店的市场份额最大化。Carson和Batta使用场景规划方法研究了纽约布法罗市的州立大学校园中选择救护车位置的问题。

设施选址场景规划方法的核心是找出随机情况下问题的一系列可能状况,并在这些状况基础上确定设施选址方案。设施选址场景规划的目标可以分为三类,分别是:针对所有场景进行优化;针对最坏情况的场景进行优化;使所有场景的最坏损失最小化。


相关文章推荐:
NP-complete | 需求 | 场景 |
相关词汇词典