Social Optimal Location of Facilities with Fixed Servers,Stochastic Demand,and Congestion

We consider two capacity choice scenarios for the optimal location of facilities with fixed servers, stochastic demand, and congestion. Motivating applications include virtual call centers, consisting of geographically dispersed centers, walk‐in health clinics, motor vehicle inspection stations, automobile emissions testing stations, and internal service systems. The choice of locations for such facilities influences both the travel cost and waiting times of users. In contrast to most previous research, we explicitly embed both customer travel/connection and delay costs in the objective function and solve the location–allocation problem and choose facility capacities simultaneously. The choice of capacity for a facility that is viewed as a queueing system with Poisson arrivals and exponential service times could mean choosing a service rate for the servers (Scenario 1) or choosing the number of servers (Scenario 2). We express the optimal service rate in closed form in Scenario 1 and the (asymptotically) optimal number of servers in closed form in Scenario 2. This allows us to eliminate both the number of servers and the service rates from the optimization problems, leading to tractable mixed‐integer nonlinear programs. Our computational results show that both problems can be solved efficiently using a Lagrangian relaxation optimization procedure.     

Approximating soft-capacitated facility location problem with uncertainty

In this paper we devise the stochastic and robust approaches to study the soft-capacitated facility location problem with uncertainty. We first present a new stochastic soft-capacitated model called The 2-Stage Soft Capacitated Facility Location Problem and solve it via an approximation algorithm by reducing it to linear-cost version of 2-stage facility location problem and dynamic facility location problem. We then present a novel robust model of soft-capacitated facility location, The Robust Soft Capacitated Facility Location Problem. To solve it, we improve the approximation algorithm proposed by Byrka et al. (LP-rounding algorithms for facility-location problems. CoRR, 2010a) for RFTFL and then treat it similarly as in the stochastic case. The improvement results in an approximation factor of \(\alpha + 4\) for the robust fault-tolerant facility location problem, which is best so far.     

The min-p robust optimization approach for facility location problem under uncertainty

Improper value of the parameter p in robust constraints will result in no feasible solutions while applying stochastic p-robustness optimization approach (p-SRO) to solving facility location problems under uncertainty. Aiming at finding the lowest critical p-value of parameter p and corresponding robust optimal solution, we developed a novel robust optimization approach named as min-p robust optimization approach (min-pRO) for P-median problem (PMP) and fixed cost P-median problem (FPMP). Combined with the nearest allocation strategy, the vertex substitution heuristic algorithm is improved and the influencing factors of the lowest critical p-value are analyzed. The effectiveness and performance of the proposed approach are verified by numerical examples. The results show that the fluctuation range of data is positively correlated with the lowest critical p-value with given number of new facilities. However, the number of new facilities has a different impact on lowest critical p-value with the given fluctuation range of data. As the number of new facilities increases, the lowest critical p-value for PMP and FPMP increases and decreases, respectively.

     

基于双层规划的反恐应急设施选址模型及算法

恐怖袭击常以人流密集地区的平民作为袭击目标，并存在突发性和随机性等特点，极易造成严重的袭击后果。通过反恐应急设施的合理布局可以缩短救援人员和物资的到达时间，从而减轻袭击后果。首先，对反恐应急设施选址问题进行描述，并将其构造为一类离散双层规划模型。其中，上层规划是关于政府选址的0-1规划问题，下层规划则是关于恐怖分子袭击目标选择的0-1规划问题。其次，结合模型和问题的特征设计算法，利用分支定界算法实现上层选址变量的隐枚举，同时通过下层问题的求解来确定上下界并判断是否满足分枝或剪枝的条件。最后，结合南疆地区的交通拓扑网络进行算例分析，结果证明有效的选址方案可以大大降低袭击损失。     

An approximation algorithm for stochastic multi-level facility location problem with soft capacities

Journal of Combinatorial Optimization - Facility location problem is one of the most important problems in the combinatorial optimization. The multi-level facility location problem and the facility...     

基于持续运营机会约束的竞争设施点选址研究——一种有效的实数编码遗传求解算法

