基于P-中位模型的网络关键设施识别问题的算法设计与实现

在网络服务系统中,存在由于各种人为因素(恐怖行为、黑客袭击等)导致网络设施服务中断的情况.为抵御有预谋的攻击,需要更加重视如何识别网络系统中的关键设施.结合P-中位选址模型,以设施失效对网络系统运行效率影响最大化为目标,给出针对基于P-中位模型的网络关键设施识别问题(即R-中断模型),并针对该模型提出贪婪搜索、邻域搜索和禁忌搜索3种算法.结合Galvo、Europe 150 和USA 263 等大型的测试实例,对上述算法进行比较分析,得出禁忌搜索算法最有效的结论.最后,结合Europe 150 数据的例子比较了P-中位问题与R-中断问题,认为在选址决策中事先考虑到人为攻击导致的中断问题可以增加网络的抗攻击能力,减少损失.     

Facility Location: A Robust Optimization Approach

In this research, we apply robust optimization (RO) to the problem of locating facilities in a network facing uncertain demand over multiple periods. We consider a multi‐period fixed‐charge network location problem for which we find (1) the number of facilities, their location and capacities, (2) the production in each period, and (3) allocation of demand to facilities. Using the RO approach we formulate the problem to include alternate levels of uncertainty over the periods. We consider two models of demand uncertainty: demand within a bounded and symmetric multi‐dimensional box, and demand within a multi‐dimensional ellipsoid. We evaluate the potential benefits of applying the RO approach in our setting using an extensive numerical study. We show that the alternate models of uncertainty lead to very different solution network topologies, with the model with box uncertainty set opening fewer, larger facilities. Through sample path testing, we show that both the box and ellipsoidal uncertainty cases can provide small but significant improvements over the solution to the problem when demand is deterministic and set at its nominal value. For changes in several environmental parameters, we explore the effects on the solution performance.     

Distributionally robust maximum probability shortest path problem

In this study, we discuss and develop a distributionally robust joint chance-constrained optimization model and apply it for the shortest path problem under resource uncertainty. In sch a case, robust chance constraints are approximated by constraints that can be reformulated using convex programming. Since the issue we are discussing here is of the multi-resource type, the resource related to cost is deterministic; however, we consider a robust set for other resources where covariance and mean are known. Thus, the chance-constrained problem can be expressed in terms of a cone constraint. In addition, since our problem is joint chance-constrained optimization, we can use Bonferroni approximation to divide the problem into L separate problems in order to build convex approximations of distributionally robust joint chance constraints. Finally, numerical results are presented to illustrate the rigidity of the bounds and the value of the distributionally robust approach.

     

设施失灵风险下不确定需求应急定位-路径鲁棒优化研究

为抵御突发灾害对路网造成的破坏性和设施失灵风险,降低系统成本,并快速完成应急救援任务,本文考虑到受灾点物资需求量的不确定和风险对救援系统的影响,采用直升机进行物资运送以规避路径风险。建立了最小化应急物流系统总成本和物资到达需求点总救援时间为双目标的应急物流定位-路径鲁棒优化模型,基于相对鲁棒优化方法处理需求不确定,采用偏差鲁棒优化思想描述设施失灵风险损失,采用遗传算法进行求解。通过对三个算例进行数据仿真实验,证明了相对鲁棒优化方法在处理需求不确定和偏差鲁棒优化方法在处理设施失灵风险方面的有效性,进而为解决应急设施点的开设和救援物资的安全及时准确配送,增强应急物流系统的风险应对能力提供了有效的方法。     

Critical objective function values in linear sum assignment problems

The linear sum assignment problem has been well studied in combinatorial optimization. Because of the integrality property, it is a linear programming problem with a variety of efficient algorithms to solve it. In the given research, we present a reformulation of the linear sum assignment problem and a Lagrangian relaxation algorithm for its reformulation. An important characteristic of the new Lagrangian relaxation method is that the optimal Lagrangian multiplier yields a critical bottleneck value. Lagrangian relaxation has only one Lagrangian multiplier, which can only take on a limited number of values, making the search for the optimal multiplier easy. The interpretation of the optimal Lagrangian parameter is that its value is equal to the price that must be paid for all objects in the problem to be assigned.     

A robust approach to the share-of-choice product design problem

