Efficient solution methods for covering tree problems

In recent years, interest has been shown in the optimal location of ‘extensive’ facilities in a network. Two such problems—the Maximal Direct and Indirect Covering Tree problems—were introduced by Hutson and ReVelle. Previous solution techniques are extended to provide an efficient algorithm for the Indirect Covering Tree problem and the generalization in which demand covered is attenuated by distance. It is also shown that the corresponding problem is NP-hard when the underlying network is not a tree.     

Incorporating the threat of terrorist attacks in the design of public service facility networks

In this paper, we consider the design problem of a public service facility network with existing facilities when there is a threat of possible terrorist attacks. The aim of the system planner, who is responsible for the operation of the network, is to open new facilities, relocate existing ones if necessary, and protect some of the facilities to ensure a maximum coverage of the demand that is assumed to be aggregated at customer zones. By doing so, the system planner anticipates that a number of unprotected facilities will be rendered out-of-service by terrorist attacks. It is assumed that the sum of the fixed cost of opening new facilities, the relocation costs, and the protection costs cannot exceed a predetermined budget level. Adopting the approach of gradual (or partial) coverage, we formulate a bilevel programming model where the system planner is the leader and the attacker is the follower. The objective of the former is the maximization of the total service coverage, whereas the latter wants to minimize it. We propose a heuristic solution procedure based on tabu search where the search space consists of the decisions of the system planner, and the corresponding objective value is computed by optimally solving the attacker??s problem using CPLEX. To assess the quality of the solutions produced by the tabu search (TS) heuristic, we also develop an exhaustive enumeration method, which explores all the possible combinations of opening new facilities, relocating existing ones, and protecting them. Since its time complexity is exponential, it can only be used for relatively small instances. Therefore, to be used as a benchmark method, we also implement a hill climbing procedure employed with the same type of moves as the TS heuristic. Besides, we carry out a sensitivity analysis on some of the problem parameters to investigate their effect on the solution characteristics.     

The plant location problem with demand-dependent setup costs and centralized allocation

Suppose that customers are situated at the nodes of a transportation network, and a service company plans to locate a number of facilities that will serve the customers. The objective is to minimize the sum of the total setup cost and the total transportation cost. The setup cost of a facility is demand-dependent, that is, it depends on the number of customers that are served by the facility. Centralized allocation of customers to facilities is assumed, that is, the service company makes a decision about allocation of customers to facilities. In the case of a general network, the model can be formulated as a mixed integer programming problem. For the case of a tree network, we develop a polynomial-time dynamic programming algorithm.     

Weber problems with mixed distances and regional demand

We consider a location problem where the distribution of the existing facilities is described by a probability distribution and the transportation cost is given by a combination of transportation cost in a network and continuous distance. The motivation is that in many cases transportation cost is partly given by the cost of travel in a transportation network whereas the access to the network and the travel from the exit of the network to the new facility is given by a continuous distance.      

Continuous covering and cooperative covering problems with a general decay function on networks

A cooperative covering location problem anywhere on the networks is analysed. Each facility emits a signal that decays by the distance along the arcs of the network and each node observes the total signal emitted by all facilities. A node is covered if its cumulative signal exceeds a given threshold. The cooperative approach differs from traditional covering models where the signal from the closest facility determines whether or not a point is covered. The objective is to maximize coverage by the best location of facilities anywhere on the network. The problems are formulated and analysed. Optimal algorithms for one or two facilities are proposed. Heuristic algorithms are proposed for location of more than two facilities. Extensive computational experiments are reported.     

The minmax regret gradual covering location problem on a network with incomplete information of demand weights

The gradual covering location problem seeks to establish facilities on a network so as to maximize the total demand covered, allowing partial coverage. We focus on the gradual covering location problem when the demand weights associated with nodes of the network are random variables whose probability distributions are unknown. Using only information on the range of these random variables, this study is aimed at finding the “minmax regret” location that minimizes the worst-case coverage loss. We show that under some conditions, the problem is equivalent to known location problems (e.g. the minmax regret median problem). Polynomial time algorithms are developed for the problem on a general network with linear coverage decay functions.     

A fuzzy programming approach for dynamic virtual hub location problem

Hub location problem has been used in transportation network to exploit economies of scale. For example, a controversial issue in the planning of air transportation networks is inclement weather or emergency conditions. In this situation, hub facilities would not be able to provide a good service to their spoke nodes temporarily. Thus, some other kinds of predetermined underutilized facilities in the network are used as virtual hubs to host some or all connections of original hubs to recover the incurred incapacitation and increase network flexibility and demand flow. In such an unexpected situation, it is not unreasonable to expect that some information be imprecise or vague. To deal with this issue, fuzzy concept is used to pose a more realistic problem. Here, we present a fuzzy integer liner programming approach to propose a dynamic virtual hub location problem with the aim of minimizing transportation cost in the network. We examine the effectiveness of our model using the well-known CAB data set.     

