随机容错设施布局问题的近似算法

在确定性的容错设施布局问题中, 给定顾客的集合和地址的集合. 在每个地址上可以开设任意数目的不同设施. 每个顾客j有连接需求r_j. 允许将顾客j连到同一地址的不同设施上. 目标是开设一些设施并将每个顾客j连到r_j个不同的设施上, 使得总开设费用和连接费用最小. 研究两阶段随机容错设施布局问题(SFTFP), 顾客的集合事先不知道, 但是具有有限多个场景并知道其概率分布. 每个场景指定需要服务的顾客的子集. 并且每个设施有两种类型的开设费用. 在第一阶段根据顾客的随机信息确定性地开设一些设施, 在第二阶段根据顾客的真实信息再增加开设一些设施．给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.     

带次模惩罚的优先设施选址问题的近似算法

研究带次模惩罚的优先设施选址问题, 每个顾客都有一定的服务水平要求, 开设的设施只有满足了顾客的服务水平要求, 才能为顾客提供服务, 没被服务的顾客对应一定的次模惩罚费用. 目标是使得开设费用、连接费用与次模惩罚费用之和最小. 给出该问题的整数规划、 线性规划松弛及其对偶规划. 基于原始对偶和贪婪增广技巧, 给出该问题的两个近似算法, 得到的近似比分别为3和2.375.     

随机容错设施选址问题的原始-对偶近似算法

研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现（在第一阶段不知道）．两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合（称为场景）．并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务．给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小．根据问题的特定结构,给出了原始。对偶（组合）3-近似算法．     

带次模惩罚和随机需求的设施选址问题

考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构,给出原始对偶3-近似算法. 在算法的第一步,构造了一组对偶可行解;在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.     

带有异常点的平方度量设施选址问题

传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用（设施的开设费用与连接费用之和）,也会影响到对其他顾客的服务质量。研究异常点在最终方案中允许不被服务的情况,称之为带有异常点的平方度量设施选址问题。该问题是无容量设施选址问题的推广。问题可描述如下：给定设施集合、顾客集,以及设施开设费用和顾客连接费用,目标是选择设施的子集开设以满足顾客的需求,使得设施开设费用与连接费用之和最小。利用原始对偶技巧设计了近似算法,证明了该算法的近似比是9。     

带惩罚的动态设施选址问题的近似算法

本文研究带惩罚的动态设施选址问题,在该问题中假设不同时段内设施的开放费用、用户的需求及连接费用可以不相同,而且允许用户的需求不被满足,但是要有惩罚.对此问题我们给出了第-个近似比为1.8526的原始对偶(组合)算法.     

鲁棒动态设施选址问题的近似算法

设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务 (带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的 (带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。     

平方度量的k层设施选址问题的近似算法

本文中,我们研究平方度量的k层设施选址问题,该问题中设施分为k层,每个顾客都要连接到位于不同层上的k个设施,顾客与设施以及设施与设施之间的距离是平方度量的.目标是使得开设费用与连接费用之和最小.基于线性规划舍入技巧,我们给出了9-近似算法.进一步,我们研究了平方度量的k层软容量设施选址问题,并给出了线性规划舍入12.2216-近似算法.     

带次模惩罚的仓库—零售商网络设计问题的近似算法

本文研究了一个带次模惩罚的仓库—零售商网络设计问题.在该类问题中,允许以支付惩罚费用为代价,拒绝给部分零售商供货,并且我们假设问题的惩罚费用函数是一个不减的非负次模函数.对于此问题,我们给出一个近似比为3的原始对偶算法.     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.     

带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法

$k$-种产品设施选址问题是指存在一组客户和一组可以建设设施的地址。现有$k$种不同的产品,每一客户均需要$k$种不同的产品,且每一设施最多只能生产一种产品。问题的要求是从若干地址中选择一组地址来建立设施,对所要建立的设施指定其生产的产品,并为每一个客户提供一组指派确保每一客户都有$k$个设施来为其提供$k$种不同的产品,使得设施建设费用与运输费用之和最小。对于$k$-种产品设施选址问题,我们通常简写为$k$-PUFLP,其中,当所有设施建设费用为0时,记为$k$-PUFLPN。本文对$k$-PUFLPN进行线性舍入,通过分析最优分数解特殊结构,当$k\geq 3$时分析算法将$k$-PUFLPN的近似比从$\frac{3k}{2}-1$提升到了$\frac{3k}{2}-\frac{3}{2}$。鲁棒$k$-种产品设施选址问题是指在该问题中,最多有$q$个客户可以不被服务。我们首次对无容量限制下建设费用为0时的鲁棒$k$-种产品选址问题建立模型,当$k\geq 3$,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。对顾客伴有线性惩罚的鲁棒$k$-种产品设施选址问题,本文同时考虑异常值与惩罚性,利用$k$-PUFLPN中最优整数解与最优分数解的关系,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。     

A facility location model with safety stock costs: analysis of the cost of single-sourcing requirements

We consider a supply chain setting where multiple uncapacitated facilities serve a set of customers with a single product. The majority of literature on such problems requires assigning all of any given customer??s demand to a single facility. While this single-sourcing strategy is optimal under linear (or concave) cost structures, it will often be suboptimal under the nonlinear costs that arise in the presence of safety stock costs. Our primary goal is to characterize the incremental costs that result from a single-sourcing strategy. We propose a general model that uses a cardinality constraint on the number of supply facilities that may serve a customer. The result is a complex mixed-integer nonlinear programming problem. We provide a generalized Benders decomposition algorithm for the case in which a customer??s demand may be split among an arbitrary number of supply facilities. The Benders subproblem takes the form of an uncapacitated, nonlinear transportation problem, a relevant and interesting problem in its own right. We provide analysis and insight on this subproblem, which allows us to devise a hybrid algorithm based on an outer approximation of this subproblem to accelerate the generalized Benders decomposition algorithm. We also provide computational results for the general model that permit characterizing the costs that arise from a single-sourcing strategy.     

Supply capacity acquisition and allocation with uncertain customer demands

We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver.     

The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation

We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.     

An Iterated Local Search for the Budget Constrained Generalized Maximal Covering Location Problem

Capacitated covering models aim at covering the maximum amount of customers’ demand using a set of capacitated facilities. Based on the assumptions made in such models, there is a unique scenario to open a facility in which each facility has a pre-specified capacity and an operating budget. In this paper, we propose a generalization of the maximal covering location problem, in which facilities have different scenarios for being constructed. Essentially, based on the budget invested to construct a given facility, it can provide different service levels to the surrounded customers. Having a limited budget to open the facilities, the goal is locating a subset of facilities with the optimal opening scenario, in order to maximize the total covered demand and subject to the service level constraint. Integer linear programming formulations are proposed and tested using ILOG CPLEX. An iterated local search algorithm is also developed to solve the introduced problem.     

The \alpha -cost minimization model for capacitated facility location-allocation problem with uncertain demands

Facility location-allocation problem aims at determining the locations of some facilities to serve a set of spatially distributed customers and the allocation of each customer to the facilities such that the total transportation cost is minimized. In real life, the facility location-allocation problem often comes with uncertainty for lack of the information about the customers’ demands. Within the framework of uncertainty theory, this paper proposes an uncertain facility location-allocation model by means of chance-constraints, in which the customers’ demands are assumed to be uncertain variables. An equivalent crisp model is obtained via the \(\alpha \) -optimistic criterion of the total transportation cost. Besides, a hybrid intelligent algorithm is designed to solve the uncertain facility location-allocation problem, and its viability and effectiveness are illustrated by a numerical example.