The discrete Unconscious search and its application to uncapacitated facility location problem

In this paper a discrete variant of Unconscious search (US) for solving uncapacitated facility location problem (UFLP) is proposed. Unconscious search mimics the process of psychoanalytic psychotherapy in which the psychoanalyst tries to access the unconscious of a mental patient to find the root cause his/her problem, which is encapsulated in unconsciousness. Unconscious search is a multi-start metaheuristic which has three main stages, namely construction, construction review and local search. In construction phase a new solution is generated. In construction review the generated solution in construction phase is used to produce more starting points for using in the local search phase. The results of applying US to UFLP shows that this metaheuristic can determine high quality solutions in short processing time comparing to other heuristics.     

Branch-and-bound algorithm for a competitive facility location problem

We study a mathematical model generalizing the well-known facility location problem. In this model we consider two competing sides successively placing their facilities and aiming to “capture” consumers, in order to make maximal profit. We state the problem as a bilevel integer programming problem, regarding optimal noncooperative solutions as optimal solutions. We propose a branch-and-bound algorithm for finding the optimal noncooperative solution. While constructing the algorithm, we represent our problem as the problem of maximizing a pseudo-Boolean function. An important ingredient of the algorithm is a method for calculating an upper bound for the values of the pseudo-Boolean function on subsets of solutions. We present the results of a simulation demonstrating the computational capabilities of the proposed algorithm.     

Local search heuristics for the mobile facility location problem

In the mobile facility location problem (MFLP), one seeks to relocate (or move) a set of existing facilities and assign clients to these facilities so that the sum of facility movement costs and the client travel costs (each to its assigned facility) is minimized. This paper studies formulations and develops local search heuristics for the MFLP. First, we develop an integer programming (IP) formulation for the MFLP by observing that for a given set of facility destinations the problem may be decomposed into two polynomially solvable subproblems. This IP formulation is quite compact in terms of the number of nonzero coefficients in the constraint matrix and the number of integer variables; and allows for the solution of large-scale MFLP instances. Using the decomposition observation, we propose two local search neighborhoods for the MFLP. We report on extensive computational tests of the new IP formulation and local search heuristics on a large range of instances. These tests demonstrate that the proposed formulation and local search heuristics significantly outperform the existing formulation and a previously developed local search heuristic for the problem.     

Binary crow search algorithm for the uncapacitated facility location problem

Neural Computing and Applications - The crow search algorithm (CSA) is a recently proposed population-based optimization algorithm for continuous optimization. Since the original CSA searches for a...     

Solving the uncapacitated facility location problem using tabu search

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.     

设备定位问题局部搜索算法的实验

讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法,设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解;贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法,但两者求解质量相当;设备价值和服务价值数值范围越大,局部搜索算法越容易求得最优解。     

Local search algorithms for the problem of competitive location of enterprises

This article deals with the mathematical model that generalizes the known problem of location of enterprises and is represented in the form of the problem of bilevel mathematical programming. In this model two competitive sides sequentially locate enterprises, and each of the sides strives to maximize its profit. As optimal solutions of the investigated problem, optimal cooperative and optimal noncooperative solutions are considered. The method is suggested for calculating the upper bounds of values of the goal function of the problem at optimal cooperative and noncooperative solutions. Simultaneously with the calculation of the upper bound, the initial approximate solution is set up. Algorithms of the local search for improving this solution are suggested. The algorithms involve two stages: at the first stage the locally optimal solution is found, while at the second stage the locally optimal solution relative to the neighborhood called the generalized one is found. The results of computational experiments demonstrating the possibilities of the suggested algorithms are displayed.     

Location equilibria for a continuous competitive facility location problem under delivered pricing

The problem of finding location equilibria of a location-price game where firms first select their locations and then set delivered prices in order to maximise their profits is investigated. Assuming that firms set the equilibrium prices in the second stage, the game can be reduced to a location game for which a global minimiser of the social cost is a location equilibrium, provided that the demand is completely inelastic and the marginal production cost is constant. When the set of feasible locations is a region of the plane the minimisation of the social cost becomes a hard-to-solve global optimisation problem. We propose an exact interval branch-and-bound algorithm suitable for small and medium size problems and an alternating Weiszfeld-like heuristic for larger instances. The latter approach is based on a new iterative formula for which the validity of the descent property is proved. The proposed heuristic performs extremely well against the exact method when tested on small to medium size instances while requiring a tiny fraction of its computational time.     

On the competitive facility location problem with a free choice of suppliers

We consider a mathematical model from the class of competitive sequential facility location problems. In these problems, the competitors sequentially open their facilities, and each side aims to “capture” the consumers and maximize its profits. In the proposed model, we consider a situation of a “free” choice by each side of an open facility to service a customer. The model is formulated as a bilevel integer programming problem. We show that the problem of finding an optimal noncooperative solution can be represented as a maximization problem for a pseudo-Boolean function. We propose an algorithm for constructing an admissible noncooperative solution for fixed values of the variables in this pseudo-Boolean function. We also propose a method for constructing an upper bound on the maximal value of the pseudo-Boolean function on subsets of solutions defined by partial (0, 1)-vectors.     