Contour line construction for a new rectangular facility in an existing layout with rectangular departments

In a recent paper, Savas et al. [S. Savas, R. Batta, R. Nagi, Finite-size facility placement in the presence of barriers to rectilinear travel, Operations Research 50 (6) (2002) 1018–1031] consider the optimal placement of a finite-sized facility in the presence of arbitrarily shaped barriers under rectilinear travel. Their model applies to a layout context, since barriers can be thought to be existing departments and the finite-sized facility can be viewed as the new department to be placed. In a layout situation, the existing and new departments are typically rectangular in shape. This is a special case of the Savas et al. paper. However the resultant optimal placement may be infeasible due to practical constraints like aisle locations, electrical connections, etc. Hence there is a need for the development of contour lines, i.e. lines of equal objective function value. With these contour lines constructed, one can place the new facility in the best manner. This paper deals with the problem of constructing contour lines in this context. This contribution can also be viewed as the finite-size extension of the contour line result of Francis [R.L. Francis, Note on the optimum location of new machines in existing plant layouts, Journal of Industrial Engineering 14 (2) (1963) 57–59].     

p-Hub approach for the optimal park-and-ride facility location problem

Park and Ride facilities (P&R) are car parks at which users can transfer to public transportation to reach their final destination. We propose a mixed linear programming formulation to determine the location of a fixed number of P&R facilities so that their usage is maximized. The facilities are modeled as hubs. Commuters can use one of the P&R facilities or choose to travel by car to their destinations, and their behavior follows a logit model. We apply a p-hub approach considering that users incur in a known generalized cost of using each P&R facility as input for the logit model. For small instances of the problem, we propose a novel linearization of the logit model, which allows transforming the binary nonlinear programming problem into a mixed linear programming formulation. A modification of the Heuristic Concentration Integer (HCI) procedure is applied to solve larger instances of the problem. Numerical experiments are performed, including a case in Queens, NY. Further research is proposed.     

考虑应急设施中断风险与防御的可靠性选址模型研究

为提高应急设施运行的可靠性和抵御中断风险的能力, 研究中断情境下的应急设施选址-分配决策问题。扩展传统无容量限制的固定费用选址模型, 从抵御设施中断的视角和提高服务质量的视角建立选址布局网络的双目标优化模型, 以应急设施的建立成本和抵御设施中断的加固成本最小为目标, 以最大化覆盖服务质量水平为目标, 在加固预算有限及最大最小容量限制约束下, 构建中断情境下应急设施的可靠性选址决策优化模型。针对所构建模型的特性利用非支配排序多目标遗传算法(NSGA-Ⅱ)求解该模型, 得到多目标的Pareto前沿解集。以不同的算例分析和验证模型和算法的可行性。在获得Pareto前沿的同时对不同中断概率进行灵敏度分析, 给出Pareto最优解集的分布及应急设施选址布局网络的拓扑结构。     

Optimal location of interconnected facilities on tree networks subject to distance constraints

Optimal location of interconnected facilities on tree networks is considered in the case when some of the nodes of the network contain existing facilities. The distances between the facilities must satisfy maximum constraints. Polynomial algorithms for the solution of this problem are proposed.     

On solving the discrete location problems when the facilities are prone to failure

The classical discrete location problem is extended here, where the candidate facilities are subject to failure. The unreliable location problem is defined by introducing the probability that a facility may become inactive. The formulation and the solution procedure have been motivated by an application to model and solve a large size problem for locating base stations in a cellular communication network. We formulate the unreliable discrete location problems as 0–1 integer programming models, and implement an enhanced dual-based solution method to determine locations of these facilities to minimize the sum of fixed cost and expected operating (transportation) cost. Computational tests of some well-known problems have shown that the heuristic is efficient and effective for solving these unreliable location problems.     

Designing multi-echelon service parts networks with finite repair capacity

We propose an approach to model and solve the joint problem of facility location, inventory allocation and capacity investment in a two echelon, single-item, service parts supply chain with stochastic demand. The objective of the decision problem is to minimize the total expected costs associated with (1) opening repair facilities, (2) assigning each field service location to an opened facility, (3) determining capacity levels of the opened repair facilities, and (4) optimizing inventory allocation among the locations. Due to the size of the problem, computational efficiency is essential. The accuracy of the approximations and effectiveness of the approach are analyzed with two numerical studies. The approach provides optimal results in 90% of scenarios tested and was within 2% of optimal when it did not.We explore the impact of capacity utilization, inventory availability, and lead times on the performance of the approach. We show that including tactical considerations jointly with strategic network design resulted in additional cost savings from 3% to 12%. Our contribution is the development of a practical model and approach to support the decision making process of joint facility location and multi-echelon inventory optimization.     