竞争设施点选址是空间经济、区域发展、组合优化和系统工程的重要课题之一。本文以市场份额最大化为目标,研究了基于持续运营机会约束的竞争设施点选址问题,并给出了一种有效的实数编码遗传求解算法。在求解模型方面,首先假定运营成本是竞争设施点规模大小的函数,并对设施点持续运营概率进行机会约束,借鉴引力模型建立竞争设施点选址-设计问题的非线性混合整数规划模型。其次,考虑到选址变量和规模变量的数值类型,以及编码变换问题,设计了一种实数编码遗传求解算法。通过数值实验表明,对不同规模问题的实际计算结果,该算法可以在较短时间内获得最优解,可行解和精确解之间误差小于0.5%,相关比较分析也讨论了该算法的优越性和实用性,为竞争设施点选址问题的研究提供了不同的视角和实用求解算法。     

Optimal location and capability of oil-spill response facilities for the south coast of Newfoundland

The south coast of Newfoundland (Canada) includes both open sea and semi-enclosed waterways which collectively account for over 20,000 vessel movements annually. Every such movement poses the risk of an oil spill which can endanger the fragile marine life and tourism locales in the region, and is a source of concern to the communities. In an effort to analyze the problem, we present a two-stage stochastic programming approach which tackles both the location and stockpile of equipment at the emergency response facilities. The proposed optimization program was tested on realistic data collected from publicly available reports and through personal communications with emergency response personnel. These data were then varied to solve a number of scenarios which account for the stochastic nature of the problem parameters. Although only two response facilities seem to be appropriate for almost all scenarios, the size of equipment stockpile is a function of both the societal disutility factor and the trade-off between environmental cost and facility and equipment acquisition cost.     

Two ways to handle dependent uncertainties in multi-criteria decision problems

We consider multi-criteria group decision-making problems, where the decision makers (DMs) want to identify their most preferred alternative(s) based on uncertain or inaccurate criteria measurements. In many real-life problems the uncertainties may be dependent. In this paper, we focus on multicriteria decision-making (MCDM) problems where the criteria and their uncertainties are computed using a stochastic simulation model. The model is based on decision variables and stochastic parameters with given distributions. The simulation model determines for the criteria a joint probability distribution, which quantifies the uncertainties and their dependencies. We present and compare two methods for treating the uncertainty and dependency information within the SMAA-2 multi-criteria decision aid method. The first method applies directly the discrete sample generated by the simulation model. The second method is based on using a multivariate Gaussian distribution. We demonstrate the methods using a decision support model for a retailer operating in the deregulated European electricity market.     

DNMA: A double normalization-based multiple aggregation method for multi-expert multi-criteria decision making

This paper develops a comprehensive algorithm for multi-expert multi-criteria decision making problems considering quantitative and qualitative criteria in forms of benefit, cost or target types. We focus on using probabilistic linguistic term sets to express the qualitative evaluations due to their excellence in expressing complex individual and collective linguistic assessments. Firstly, we develop a target-based linear normalization technique and a target-based vector normalization technique. A weight adjustment method is proposed to achieve the tradeoff between criteria after normalization. Given that the two target-based normalization techniques have different advantages, we then propose a ranking method, which consists three subordinate models, based on these two target-based normalization approaches and three aggregation techniques. Reliable results of a multi-expert multi-criteria decision making problem are determined by integrating the subordinate utility values and the ranks of alternatives. The proposed method is implemented to solve the green enterprise ranking problems and the excavation scheme selection problem for shallow buried tunnels, respectively. The advantages of the proposed method are emphasized through comparative analyses with other ranking methods.     

A general space-time model for combinatorial optimization problems (and not only)

