A bi-objective uncapacitated facility location problem

We consider a bi-objective model for uncapacitated facility location where one objective is to maximize the net profit and the other to maximize the profitability of the investment. We first characterize the structure of the model having both a linear and a fractional objective function. In order to generate efficient solutions for the model, we develop a heuristic procedure which has computational advantages over existing methods. A numerical example is presented to illustrate the solution process and computational tests on large scale problems are also provided.     

A bi-objective modeling approach applied to an urban semi-desirable facility location problem

This paper introduces a mixed-integer, bi-objective programming approach to identify the locations and capacities of semi-desirable (or semi-obnoxious) facilities. The first objective minimizes the total investment cost; the second one minimizes the dissatisfaction by incorporating together in the same function “pull” and “push” characteristics of the decision problem (individuals do not want to live too close, but they do not want to be too far, from facilities). The model determines the number of facilities to be opened, the respective capacities, their locations, their respective shares of the total demand, and the population that is assigned to each candidate site opened. The proposed approach was tested with a case study for a particular urban planning problem: the location of sorted waste containers. The complete set of (supported or unsupported) non-inferior solutions, consisting of combinations of multi-compartment containers for the disposal of four types of sorted waste in nineteen candidate sites, and population assignments, was generated. The results obtained for part of the historical center of an old European city (Coimbra, Portugal) show that this approach can be applied to a real-world planning scenario.     

An interactive solution approach for a bi-objective semi-desirable location problem

In this study, we consider a semi-desirable facility location problem in a continuous planar region considering the interaction between the facility and the existing demand points. A facility can be defined as semi-desirable if it has both undesirable and desirable effects to the people living in the vicinity. Our aim is to maximize the weighted distance of the facility from the closest demand point as well as to minimize the service cost of the facility. The distance between the facility and the demand points is measured with the rectilinear metric. For the solution of the problem, a three-phase interactive geometrical branch and bound algorithm is suggested to find the most preferred efficient solution. In the first two phases, we aim to eliminate the parts of the feasible region the inefficiency of which can be proved. The third phase has been suggested for an interactive search in the remaining regions with the involvement of a decision maker (DM). In the third phase, the DM is given the opportunity to use either an exact or an approximate procedure to carry out the search. The exact procedure is based on the reference point approach and guarantees to find an efficient point as the most preferred solution. On the other hand, in the approximate procedure, a hybrid methodology is used to increase the efficiency of the reference point approach. The approximate procedure can be used when the DM prefers to see locally efficient solutions so as to save computation time. We demonstrate the performance of the proposed method through example problems.     

A polynomial algorithm for the multicriteria cent-dian location problem

Given a network with several weights per node and several lengths per edge, we address the problem of locating a facility on the network such that the convex combinations of the center and median objective functions are minimized. Since we consider several weights and several lengths, various objective functions should be minimized, and hence we have to solve a multicriteria cent-dian location problem. A polynomial algorithm to characterize the efficient location point set on the network is developed. Furthermore, this model can generalize other problems such as the multicriteria center problem and the multicriteria median problem. Computing time results on random planar networks considering different combinations of weights and lengths are reported, which strengthen the polynomial complexity of the procedure.     

A multicriteria facility location model for municipal solid waste management in North Greece

Up to 2002, Hellenic Solid Waste Management (SWM) policy specified that each of the country’s 54 prefectural governments plan its own SWM system. After 2002, this authority was shifted to the country’s 13 regions entirely. In this paper, we compare and contrast regional and prefectural SWM planning in Central Macedonia. To design the prefectural plan, we assume that each prefecture must be self-sufficient, and we locate waste facilities in each prefecture. In contrast, in the regional plan, we assume cooperation between prefectures and locate waste facilities to serve the entire region. We present a new multicriteria mixed-integer linear programming model to solve the location–allocation problem for municipal SWM at the regional level. We apply the lexicographic minimax approach to obtain a “fair” nondominated solution, a solution with all normalized objectives as equal to one another as possible. A solution to the model consists of locations and technologies for transfer stations, material recovery facilities, incinerators and sanitary landfills, as well as the waste flow between these locations.     

Solving a bi-objective nurse rerostering problem by using a utopic Pareto genetic heuristic

Nurse rerostering arises when at least one nurse announces that she will be unable to undertake the tasks previously assigned to her. The problem amounts to building a new roster that satisfies the hard constraints already met by the current one and, as much as possible, fulfils two groups of soft constraints which define the two objectives to be attained. A bi-objective genetic heuristic was designed on the basis of a population of individuals characterised by pairs of chromosomes, whose fitness complies with the Pareto ranking of the respective decoded solution. It includes an elitist policy, as well as a new utopic strategy, introduced for purposes of diversification. The computational experiments produced promising results for the practical application of this approach to real life instances arising from a public hospital in Lisbon.     