On worst-case aggregation analysis for network location problems

Network location problems occur when new facilities must be located on a network, and the network distances between new and existing facilities are important. In urban, regional, or geographic contexts, there may be hundreds of thousands (or more) of existing facilities, in which case it is common to aggregate existing facilities, e.g. represent all the existing facility locations in a zip code area by a centroid. This aggregation makes the size of the problem more manageable for data collection and data processing purposes, as well as for purposes of analysis; at the same time, it introduces errors, and results in an approximating location problem being solved. There seems to be relatively little theory for doing aggregation, or evaluating the results of aggregation; most approaches are based on experimentation or computational studies. We propose a theory that has the potential to improve the means available for doing aggregation.This research was supported in part by the National Science Foundation, Grant No. DDM-9023392.     

An Improved Lower Bound for the Multimedian Location Problem

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.     

A Branch-and-Cut Algorithm for the Median-Path Problem

The Median-Path problem consists of locating a st-path on a network, minimizing a function of two parameters: accessibility to the path and total cost of the path. Applications of this problem can be found in transportation planning, water resource management and fluid transportation. A problem formulation based on Subtour and Variable Upper Bound (VUB) inequalities was proposed in the seminal paper by (Current, Revelle and Cohon, 1989). In this paper we introduce a tighter formulation, based on a new family of valid inequalities, named Lifted Subtour inequalities, that are proved to be facet-defining. For the class of Lifted Subtour inequalities we propose a polynomial separation algorithm. Then we introduce more families of valid inequalities derived by investigating the relation to the Asymmetric Traveling Salesman Problem (ATSP) polytope and to the Stable Set polytope. These results are used to develop a Branch-and-Cut algorithm that enables us to solve to optimality small and medium size instances in less than 2 hours of CPU time on a workstation.     

A note on “quality improvement and setup reduction in the joint economic lot size model”

In a recent paper, Affisco et al. [J.F. Affisco, M.J. Paknejad, F. Nasri, Quality improvement and setup reduction in the joint economic lot size model, European Journal of Operations Research 142 (2002) 497–508] propose a quality-adjusted joint economic lot size model that considers investments in quality improvement and setup cost reduction. In particular, they consider a single-vendor, single-buyer, deterministic demand economic lot-sizing problem, and they investigate the potential impact of economic investments in the vendor’s quality improvement and setup cost reduction efforts on the system-wide costs. However, the particular form of the investment function that they use to represent the cost of investments in quality improvement does not represent actual practice in many industries. Hence, in this note, we develop modified models for quality improvement and simultaneous quality improvement and setup cost reduction using a modified form of the investment function. Our fundamental results and conclusions are substantially different than those in Affisco et al. (2002).     

Asymptotique d'un problème de positionnement optimalAsymptotic of an optimal location problem

We consider the problem of optimal location of production centres to serve a non-uniform distribution of customers. The location is required to be optimal with respect to the cost of transportation which is modeled by a weighted average of the distance function to the nearest production centre. In this Note we study the asymptotic behaviour of the problem as the number of production centres increases. This is done in connection with the theory of Monge–Kantorovich for mass transportation. To cite this article: G. Bouchitté et al., C. R. Acad. Sci. Paris, Ser. I 335 (2002) 853–858.     

A primal–dual simplex algorithm for bi-objective network flow problems

In this paper we develop a primal–dual simplex algorithm for the bi-objective linear minimum cost network flow problem. This algorithm improves the general primal–dual simplex algorithm for multi-objective linear programs by Ehrgott et al. (J Optim Theory Appl 134:483–497, 2007). We illustrate the algorithm with an example and provide numerical results.     

Sensitivity analysis of permeability parameters for flows on Barcelona networks

We consider the problem of optimizing vehicular traffic flows on an urban network of Barcelona type, i.e. square network with streets of not equal length. In particular, we describe the effects of variation of permeability parameters, that indicate the amount of flow allowed to enter a junction from incoming roads.On each road, a model suggested by Helbing et al. (2007) [11] is considered: free and congested regimes are distinguished, characterized by an arrival flow and a departure flow, the latter depending on a permeability parameter. Moreover we provide a rigorous derivation of the model from fluid dynamic ones, using recent results of Bretti et al. (2006) [3]. For solving the dynamics at nodes of the network, a Riemann solver maximizing the through flux is used, see Coclite et al. (2005) [4] and Helbing et al. (2007) [11].The network dynamics gives rise to complicate equations, where the evolution of fluxes at a single node may involve time-delayed terms from all other nodes. Thus we propose an alternative hybrid approach, introducing additional logic variables. Finally we compute the effects of variations on permeability parameters over the hybrid dynamics and test the obtained results via simulations.