A critical issue when solving the share-of-choice product design problem is the reliability of the optimal solution in the presence of partworth uncertainty. Existing approaches use point estimates of an individual's partworth utilities as input to the product optimization stage, ignoring within-person variability in estimates. Post-optimality sensitivity analysis is occasionally performed to assess the degree to which a solution is negatively impacted by partworth uncertainty. We propose a robust optimization model that explicitly captures variation in partworth estimates during the optimization process. Using a large, commercial dataset, we benchmark our model's performance against its deterministic counterpart. We also present inferential theory to guide the selection of model parameters controlled by the analyst. Results reveal that the new approach produces robust solutions in the face of measurement error. Out-of-sample coverage for individuals drawn from the target population is significantly higher than corresponding solutions from published methods.     

A Data‐Driven Inventory Control Policy for Cash Logistics Operations: An Exploratory Case Study Application at a Financial Institution

A number of market changes are impacting the way financial institutions are managing their automated teller machines (ATMs). We propose a new class of adaptive data‐driven policies for a stochastic inventory control problem faced by a large financial institution that manages cash at several ATMs. Senior management were concerned that their current cash supply system to manage ATMs was inefficient and outdated, and suspected that using improved cash management could reduce overall system cost. Our task was to provide a robust procedure to tackle the ATM's cash deployment strategies. Current industry practice uses a periodic review system with infrequent parameter updates for cash management based on the assumption that demand is normally distributed during the review period. This assumption did not hold during our investigation, warranting a new and robust analysis. Moreover, we discovered that forecast errors are often not normally distributed and that these error distributions change dramatically over time. Our approach finds the optimal time series forecaster and the best‐fitting weekly forecast error distribution. The guaranteed optimal target cash inventory level and time between orders could only be obtained through an optimization module that was embedded in a simulation routine that we built for the institution. We employed an exploratory case study methodology to collect cash withdrawal data at 21 ATMs owned and operated by the financial institution. Our new approach shows a 4.6% overall cost reduction. This reflects an annual cost savings of over $250,000 for the 2,500 ATM units that are operated by the bank.     

On the location of new facilities for chain expansion under delivered pricing

We study the problem of locating new facilities for one expanding chain which competes for demand in spatially separated markets where all competing chains use delivered pricing. A new network location model is formulated for profit maximization of the expanding chain assuming that equilibrium prices are set in each market. The cannibalization effect caused by the entrance of the new facilities is integrated in the objective function as a cost to be paid by the expanding chain to the cannibalized facilities. It is shown that the profit of the chain is maximized by locating the new facilities in a set of points which are nodes or iso-marginal delivered cost points (points on the network from which the marginal delivered cost equals the minimum marginal delivered cost from the existing facilities owned by the expanding chain). Then the location problem is reduced to a discrete optimization problem which is formulated as a mixed integer linear program. A sensitivity analysis respect to both the number of new facilities and the cannibalization cost is shown by using an illustrative example with data of the region of Murcia (Spain). Some conclusions are presented.     

基于非概率可靠性的铁路应急设施选址-路径鲁棒优化

鉴于铁路应急设施选址研究中很难合理估计参数的概率分布或确定其隶属函数的问题,将选址-路径问题与区间非概率可靠性方法结合起来,以复杂网络理论为基础,提出网络节点区间权重的确定方法,同时考虑节点权重、边权及径权区间不确定性的共同作用,构建铁路应急设施选址节点加权网络。基于区间非概率可靠性理论及区间运算规则,提出路径的非概率可靠性度量及最优时间可靠度路径选择方法,建立节点权重、边权及径权均为区间数的非概率可靠性铁路应急设施选址-路径鲁棒优化模型,并给出了求解算法,确定了基于区间模型的铁路应急设施鲁棒选址的最优方案。算例表明,本文的优化方案能更好地保证救援的时间鲁棒性,能有效地规避不确定因素波动对设施选址的长期风险,具有很好的实际应用价值。     

Lot sizing with storage losses under demand uncertainty

We address a variant of the single item lot sizing problem affected by proportional storage (or inventory) losses and uncertainty in the product demand. The problem has applications in, among others, the energy sector, where storage losses (or storage deteriorations) are often unavoidable and, due to the need for planning ahead, the demands can be largely uncertain. We first propose a two-stage robust optimization approach with second-stage storage variables, showing how the arising robust problem can be solved as an instance of the deterministic one. We then consider a two-stage approach where not only the storage but also the production variables are determined in the second stage. After showing that, in the general case, solutions to this problem can suffer from acausality (or anticipativity), we introduce a flexible affine rule approach which, albeit restricting the solution set, allows for causal production plans. A hybrid robust-stochastic approach where the objective function is optimized in expectation, as opposed to in the worst-case, while retaining robust optimization guarantees of feasibility in the worst-case, is also discussed. We conclude with an application to heat production, in the context of which we compare the different approaches via computational experiments on real-world data.     