A projection method for the uncapacitated facility location problem

Several algorithms already exist for solving the uncapacitated facility location problem. The most efficient are based upon the solution of the strong linear programming relaxation. The dual of this relaxation has a condensed form which consists of minimizing a certain piecewise linear convex function. This paper presents a new method for solving the uncapacitated facility location problem based upon the exact solution of the condensed dual via orthogonal projections. The amount of work per iteration is of the same order as that of a simplex iteration for a linear program inm variables and constraints, wherem is the number of clients. For comparison, the underlying linear programming dual hasmn + m + n variables andmn +n constraints, wheren is the number of potential locations for the facilities. The method is flexible as it can handle side constraints. In particular, when there is a duality gap, the linear programming formulation can be strengthened by adding cuts. Numerical results for some classical test problems are included.     

On the lexicographic minimax approach to location problems

When locating public facilities, the distribution of travel distances among the service recipients is an important issue. It is usually tackled with the minimax (center) solution concept. The minimax solution concept, despite the most commonly used in the public sector location models, is criticized as it does not comply with the major principles of the efficiency and equity modeling. In this paper we develop a concept of the lexicographic minimax solution (lexicographic center) being a refinement of the standard minimax approach to location problems. We show that the lexicographic minimax approach complies with both the Pareto-optimality (efficiency) principle (crucial in multiple criteria optimization) and the principle of transfers (essential for equity measures) whereas the standard minimax approach may violate both these principles. Computational algorithms are developed for the lexicographic minimax solution of discrete location problems.     

Solving a bi-objective Transportation Location Routing Problem by metaheuristic algorithms

In this work we consider a Transportation Location Routing Problem (TLRP) that can be seen as an extension of the two stage Location Routing Problem, in which the first stage corresponds to a transportation problem with truck capacity. Two objectives are considered in this research, reduction of distribution cost and balance of workloads for drivers in the routing stage. Here, we present a mathematical formulation for the bi-objective TLRP and propose a new representation for the TLRP based on priorities. This representation lets us manage the problem easily and reduces the computational effort, plus, it is suitable to be used with both local search based and evolutionary approaches. In order to demonstrate its efficiency, it was implemented in two metaheuristic solution algorithms based on the Scatter Tabu Search Procedure for Non-Linear Multiobjective Optimization (SSPMO) and on the Non-dominated Sorting Genetic Algorithm II (NSGA-II) strategies. Computational experiments showed efficient results in solution quality and computing time.     

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.     

A general model for the undesirable single facility location problem

In this paper, a finite set in which an optimal solution for a general Euclidean problem of locating an undesirable facility in a polygonal region, is determined and can be found in polynomial time. The general problem we propose leads us, among others, to several well-known problems such as the maxisum, maximin, anticentdian or r-anticentrum problem.     

Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example

The Colombian coffee supply network, managed by the Federación Nacional de Cafeteros de Colombia (Colombian National Coffee-Growers Federation), requires slimming down operational costs while continuing to provide a high level of service in terms of coverage to its affiliated coffee growers. We model this problem as a biobjective (cost-coverage) uncapacitated facility location problem (BOUFLP). We designed and implemented three different algorithms for the BOUFLP that are able to obtain a good approximation of the Pareto frontier. We designed an algorithm based on the Nondominated Sorting Genetic Algorithm; an algorithm based on the Pareto Archive Evolution Strategy; and an algorithm based on mathematical programming. We developed a random problem generator for testing and comparison using as reference the Colombian coffee supply network with 29 depots and 47 purchasing centers. We compared the algorithms based on the quality of the approximation to the Pareto frontier using a nondominated space metric inspired on Zitzler and Thiele's. We used the mathematical programming-based algorithm to identify unique tradeoff opportunities for the reconfiguration of the Colombian coffee supply network. Finally, we illustrate an extension of the mathematical programming-based algorithm to perform scenario analysis for a set of uncapacitated location problems found in the literature.     

Linear facility location — Solving extensions of the basic problem

The basic problem is to locate a linear facility to minimize the sume of weighted shortest Euclidean distances from demand points to the facility. We extend the analysis to locating a constrained linear facility, a radial facility, a linear facility where distances are rectangular and a linear facility under the minimax criterion. Each case is shown to admit a simple solution technique.     

Public facility location using dispersion,population, and equity criteria

From a practical perspective, the paper demonstrates that the appropriate use of dispersion, population, and equity criteria can lead to fairly good solutions with respect to the p-median objective. The only stipulation is that the decision maker verifies (through simple constraint checks) that the chosen locations meet the dispersion, population, and equity criteria. An empirical investigation is conducted to obtain appropriate values for these parameters. From a location science perspective, a new location model that accounts for equity and efficiency simultaneously is studied and analyzed. Specifically, the p-maxian problem with side constraints on dispersion, population, and equity is developed, its NP-completeness established, and valid inequalities and bounds derived. Computational tests show encouraging results.     

