Improved Adaptive Differential Evolution Algorithm for the Un-Capacitated Facility Location Problem

The differential evolution algorithm is an evolutionary algorithm for global optimization and the un-capacitated facility location problem (UFL) is one of the classic NP-Hard problems. In this paper, combined with the specific characteristics of the UFL problem, we introduce the activation function to the algorithm for solving UFL problem and name it improved adaptive differential evolution algorithm (IADEA). Next, to improve the efficiency of the algorithm and to alleviate the problem of being stuck in a local optimum, an adaptive operator was added. To test the improvement of our algorithm, we compare the IADEA with the basic differential evolution algorithm by solving typical instances of UFL problem respectively. Moreover, to compare with other heuristic algorithm, we use the hybrid ant colony algorithm to solve the same instances. The computational results show that IADEA improves the performance of the basic DE and it outperforms the hybrid ant colony algorithm.

Approximation Algorithms for the Priority Facility Location Problem with Penalties

develop a mentation This paper considers the priority facility primal-dual 3-approximation algorithm for procedure, the authors further improve the location problem with penalties： The authors this problem. Combining with the greedy aug- previous ratio 3 to 1.8526.

Strategyproof Facility Location with Limited Locations

We study the mechanism design of facility location problems.The problem is to design mechanisms to select a set of locations on which to build a set of facilities,aiming to optimize some system objective and achieve desirable properties based on the strategic agents'locations.The agents might have incentives to misreport their private locations,in order to minimize the costs(i.e.,the distance from the closest facility).We study the setting with limited locations,that is,the facilities can only be built on a given finite set of candidate locations,rather than the whole space.For locating a single facility and two facilities on a real line,we propose strategyproof mechanisms with tight approximation ratios,under the objectives of minimizing the total cost and the maximum cost.Further,we consider the problem of locating an obnoxious facility from which the agents want to stay as far away as possible,and derive tight bounds on the approximation ratio of strategyproof mechanisms.

Emergency response facility location in transportation networks: A literature review

Emergency response activity relies on transportation networks. Emergency facility location interacts with transportation networks clearly. This review is aimed to provide a combined framework for emergency facility location in transportation networks. The article reveals emergency response activities research clusters, issues, and objectives according to keywords co-occurrence analysis. Four classes of spatial separation models in transportation networks, including distance, routing, accessibility, and travel time are introduced. The stochastic and time-dependent characteristics of travel time are described. Travel time estimation and prediction method, travel time under emergency vehicle preemption,transportation network equilibrium method, and travel time in degradable networks are demonstrated. The emergency facilities location models interact with transportation networks, involving location-routing model, location models embedded with accessibility,location models embedded with travel time, and location models employing mathematical program with equilibrium constraints are reviewed. We then point out the-state-of-art challenges: ilities-oriented, evolution landscape and sequential decision modelling, datadriven optimization approach, and machine learning-based algorithms.

On Constrained Facility Location Problems

Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The κ-Facility Location problem further requires that the number of opened facilities is at most κ, where κ is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant ε 〉 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 ＋ √ω ＋ ε, which significantly improves the previous best known ratio （ω ＋ 1）/α for some 1 ≤ α ≤2, and a polynomial-time approximation algorithm for the ω-constrained κ- Facility Location problem with approximation ratio ω ＋ 1 ＋ ε. On the aspect of approximation hardness, we prove that unless NP C DTIME（n^O（log log n））, the ω-constrained Facility Location problem cannot be approximated within 1 ＋ln √ω 1, which slightly improves the previous best known hardness result 1.243 ＋ 0.316 ln（ω - 1）. The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.

Soft-capacitated Facility Location Game

We study the soft-capacitated facility location game which is an extension of the facility location game of Pa1 and Tardos. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that the method is effective.

A Cost-Sharing Scheme for the k-Level Facility Location Game with Penalties

In the k-level facility location problem with penalties,each client will be either serviced or rejected completely.And if the client is planned to be serviced,then it must be connected to a sequence of k different kinds of facilities located in k levels of hierarchy.The total cost including the facility cost,connection cost and penalty cost will be jointly paid by all the clients.In the corresponding game of the k-level facility location problem with penalties,called the k-level facility location game with penalties,the total cost should be allocated to different clients.This work set out a cost-sharing scheme for the k-level facility location game with penalties that is cross-monotonic,competitive,and the approximate cost recovery is 6.

An Improved Approximation Algorithm for the k-Level Facility Location Problem with Soft Capacities

We consider the k-level facility location problem with soft capacities （k-LFLPSC）. In the k- LFLPSC, each facility i has a soft capacity ui along with an initial opening cost fi ≥O, i.e., the capacity of facility i is an integer multiple of ui incurring a cost equals to the corresponding multiple of fi. We firstly propose a new bifactor （ln（1/β）/（1 -β）, 1 ＋ 2/（1 - β））-approximation algorithm for the k-level facility location problem （k-LFLP）, where β∈（0, 1） is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.

An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties

In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.

An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties

In this paper,we consider the risk-adjusted two-stage stochastic facility location problem with penalties(RSFLPP).Using the monotonicity and positive homogeneity of the risk measure function,we present an LP-rounding-based 6-approximation algorithm.

Fault-tolerant Concave Facility Location Problem with Uniform Requirements

In this paper, we consider the fault-tolerant concave facility location problem （FTCFL） with uniform requirements. By investigating the structure of the FTCFL, we obtain a modified dual-fitting bifactor approximation algorithm. Combining the scaling and greedy argumentation technique, the approximation factor is proved to be 1.52.

An Approximation Algorithm for the Stochastic Fault-Tolerant Facility Location Problem