We consider the problem of defining a strategy consisting of a set of facilities taking into account also the location where they have to be assigned and the time in which they have to be activated. The facilities are evaluated with respect to a set of criteria. The plan has to be devised respecting some constraints related to different aspects of the problem such as precedence restrictions due to the nature of the facilities. Among the constraints, there are some related to the available budget. We consider also the uncertainty related to the performances of the facilities with respect to considered criteria and plurality of stakeholders participating to the decision. The considered problem can be seen as the combination of some prototypical operations research problems: knapsack problem, location problem and project scheduling. Indeed, the basic brick of our model is a variable x_ilt which takes value 1 if facility i is activated in location l at time t, and 0 otherwise. Due to the conjoint consideration of a location and a time in the decision variables, what we propose can be seen as a general space-time model for operations research problems. We discuss how such a model permits to handle complex problems using several methodologies including multiple attribute value theory and multiobjective optimization. With respect to the latter point, without any loss of the generality, we consider the compromise programming and an interactive methodology based on the Dominance-based Rough Set Approach. We illustrate the application of our model with a simple didactic example.     

A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.     

α-鲁棒随机截流选址问题的模型和算法

由于选址决策的长期性,相关参数会随着时间而变化,所以选址问题存在很多不确定因素。本文通过不同的情景来处理截流问题中流量的不确定性,并结合随机优化和鲁棒优化,提出α-鲁棒随机截流选址模型。该模型规定了在各情景下的相对后悔值不超过α的条件下,使截得的流量的期望值最大,该条件称为α-鲁棒约束。本文将该模型建立成为一个线性0-1整数规划,并给出了改进型贪婪算法和拉格朗日启发式算法。最后,本文使用这两种算法对不同规模的截流选址问题进行了研究。     

基于前景理论的多阶段随机多准则决策方法

研究一种基于动态参考点的多阶段随机多准则决策方法。考虑多阶段决策过程中决策者的风险偏好,建立了基于前景理论的多阶段随机多准则决策分析框架,提出了一种基于阶段发展特征的动态参考点设置方法;构建准则权重的目标规划模型,结合阶段参考点动态变化的特征测算各阶段备选方案的综合前景值;设计方案综合前景值的范围估算模型,以反映决策风险对评价结果的影响;案例研究验证了上述方法的可行性和实际效果。     

The Use of Flexible Manufacturing Capacity in Pharmaceutical Product Introductions*

This work considers the value of the flexibility offered by production facilities that can easily be configured to produce new products. We focus on technical uncertainty as the driver of this value, while prior works focused only on demand uncertainty. Specifically, we evaluate the use of process flexibility in the context of risky new product development in the pharmaceutical industry. Flexibility has value in this setting due to the time required to build dedicated capacity, the finite duration of patent protection, and the probability that the new product will not reach the market due to technical or regulatory reasons. Having flexible capacity generates real options, which enables firms to delay the decision about constructing product‐specific capacity until the technical uncertainty is resolved. In addition, initiating production in a flexible facility can enable the firm to optimize production processes in dedicated facilities. The stochastic dynamic optimization problem is formulated to analyze the optimal capacity and allocation decisions for a flexible facility, using data from existing literature. A solution to this problem is obtained using linear programming. The result of this analysis shows both the value of flexible capacity and the optimal capacity allocation. Due to the substantial costs involved with flexibility in this context, the optimal level of flexible capacity is relatively small, suggesting products be produced for only short periods before initiating construction of dedicated facilities.     

Managing Production and Distribution for Supply Chains in the Processed Food Industry

We develop and evaluate a modeling approach for making periodic review production and distribution decisions for a supply chain in the processed food industry. The supply chain faces several factors, including multiple products, multiple warehouses, production constraints, high transportation costs, and limited storage at the production facility. This problem is motivated by the supply chain structure at Amy's Kitchen, one of the leading producers of natural and organic foods in the United States. We develop an enhanced myopic two‐stage approach for this problem. The first stage determines the production plan and uses a heuristic, and the second stage determines the warehouse allocation plan and uses a non‐linear optimization model. This two‐stage approach is repeated every period and incorporates look‐ahead features to improve its performance in future periods. We validate our model using actual data from one factory at Amy's Kitchen and compare the performance of our model to that of the actual operation. We find that our model significantly reduces both inventory levels and stockouts relative to those of the actual operation. In addition, we identify a lower bound on the total costs for all feasible solutions to the problem and measure the effectiveness of our model against this lower bound. We perform sensitivity analysis on some key parameters and assumptions of our modeling approach.     