Approximating the Pareto-front of a planar bi-objective competitive facility location and design problem

A bi-objective competitive facility location and design problem is considered. The problem of obtaining a complete representation of the efficient set and its corresponding Pareto-front has been previously tackled through exact general methods, but they require high computational effort. In this work, we propose a new evolutionary multi-objective optimization algorithm, named FEMOEA, which deals with the problem at hand in a fast and efficient way. It combines ideas from different multi-objective and single-objective optimization evolutionary algorithms, although it also incorporates new devices which help to reduce the computational requirements, and also to improve the quality of the provided solutions. The performance of the algorithm is analyzed by comparing it to other (meta)heuristics previously proposed in the literature. In particular, the reference algorithms MOEA/D, SPEA2 and NSGA-II have been considered. A comprehensive computational study shows that the new heuristic method outperforms, on average, the three heuristic algorithms. Additionally, it reduces, on average, the computing time of the exact methods by approximately 99%, and this offering high-quality discrete approximations of the true Pareto-front.     

RAMP algorithms for the capacitated facility location problem

Annals of Mathematics and Artificial Intelligence - In this paper, we address the Capacitated Facility Location Problem (CFLP) in which the assignment of facilities to customers must ensure enough...     

Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

Bilevel competitive facility location and pricing problems

We propose new models for competitive facility location and pricing as bilevel Boolean linear programming problems. We obtain results that characterize the complexity of the problem where a monopolist’s profit on each of the markets is defined with a monotone nonincreasing function of the servicing cost. For this problem, we also propose two approximate algorithms based on the ideas of alternating heuristics and local search. We give results of a computational experiment that show a possibility for fast computation of approximate solutions.     

The congested facility location problem

Consider a network facility location problem where congestion arises at facilities, and is represented by delay functions that approximate the queueing process. We strive to minimize the sum of customers' transportation and waiting times, and facilities' fixed and variable costs. The problem is solved using a column generation technique within a branch-and-bound scheme. Numerical results are reported and a bilevel (user-optimized) formulation considered, among other extensions.     

A leader-follower game in competitive facility location

We address the problem of locating new facilities of a firm or franchise that enters a market where a competitor operates existing facilities. The goal of the new entrant firm is to decide the location and attractiveness of its new facilities that maximize its profit. The competitor can react by opening new facilities, closing existing ones, and adjusting the attractiveness levels of its existing facilities, with the aim of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the new facilities of both the firm and the competitor can be located at predetermined candidate sites. We employ the gravity-based rule in modeling the behavior of the customers where the probability that a customer visits a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. We propose heuristics that combine tabu search with exact solution methods.     

平面选址问题的引力搜索算法求解

为求解平面选址问题,给出了一种基于引力搜索算法的求解方法。算法利用万有引力定律进行全局搜索,采用一种邻域搜索方法进行局部搜索,实现算法全局优化和局部优化的平衡。通过大量实验和与现有求解方法的比较,结果验证了算法的可行性和有效性。     

A parallel local search approach to solving the uncapacitated warehouse location problem

The uncapacitated warehouse location problem (UWLP) has been studied by many researchers. It has been solved using various approaches, including branch and bound linear programming, tabu search, simulated annealing, and genetic algorithms. This study presents a new local search (LS) approach to the UWLP that is quite simple and robust and is efficient in some cases. The algorithm was tested against standard OR Library benchmarks and M^* instances, which have already been used to test other approaches. The results show that the only disadvantage of the algorithm is the exponential growth of its computation time with the problem size. However, the multi-search design suggested here enables the algorithm to run under multi-processor or multi-core systems, which are currently provided as part of standard PC configurations.     

A parallel local search approach to solving the uncapacitated warehouse location problem

The uncapacitated warehouse location problem (UWLP) has been studied by many researchers. It has been solved using various approaches, including branch and bound linear programming, tabu search, simulated annealing, and genetic algorithms. This study presents a new local search (LS) approach to the UWLP that is quite simple and robust and is efficient in some cases. The algorithm was tested against standard OR Library benchmarks and M^* instances, which have already been used to test other approaches. The results show that the only disadvantage of the algorithm is the exponential growth of its computation time with the problem size. However, the multi-search design suggested here enables the algorithm to run under multi-processor or multi-core systems, which are currently provided as part of standard PC configurations.     

A simple and deterministic competitive algorithm for online facility location

This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also applies to a variety of models, i.e., models where the facilities can be placed anywhere in the region, or only at customer sites, or only at fixed locations. The paper shows that the algorithm is O (log n)-competitive under these various models, where n is the total number of customers. It also shows that the algorithm is O (1)-competitive with high probability and for any arrival order when customers are uniformly distributed or when they follow a distribution satisfying a smoothness property. Experimental results for a variety of scenarios indicate that the algorithm behaves extremely well in practice.