In this paper,we study a stochastic version of the fault-tolerant facility location problem.By exploiting the stochastic structure,we propose a 5-approximation algorithm which uses the LP-rounding technique based on the revised optimal solution to the linear programming relaxation of the stochastic fault-tolerant facility location problem.

Optimum Location of Field Hospitals for COVID-19: A Nonlinear Binary Metaheuristic Algorithm

Determining the optimum location of facilities is critical in many fields,particularly in healthcare.This study proposes the application of a suitable location model for field hospitals during the novel coronavirus 2019(COVID-19)pandemic.The used model is the most appropriate among the three most common location models utilized to solve healthcare problems(the set covering model,the maximal covering model,and the P-median model).The proposed nonlinear binary constrained model is a slight modification of the maximal covering model with a set of nonlinear constraints.The model is used to determine the optimum location of field hospitals for COVID-19 risk reduction.The designed mathematical model and the solution method are used to deploy field hospitals in eight governorates in Upper Egypt.In this case study,a discrete binary gaining–sharing knowledge-based optimization(DBGSK)algorithm is proposed.The DBGSK algorithm is based on how humans acquire and share knowledge throughout their life.The DBGSK algorithm mainly depends on two junior and senior binary stages.These two stages enable DBGSK to explore and exploit the search space efficiently and effectively,and thus it can solve problems in binary space.

Method to Evaluate the Location of Aged Care Facilitiesin Urban Areas Focusing on the Equity in Terms ofUsers’Accessibility

The present study developed and tested a method to evaluate the location of aged care facilities from the viewpoint of whether they are equitably located for users,using the improved Median Share Ratio(MSR).By evaluating the current location of aged care facilities,it is possible to extract the districts which are short of facilities.The evaluation method was applied to Chofu and Kiyose Cities in Tokyo Metropolis,Japan,and the evaluation result of weighting and that of not weighting by elderly population were compared and discussed.Consequently,adopting the evaluation method with weighting by elderly population,it is possible to adequately examine the districts where new aged care facilities should be constructed.From this evidence,it is significant to evaluate the location of aged care facilities,using the improved MSR with weighting by elderly population in the study.

An Algorithm for Solving Generalized Single Row Facility Layout Problem

Layout design problem is to determine a suitable arrangement for the departments so that the total costs associated with the flow among departments become least. Single Row Facility Layout Problem, SRFLP, is one of the layout problems that have many practical applications. This problem and its specific scenarios are often used to model many of the raised issues in the field of facility location. SRFLP is an arrangement of n departments with a specified length in a straight line so that the sum of the weighted distances between the pairs of departments is minimized. This problem is NP-hard. In this paper, first, a lower bound for a special case of SRFLP is presented. Then, a general case of SRFLP is presented in which some new and real assumptions are added to generate more practical model. Then a lower bound, as well as an algorithm, is proposed for solving the model. Experimental results on some instances in literature show the efficiency of our algorithm.

The Coupled Operational Systems:A Linear Optimisation Review

The purpose of this review is to summarise the existing literature on the operational systems as to explain the current state of understanding on the coupled operational systems.The review only considers the linear optimisation of the operational systems.Traditionally,the operational systems are classified as decoupled,tightly coupled,and loosely coupled.Lately,the coupled operational systems were classified as systems of time-sensitive and time-insensitive operational cycle,systems employing one mix and different mixes of factors of production,and systems of single-linear,single-linear-fractional,and multi-linear objective.These new classifications extend the knowledge about the linear optimisation of the coupled operational systems and reveal new objective-improving models and new state-of-the-art methodologies never discussed before.Business areas affected by these extensions include product assembly lines,cooperative farming,gas/oil reservoir development,maintenance service throughout multiple facilities,construction via different locations,flights traffic control in aviation,game reserves,and tramp shipping in maritime cargo transport.

Greedy Randomized Adaptive Search Procedure with Path-Relinking for the Vertex p-Center Problem

The p-center problem consists of choosing a subset of vertices in an undirected graph as facilities in order to minimize the maximum distance between a client and its closest facility. This paper presents a greedy randomized adaptive search procedure with path-relinking （GRASP/PR） algorithm for the p-center problem, which combines both GRASP and path-relinking. Each iteration of GRASP/PR consists of the construction of a randomized greedy solution, followed by a tabu search procedure. The resulting solution is combined with one of the elite solutions by path-relinking, which consists in exploring trajectories that connect high-quality solutions. Experiments show that GRASP/PR is competitive with the state-of-the-art algorithms in the literature in terms of both solution quality and computational efficiency. Specifically, it virtually improves the previous best known results for 10 out of 40 large instances while matching the best known results for others.

Improved binary artificial bee colony algorithm

The artificial bee colony(ABC)algorithm is an evolutionary optimization algorithm based on swarm intelligence and inspired by the honey bees’food search behavior.Since the ABC algorithm has been developed to achieve optimal solutions by searching in the continuous search space,modification is required to apply it to binary optimization problems.In this study,we modify the ABC algorithm to solve binary optimization problems and name it the improved binary ABC(IbinABC).The proposed method consists of an update mechanism based on fitness values and the selection of different decision variables.Therefore,we aim to prevent the ABC algorithm from getting stuck in a local minimum by increasing its exploration ability.We compare the IbinABC algorithm with three variants of the ABC and other meta-heuristic algorithms in the literature.For comparison,we use the well-known OR-Library dataset containing 15 problem instances prepared for the uncapacitated facility location problem.Computational results show that the proposed algorithm is superior to the others in terms of convergence speed and robustness.The source code of the algorithm is available at https://github.com/rafetdurgut/ibinABC.