交叉销售下基于支持向量聚类的数据驱动多产品库存鲁棒优化模型

针对单周期环境下考虑交叉销售的多产品库存决策问题,在市场需求不确定条件下,建立了带有预算约束的交叉销售多产品库存鲁棒优化模型。针对不确定市场需求,采用支持向量聚类(SVC)方法构建了满足一定置信水平的数据驱动不确定集。进一步,运用拉格朗日对偶方法将所建模型等价转化为易于求解的线性规划问题。最后,通过数值计算对比分析了SVC不确定集下及传统不确定集下的零售商利润绩效,并评估了SVC数据驱动鲁棒优化方法导致的绩效损失,进而分析了预算及交叉销售系数对零售商利润绩效的影响。结果表明,SVC数据驱动鲁棒优化方法具有良好的鲁棒性,能够有效抑制需求不确定性对从事多产品销售的零售商利润绩效的影响。特别地,需求分布信息的缺失虽然会给零售商带来一定的绩效损失,但损失值很小,表明文中提出的基于SVC的数据驱动鲁棒优化方法可以为管理者在需求不确定性环境下制定库存策略提供有效决策借鉴。     

基于煤矿透水事故应急响应时效性的水泵布局鲁棒优选问题研究

为了提高煤矿透水事故中矿工获救和恢复健康的可能性，本文基于应急响应时效性研究关键资源-水泵布局问题。已有应急资源布局问题的研究多从成本、时间、资源需求满足度等方面进行，煤矿透水事故应急响应时效性是综合考虑被困矿工获救时间以及被困过程中被困位置最低氧气含量和食物缺少量三方面要素的事故应对效果。首先，建立了基于煤矿透水事故发生、发展和应急响应机理的三方面要素计算方法；然后，在供氧和供食物所需资源布局给定的前提下，设计水泵布局的目标函数和约束条件，建立水泵布局鲁棒优选模型，通过机会时间窗概念的引入和分支定界算法的思想，给出水泵布局不可行方案的判别准则，并在此基础上进行优选算法的设计；最后，在实际发生的煤矿透水事故典型案例基础上，构造算例，检验水泵布局鲁棒优选模型的有效性。     

A joint optimal pricing and order quantity model under parameter uncertainty and its practical implementation

We consider a robust optimization model of determining a joint optimal bundle of price and order quantity for a retailer in a two-stage supply chain under uncertainty of parameters in demand and purchase cost functions. Demand is modeled as a decreasing power function of product price, and unit purchase cost is modeled as a decreasing power function of order quantity and demand. While the general form of the power functions are given, it is assumed that parameters defining the two power functions involve a certain degree of uncertainty and their possible values can be characterized by ellipsoids. We show that the robust optimization problem can be transformed into an equivalent convex optimization which can be solved efficiently and effectively using interior-point methods. In addition, we propose a practical implementation of the model, where the stochastic characteristics of parameters are obtained from regression analysis on past sales and production data, and ellipsoidal representations of the parameter uncertainties are obtained based on a combined use of genetic algorithm and Monte Carlo simulation. An illustrative example is provided to demonstrate the model and its implementation.     

A joint optimal pricing and order quantity model under parameter uncertainty and its practical implementation

We consider a robust optimization model of determining a joint optimal bundle of price and order quantity for a retailer in a two-stage supply chain under uncertainty of parameters in demand and purchase cost functions. Demand is modeled as a decreasing power function of product price, and unit purchase cost is modeled as a decreasing power function of order quantity and demand. While the general form of the power functions are given, it is assumed that parameters defining the two power functions involve a certain degree of uncertainty and their possible values can be characterized by ellipsoids. We show that the robust optimization problem can be transformed into an equivalent convex optimization which can be solved efficiently and effectively using interior-point methods. In addition, we propose a practical implementation of the model, where the stochastic characteristics of parameters are obtained from regression analysis on past sales and production data, and ellipsoidal representations of the parameter uncertainties are obtained based on a combined use of genetic algorithm and Monte Carlo simulation. An illustrative example is provided to demonstrate the model and its implementation.     

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.     

具有遗憾值约束的鲁棒供应链网络设计模型研究