A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem

We consider the multi-mode resource-constrained project scheduling problem (MRCPSP), where a task has different execution modes characterized by different resource requirements. Due to the nonrenewable resources and the multiple modes, this problem is NP-hard; therefore, we implement an evolutionary algorithm looking for a feasible solution minimizing the makespan.     

Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach

Models developed to analyze facility location decisions have typically optimized one or more objectives, subject to physical, structural, and policy constraints, in a static or deterministic setting. Because of the large capital outlays that are involved, however, facility location decisions are frequently long-term in nature. Consequently, there may be considerable uncertainty regarding the way in which relevant parameters in the location decision will change over time. In this paper, we propose two approaches for analyzing these types of dynamic location problems, focussing on situations where the total number of facilities to be located in uncertain. We term this type of location problem NOFUN (Number Of Facilities Uncertain). We analyze the NOFUN problem using two well-established decision criteria: the minimization of expected opportunity loss (EOL), and the minimization of maximum regret. In general, these criteria assume that there are a finite number of decision options and a finite number of possible states of nature. The minisum EOL criterion assumes that one can assign probabilities for the occurrence of the various states of nature and, therefore, find the initial set of facility locations that minimize the sum of expected losses across all future states. The minimax regret criteria finds the pattern of initial facility locations whose maximum loss is minimized over all possible future states.     

Solving the robust two-stage capacitated facility location problem with uncertain transportation costs

In this study, we start from a multi-source variant of the two-stage capacitated facility location problem (TSCFLP) and propose a robust optimization model of the problem that involves the uncertainty of transportation costs. Since large dimensions of the robust TSCFLP could not be solved to optimality, we design a memetic algorithm (MA), which represents a combination of an evolutionary algorithm (EA) and a modified simulated annealing heuristic (SA) that uses a short-term memory of undesirable moves from previous iterations. A set of computational experiments is conducted to examine the impact of different protection levels on the deviation of the objective function value. We also investigate the impact of variations of transportation costs that may occur on both transhipment stages on the total cost for a fixed protection level. The obtained results may help in identifying a sustainable and efficient strategy for designing a two stage capacitated transportation network with uncertain transportation costs, and may be applicable in the design and management of similar transportation networks.     

Solving nonconvex economic load dispatch problem using particle swarm optimization with time varying acceleration coefficients

This article presents the design and application of an efficient hybrid heuristic search method to solve the practical economic dispatch problem considering many nonlinear characteristics of power generators, and their operational constraints, such as transmission losses, valve‐point effects, multi‐fuel options, prohibited operating zones, ramp rate limits and spinning reserve. These practical operation constraints which can usually be found at the same time in realistic power system operations make the economic load dispatch (ELD) problem a nonsmooth optimization problem having complex and nonconvex features with heavy equality and inequality constraints. A particle swarm optimization with time varying acceleration coefficients is proposed to determine optimal ELD problem in this paper. The proposed methodology easily takes care of solving nonconvex ELD problems along with different constraints like transmission losses, dynamic operation constraints, and prohibited operating zones. The proposed approach has been implemented on the 3‐machines 6‐bus, IEEE 5‐machines 14‐bus, IEEE 6‐machines 30‐bus systems and 13 thermal units power system. The proposed technique is compared with solve the ELD problem with hybrid approach by using the valve‐point effect. The comparison results prove the capability of the proposed method give significant improvements in the generation cost for the ELD problem. © 2015 Wiley Periodicals, Inc. Complexity 21: 299–308, 2016     

Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique

This paper deals with the uncapacitated multiple allocation hub location problem. The dual problem of a four-indexed formulation is considered and a heuristic method, based on a dual-ascent technique, is designed. This heuristic, which is reinforced with several specifical subroutines and does not require any external linear problem solver, is the core tool embedded in an exact branch-and-bound framework. Besides, the heuristic provides the branch-and-bound algorithm with good lower bounds for the nodes of the branching tree. The results of the computational experience (with the classical CAB and AP data sets) are included, showing the great effectiveness of this approach: instances with up to 120 nodes are solved.     

Single facility location and relocation problem with time dependent weights and discrete planning horizon

In this paper a single facility location problem with multiple relocation opportunities is investigated. The weight associated with each demand point is a known function of time. We consider either rectilinear, or squared Euclidean, or Euclidean distances. Relocations can take place at pre-determined times. The objective function is to minimize the total location and relocation costs. An algorithm which finds the optimal locations, relocation times and the total cost, for all three types of distance measurements and various weight functions, is developed. Locations are found using constant weights, and relocations times are the solution to a Dynamic Programming or Binary Integer Programming (BIP) model. The time horizon can be finite or infinite.