Heuristic Procedures for Practical-Sized Uncapacitated Location-Capacitated Routing Problems*

Facility location and vehicle routing are two important logistical problems closely interrelated in many real-world applications where locating facilities and determining the associated multi-stop vehicle routes are required simultaneously. Previous research has found that using the classical facility location models on these location-routing problems (LRPs) may lead to suboptimal solutions. We propose an approximate approach for the LRPs, which first generates and improves feasible location/allocation schemes with the associated multi-stop routing costs approximated using some route length estimators. We then design the minimum-cost routes based on the location/allocation results. We review two estimators that can provide accurate approximations to the multi-stop route distances; define the uncapacitated location-capacitated routing problem; and evaluate several heuristic procedures for approximately solving the problem. Computational results show that when vehicle capacities are not too restrictive, the sequential procedures that incorporate the two robust route length estimators can produce good solutions to practical-sized problems with a reasonable amount of computational efforts.     

基于混合蚁群算法的生产系统设施规划问题研究

设施规划问题主要研究生产设备的布局规划,从而减小厂区内的物料搬运成本。一个有效的设施规划有利于生产过程中整体运作效率的提高。随着市场竞争的日趋激烈,市场环境处于不断的变化之中,制造企业需不断对设施布局进行重新规划来适应不断变化的市场环境对产品需求量的影响,并达到降低成本的目的。这一问题便需要用多阶段设施规划（MFLP）的方法来解决。本文提出了一种改进的混和蚁群算法（HACO）来解决带有财务预算约束的多阶段设施规划问题,并将此方法与其他一些典型的启发式算法进行了对比分析。结果表明,本文提出的HACO算法是求解带有财务预算约束的MFLP问题的一种有效的方法。     

The facility location problem with Bernoulli demands

This paper presents the facility location problem with Bernoulli demands. In this capacitated discrete location stochastic problem the goal is to define an a priori solution for the locations of the facilities and for the allocation of customers to the operating facilities that minimizes the sum of the fixed costs of the open facilities plus the expected value of the recourse function. The problem is formulated as a two-stage stochastic program and two different recourse actions are considered. For each of them, a closed form is presented for the recourse function and a deterministic equivalent formulation is obtained for the case in which the probability of demand is the same for all customers. Numerical results from computational experiments are presented and analyzed.     

层次型应急设施布局模型及其应用

应急设施的特殊性决定了应急设施布局作为特殊的设施布局问题,必须更加注重及时性。应急服务的级别决定应急布局模型的考虑因素,现实中往往同时布局多个层次的应急设施,本文基于一个p-中心重心的混合模型,建立了层次型应急设施布局模型。根据应急服务的真实情况,该模型对距离的测算进行了改进,以交通网络距离代替欧氏距离。最后,将其应用于上海市上海某区的医疗设施布局。     

A method combining genetic algorithm with simultaneous perturbation stochastic approximation for linearly constrained stochastic optimization problems

This paper considers the optimization of linearly constrained stochastic problem which only noisy measurements of the loss function are available. We propose a method which combines genetic algorithm (GA) with simultaneous perturbation stochastic approximation (SPSA) to solve linearly constrained stochastic problems. The hybrid method uses GA to search for optimum over the whole feasible region, and SPSA to search for optimum at local region. During the GA and SPSA search process, the hybrid method generates new solutions according to gradient projection direction, which is calculated based on active constraints. Because the gradient projection method projects the search direction into the subspace at a tangent to the active constraints, it ensures new solutions satisfy all constraints strictly. This paper applies the hybrid method to nine typical constrained optimization problems and the results coincide with the ideal solutions cited in the references. The numerical results reveal that the hybrid method is suitable for multimodal constrained stochastic optimization problem. Moreover, each solution generated by the hybrid method satisfies all linear constraints strictly.