考虑不确定性环境,研究战略层次的供应链网络鲁棒设计问题,目标是设计参数发生摄动时,供应链性能能够保持稳健性。基于鲁棒解的定义,建立从上游供应商选择到下游设施选址-需求分配的供应链网络设计鲁棒优化模型;提出确定遗憾值限定系数上限和下限的方法,允许决策者调节鲁棒水平,选择多种供应链网络结构;通过模型分解与协调,设计了供应链节点配置的禁忌搜索算法。算例的计算结果表明了禁忌搜索算法具有良好的收敛特性,以及在处理大规模问题上的优越性;同时也反映了利用鲁棒优化模型进行供应链网络设计,可以有效规避投资风险。     

The Steiner cycle and path cover problem on interval graphs

The Steiner path problem is a common generalization of the Steiner tree and the Hamiltonian path problem, in which we have to decide if for a given graph there exists a path visiting a fixed set of terminals. In the Steiner cycle problem we look for a cycle visiting all terminals instead of a path. The Steiner path cover problem is an optimization variant of the Steiner path problem generalizing the path cover problem, in which one has to cover all terminals with a minimum number of paths. We study those problems for the special class of interval graphs. We present linear time algorithms for both the Steiner path cover problem and the Steiner cycle problem on interval graphs given as endpoint sorted lists. The main contribution is a lemma showing that backward steps to non-Steiner intervals are never necessary. Furthermore, we show how to integrate this modification to the deferred-query technique of Chang et al. to obtain the linear running times.

     

Modified differential evolution with self-adaptive parameters method

The differential evolution algorithm (DE) is a simple and effective global optimization algorithm. It has been successfully applied to solve a wide range of real-world optimization problem. In this paper, the proposed algorithm uses two mutation rules based on the rand and best individuals among the entire population. In order to balance the exploitation and exploration of the algorithm, two new rules are combined through a probability rule. Then, self-adaptive parameter setting is introduced as uniformly random numbers to enhance the diversity of the population based on the relative success number of the proposed two new parameters in a previous period. In other aspects, our algorithm has a very simple structure and thus it is easy to implement. To verify the performance of MDE, 16 benchmark functions chosen from literature are employed. The results show that the proposed MDE algorithm clearly outperforms the standard differential evolution algorithm with six different parameter settings. Compared with some evolution algorithms (ODE, OXDE, SaDE, JADE, jDE, CoDE, CLPSO, CMA-ES, GL-25, AFEP, MSAEP and ENAEP) from literature, experimental results indicate that the proposed algorithm performs better than, or at least comparable to state-of-the-art approaches from literature when considering the quality of the solution obtained.     

Risk based facility location by using fault tree analysis in disaster management

Determining the locations of facilities for prepositioning supplies to be used during a disaster is a strategic decision that directly affects the success of disaster response operations. Locating such facilities close to the disaster-prone areas is of utmost importance to minimize response time. However, this is also risky because the facility may be disrupted and hence may not support the demand point(s). In this study, we develop an optimization model that minimizes the risk that a demand point may be exposed to because it is not supported by the located facilities. The purpose is to choose the locations such that a reliable facility network to support the demand points is constructed. The risk for a demand point is calculated as the multiplication of the (probability of the) threat (e.g., earthquake), the vulnerability of the demand point (the probability that it is not supported by the facilities), and consequence (value or possible loss at the demand point due to threat). The vulnerability of a demand point is computed by using fault tree analysis and incorporated into the optimization model innovatively. To our knowledge, this paper is the first to use such an approach. The resulting non-linear integer program is linearized and solved as a linear integer program. The locations produced by the proposed model are compared to those produced by the p-center model with respect to risk value, coverage distance, and covered population by using several test problems. The model is also applied in a real problem. The results indicate that taking the risk into account explicitly may create significant differences in the risk levels.     

Quantitative Comparison of Approximate Solution Sets for Bi‐criteria Optimization Problems*

We present the Integrated Preference Functional (IPF) for comparing the quality of proposed sets of near‐pareto‐optimal solutions to bi‐criteria optimization problems. Evaluating the quality of such solution sets is one of the key issues in developing and comparing heuristics for multiple objective combinatorial optimization problems. The IPF is a set functional that, given a weight density function provided by a decision maker and a discrete set of solutions for a particular problem, assigns a numerical value to that solution set. This value can be used to compare the quality of different sets of solutions, and therefore provides a robust, quantitative approach for comparing different heuristic, a posteriori solution procedures for difficult multiple objective optimization problems. We provide specific examples of decision maker preference functions and illustrate the calculation of the resulting IPF for specific solution sets and a simple family of combined objectives.