Search

Typically, within facility location problems, fairness is defined in terms of accessibility of users. However, for facilities perceived as undesirable by communities hosting them, fairness between the usage of facilities becomes especially important. Limited research exists on this notion of fairness. To close this gap, we develop a series of optimization models for the allocation of populations of users to facilities such that access for users is balanced with a fair utilization of facilities. The optimality conditions of the underlying nonconvex quadratic models state the precise balance between accessibility and fairness. We define new classes of fairness and a metric to quantify the extent to which fairness is achieved in both optimal and suboptimal allocations. We show that a continuous relaxation of our central model is sufficient to achieve a perfect extent of fairness, while a special case reduces to the classical notion of proportional fairness. Our work is motivated by pervasive ecological challenges faced by the waste management community as policymakers seek to reduce the number of recycling centers in the last few years. As a computational case study, applying our models on data for the state of Bavaria in Germany, we find that even after the closure of a moderate number of recycling centers, large degrees of access can be ensured, provided that the closures are conducted optimally. Fairness, however, is impacted more, with facilities in rural regions shouldering larger loads of visiting populations than those in urban regions. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: Computer resources and support provided by the Erlangen Regional Computing Center are gratefully acknowledged. B. Singh was partially financially supported by the Bavarian State Ministry for Science and Art (Bayerisches Staatsministerium für Wissenschaft und Kunst) under the Competence Network for Scientific High Performance Computing in Bavaria. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0308) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0308). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Let G=(V,E)$$ G=\left(V,E\right) $$ be a graph with unit‐length edges and nonnegative costs assigned to its vertices. Given a list of pairwise different vertices S=(s1,s2,...,sp)$$ S=\left({s}_1,{s}_2,\dots, {s}_p\right) $$, the prioritized Voronoi diagram of G$$ G $$ with respect to S$$ S $$ is the partition of G$$ G $$ in p$$ p $$ subsets V1,V2,...,Vp$$ {V}_1,{V}_2,\dots, {V}_p $$ so that, for every i$$ i $$ with 1≤i≤p$$ 1\le i\le p $$, a vertex v$$ v $$ is in Vi$$ {V}_i $$ if and only if si$$ {s}_i $$ is a closest vertex to v$$ v $$ in S$$ S $$ and there is no closest vertex to v$$ v $$ in S$$ S $$ within the subset {s1,s2,...,si−1}$$ \left\{{s}_1,{s}_2,\dots, {s}_{i-1}\right\} $$. For every i$$ i $$ with 1≤i≤p$$ 1\le i\le p $$, the load of vertex si$$ {s}_i $$ equals the sum of the costs of all vertices in Vi$$ {V}_i $$. The load of S$$ S $$ equals the maximum load of a vertex in S$$ S $$. We study the problem of adding one more vertex v$$ v $$ at the end of S$$ S $$ in order to minimize the load. This problem occurs in the context of optimally locating a new service facility (e.g., a school or a hospital) while taking into account already existing facilities, and with the goal of minimizing the maximum congestion at a site. There is a brute‐force algorithm for solving this problem in 풪(nm) time on n$$ n $$‐vertex m$$ m $$‐edge graphs. We prove a matching time lower bound–up to sub‐polynomial factors–for the special case where m=n1+o(1)$$ m={n}^{1+o(1)} $$ and p=1$$ p=1 $$, assuming the so called Hitting Set Conjecture of Abboud et al. On the positive side, we present simple linear‐time algorithms for this problem on cliques, paths and cycles, and almost linear‐time algorithms for trees, proper interval graphs and (assuming p$$ p $$ to be a constant) bounded‐treewidth graphs. [ABSTRACT FROM AUTHOR]

Indonesia has abundant potential for solar energy. The decrease in the cost of solar power generation components can bolster the development of solar power plants. Due to its geographical characteristics, it is essential to analyze the feasibility of using solar power plants as a primary renewable energy source in Indonesia, especially on Sumatra Island. One of the critical aspects of developing solar power plants is determining the suitable location of the power plant and allocating the electricity generated to the regions. Therefore, this study considers the Capacitated Location Allocation Problem (CLAP) to determine the optimal placement of solar power plants on Sumatra Island to minimize investment and transmission costs. To address the problem, we explore three metaheuristics, namely Particle Swarm Optimization (PSO), Simulated Annealing (SA), and Large Neighborhood Search (LNS). The results obtained by these metaheuristic methods show significant differences in cost, with SA providing the best solution with the lowest cost. The investment and transmission cost can be minimized by solving the CLAP to obtain optimal solar power plant placement while enhancing the region's resilience in implementing distributed generation. [ABSTRACT FROM AUTHOR]

The Capacitated Facility Location Problem (CFLP) is a well-known optimisation problem with applications in a number of fields, such as distribution system planning, telecommunication network design, and supply chain design. The goal of this paper is to present a matheuristic algorithm based on the corridor method, to develop a general algorithm for a number of variants of the CFLP. The algorithm exploits solutions obtained via Lagrangean relaxation and builds corridors around such solutions via the introduction of constraints around the incumbent solution, used to limit the size of the solution space explored at each iteration. A thorough exploration of the neighbourhoods induced by the corridors is carried out using a mixed integer programming (MIP) solver. More precisely, we solve to (near) optimality over 500 benchmark instances, using the single-source as well as the multi-source formulations, both in the nominal variant, i.e. the deterministic version of the problem, and the robust variant, i.e. the version obtained when using robust optimisation to model the uncertainty of the problem parameters. The performance of the algorithm is highly competitive when compared with the best approaches proposed in the literature for each variant of the CFLP, especially considering that the algorithm has not been designed with a specific CFLP formulation in mind. [ABSTRACT FROM AUTHOR]

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement– odd , even , or unconstrained –of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparseT-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem. [ABSTRACT FROM AUTHOR]

The facility location problem (FLP) is a complex optimization problem that has been widely researched and applied in industry. In this research, we proposed two innovative approaches to complement the limitations of traditional methods, such as heuristics, metaheuristics, and genetic algorithms. The first approach involves utilizing crowdsourcing through video game players to obtain improved solutions, filling the gap in existing research on crowdsourcing for FLP. The second approach leverages machine learning techniques, specifically prediction methods, to provide an efficient exploration of the solution space. Our findings indicate that machine learning techniques can complement existing solutions by providing a more comprehensive approach to solving FLP and filling gaps in the solution space. Furthermore, machine learning predictive models are efficient for decision making and provide quick insights into the system's behavior. In conclusion, this research contributes to the advancement of problem-solving techniques and has potential implications for solving a wide range of complex, NP-hard problems in various domains. [ABSTRACT FROM AUTHOR]

The dominating set of the graph G is a subset D of vertex set V, such that every vertex not in V -- D is adjacent to at least one vertex in the vertex subset D. A dominating set D is a minimal dominating set if no proper subset of D is a dominating set. The number of elements in such set is called as domination number of graph and is denoted by (G). In this work the domination numbers are obtained for family of prism graphs such as prism CLn, antiprism Qn and crossed prism Rn by identifying one of their minimum dominating set. [ABSTRACT FROM AUTHOR]

Supply chain planning is becoming increasingly important today, as it is essential for efficient operations to design supply chains that are flexible, sustainable, highly available and able to respond quickly and efficiently to dynamically changing customer needs, while operating costeffectively. When designing supply chains, it is important to consider not only the investment cost but also the operational cost. This requires the most accurate forecasting of future supply chain needs. In this paper, the authors present a new method for the optimal design of a multicentre distribution network, which uses evolutionary optimisation and Monte Carlo simulation to determine the optimal distribution network structure in an arbitrary geographical area. The design takes into account investment and operational costs, with particular emphasis on the question of how to estimate the average transportation distances in a distribution network with an unknown structure. [ABSTRACT FROM AUTHOR]

The location of a logistics center is very important in a logistics system, as the success of the location determines the whole logistics system's structure, shape, and mode, and not only affects the logistics center's own operating costs, performance, and future development, but also affects the operation of the entire logistics system. Therefore, the selection of the location for a logistics center has great significance for improving the efficiency of regional logistics and optimizing the structure of a logistics system. This study constructed a multi-factor constrained P-median site-selection model to optimize the locations of logistics centers to improve the efficiency of logistics and optimize the structure of the logistics system in a region. The results show that the optimal distribution of logistics center sites and the coverage of freight capacity demand derived from the particle swarm algorithm are more balanced than those derived by the other algorithm. Following the comparison of the results for the utility of the optimized layout points solved by the particle swarm algorithm and the immune genetic algorithm, it is concluded that the optimal fitness value obtained by the particle swarm algorithm is lower than the other. It is proven that the particle swarm algorithm of the P-median site-selection model under this multi-factor constraint has some reference value for the selection of the sites of multi-logistics centers. [ABSTRACT FROM AUTHOR]

Given an n-vertex m-edge graph G of clique-width at most k, and a corresponding k-expression, we present algorithms for computing some well-known centrality indices (eccentricity and closeness) that run in O (2 O (k) (n + m) 1 + ϵ) time for any ϵ > 0 . Doing so, we can solve various distance problems within the same amount of time, including: the diameter, the center, the Wiener index and the median set. Our run-times match conditional lower bounds of Coudert et al. (SODA'18) under the Strong Exponential-Time Hypothesis. On our way, we get a distance-labeling scheme for n-vertex m-edge graphs of clique-width at most k, using O (k log 2 n) bits per vertex and constructible in O ~ (k (n + m)) time from a given k-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on k in their scheme. As a corollary, we get an O ~ (k n 2) -time algorithm for computing All-Pairs Shortest-Paths on n-vertex graphs of clique-width at most k, being given a k-expression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with non-negative vertex-weights, under two different types of distances studied in the literature. For that, we introduce a new type of orthogonal range query as a side contribution of this work, that might be of independent interest. [ABSTRACT FROM AUTHOR]

Ageneric class of multistage optimisation problems related to production/inventorymanagement underMarkovian uncertainty is introduced and investigated. For each instance in the class, it is shown how to construct state-space representable uncertainty sets at any probability level, thus leading to efficient resolution of both the stochastic and robust versions of the problem. Computational experiments aimed at comparing the optimal strategies corresponding to both versions in terms of risk are then reported and discussed; it is observed that the robust optimisation approach can significantly outperform the stochastic optimisation approach when targeting lower risk levels (typically less than 2%). [ABSTRACT FROM AUTHOR]

We consider the problem of designing a parcel locker network as a solution to the Logistics LastMile Problem: Choosing the optimal number, locations, and sizes of parcel locekers facilities. The objective is to maximize the total profit, consisting of the revenue from customers who use the service, minus the facilities' fixed and operational setup costs, the discounts in the delivery costs for customers who need to travel in order to collect their parcels, and the loss of potential customers who are not willing to travel for service. The problem is expressed as a 0-1 integer linear program. We show that it is equivalent to the well-known Uncapacitated Facility Location Problem. We then solve the modified problem, and apply it to an industrial-sized network. [ABSTRACT FROM AUTHOR]

In this paper, we present an extension of the classic p-median facility location model. The new formulation allows the user to trace the trade-off between the demand-weighted average distance (the traditional p-median objective) and the range in assigned demand. We extend the model to incorporate additional constraints that significantly reduce the computation time associated with the model. We also outline a genetic algorithm-based approach for solving the problem. The paper shows that significant reductions in the range in assigned demand are possible with relatively minor degradations in the average distance metric. The paper also shows that the genetic algorithm does very well at identifying the approximate trade-off curve. The model and algorithms were tested on real-life data-sets ranging in size from 33 nodes to 880 nodes. [ABSTRACT FROM AUTHOR]

Design of facilities network, allocation of customers to be served from the facilities and their operations have strong economic, environmental and social impacts. Although the decisions in the facility location problem may have varying effects on these impacts, simultaneous consideration of these effects in the early stages of decision-making for facility location selection and network plan has attracted limited attention in the facility location decision literature. Specifically, the social dimension and mathematical modelling are rarely used. In this paper, we present a decision support framework for the facility location problem that incorporates the triple bottom line accounting of sustainability. The framework is a valuable integration of mathematical modelling embedding the criteria with proper measurement indicators in a multi-objective model, perspectives of the related stakeholders, any thresholds and assumption, model analysis, and the decision-maker strategy to find the best-fit alternative.We demonstrate our methodological approach to establish a supply network for digital products in Turkey using real data. The results indicate that the method can balance the economic, environmental and social pillars, based on limitations of the three pillars and strategic perspective of the decision-maker. The decision-maker can interpret the interactions among the three pillars of sustainability and can make his decision by analysing the balance between them. [ABSTRACT FROM AUTHOR]

In this paper, we study a two-echelon capacitated facility location problem with plant size selection (TECFLP-PSS). Given a set of potential sites for plants, each of which is associated with several possible sizes and corresponding unit production costs, a set of potential sites for capacitated depots and a set of customers with demands, the TECFLP-PSS aims to optimise the plant locations and sizes, the depot locations and the product flows from the opened plants to the opened depots and then to the end customers under single-source constraints. The objective is to satisfy all customers’ demands with a minimum total cost of facility opening, production and transportation. We develop a mixed integer programming model and propose a Lagrangean relaxation approach combined with new valid inequalities and core problem to achieve tight lower and upper bounds for this problem. We then improve the upper bound with a hybrid simulated annealing tabu search procedure. Computational experiments on benchmarks and randomly generated instances are conducted to validate the effectiveness and efficiency of the proposed method. [ABSTRACT FROM PUBLISHER]

In this paper, we apply the minimum information theory to the uncapacitated p-median facility location problem to determine the most probable allocation solution. Indeed, we investigate the bi-level p-median model introduced by [TRANSPORT RES B-METH. 123 (2019) 1–20] in the case that facilities have unlimited capacities. At the upper level, minimizing the cost of establishing facilities and allocating demands is considered, while the most probable allocation solution in the customers' point of view is determined through the lower level. By adding the Karush-Kuhn-Tucker optimality conditions of the lower-level problem to the upper-level constraints, the bi-level model is reduced to a one-level linear mixed integer problem. Some numerical examples are provided to verify the added value of the proposed model and its solution method. [ABSTRACT FROM AUTHOR]

Protecting important nodes in a network against natural disasters, security threats, attacks, and so on is one of the main goals of network planners. In this paper, a new model is presented for protecting an important node (NMPN) in a typical network based on a defensive location problem where the threatening agent (t-agent) can reinforce its power at some nodes. The NMPN is a bi-level programming problem. At the upper level, the planner agent (p-agent) try to find the best lo- cations for protecting resources in order to protect the important node. The lower level problem is represented as the shortest path problem in the network in which the edges are weighted with positive values and sometimes negative values. Thus, the Bellman-Ford algorithm is applied to solve the lower level problem. The NMPN is an NP-hard problem. In this work, the genetic, ant colony optimization, binary artificial bee colony with differential evolution, artificial bee colony algorithms, and a modified tabu search (MTS) algorithm are used to solve it. A test problem is randomly generated to investigate the performance of the metaheuristic algorithms in this paper. Parameters of the metaheuris- tic algorithms are tuned by the Taguchi method for solving the test problem. Also, the ANOVA test and Tukey's test are used to compare the performance of the metaheuristic algorithms. The best results are obtained by the MTS algorithm. [ABSTRACT FROM AUTHOR]

The facility location problem (FLP) is a complex optimization problem that has been widely researched and applied in industry. In this research, we proposed two innovative approaches to complement the limitations of traditional methods, such as heuristics, metaheuristics, and genetic algorithms. The first approach involves utilizing crowdsourcing through video game players to obtain improved solutions, filling the gap in existing research on crowdsourcing for FLP. The second approach leverages machine learning techniques, specifically prediction methods, to provide an efficient exploration of the solution space. Our findings indicate that machine learning techniques can complement existing solutions by providing a more comprehensive approach to solving FLP and filling gaps in the solution space. Furthermore, machine learning predictive models are efficient for decision making and provide quick insights into the system’s behavior. In conclusion, this research contributes to the advancement of problem-solving techniques and has potential implications for solving a wide range of complex, NP-hard problems in various domains.

In this study, we have considered a multi-period centre facility location–relocation problem in the presence of a probabilistic polyhedral barrier uniformly distributed on a horizontal barrier route in rectilinear plane. The objective function of this location–relocation problem is the minimisation of the cost of maximum expected rectilinear barrier distance from demand points to the new facility plus the relocation cost (i.e. a changeover cost at the beginning of each period) in the form of a mixed integer quadratic-constrained mathematical programming. The computational results show that the non-linear solver of commercial software LINGO is only effective in solving small-sized problems. A linear approximation for the system constraints is proposed so that a new mixed integer linear programming model is generated which is solvable via CPLEX optimisation software. Moreover, we proposed a problem decomposition procedure that reduces the multi-period problem into a number of single-period problems with some modifications. To show the efficiency of the model and solution methodologies, a broad range of numerical examples are performed. Results indicate that the developed problem decomposition procedure obtains the near-optimal solution comparatively with the results obtained from the non-linear solver of LINGO, and that the lower bound problem can be useful for large-sized problems in a reasonable time. Moreover, a practical case example to show the model validity in real world is solved and to reality check from practice, results are compared with the problem without barrier. [ABSTRACT FROM AUTHOR]

Copyright of Duzce University Journal of Science & Technology is the property of Duzce University Journal of Science & Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Nowadays – particularly in systems dealing with hazardous materials (HAZMAT) – in addition to minimising the cost of operations in facility location and routing problems, the risk of these operations is considered an important objective. In this paper, a new mathematical model for the location and routing in facilities and disposal sites is proposed. Also, the risk and cost of transporting goods from facilities to customers is considered. The model minimises weighted sum of the cost and risk by answering these questions: (1) where to open the facilities which produce HAZMAT; (2) where to open disposal sites; (3) to which facilities every customer should be assigned; (4) to which disposal site each facility should be assigned; (5) which route a facility should choose to serve the customers; and (6) which route a facility should choose to reach a disposal site. A novel GA is applied to solve the mathematical model. The results show the robustness of GA in terms of finding high-quality non-dominated solutions and running time. [ABSTRACT FROM PUBLISHER]

This paper presents a new heuristic algorithm for the following covering problem. For a set of n demand points in continuous space, locate a given number of facilities or sensors anywhere on the plane in order to obtain maximum coverage. This means, in this problem an infinite set of potential locations in continuous space should be explored. We present a heuristic algorithm that finds a near-optimal solution for large-scale instances of this problem in a reason- able time. Moreover, we compare our results with previous algorithms on randomly generated datasets that vary in size and distribution. Our experiments show that in comparison to other methods in the literature, the proposed algorithm is scalable and can find solutions for large-scale instances very fast, when previous algorithms unable to handle these instances. Finally, some results of the tests performed on a real-world dataset are also presented. [ABSTRACT FROM AUTHOR]

The present paper deals with a variant of hub location problems (HLP): the uncapacitated single allocation p-Hub median problem (USApHMP). This problem consists to jointly locate hub facilities and to allocate demand nodes to these selected facilities. The objective function is to minimize the routing of demands between any origin and destination pair of nodes. This problem is known to be NP-hard. Based on the artificial immune systems (AIS) framework, this paper develops a new approach to efficiently solve the USApHMP. The proposed approach is in the form of a clonal selection algorithm (CSA) that uses appropriate encoding schemes of solutions and maintains their feasibility. Comprehensive experiments and comparison of the proposed approach with other existing heuristics are conducted on benchmark from civil aeronautics board, Australian post, PlanetLab and Urand data sets. The results obtained allow to demonstrate the validity and the effectiveness of our approach. In terms of solution quality, the results obtained outperform the best-known solutions in the literature. [ABSTRACT FROM AUTHOR]

In disasters, the first seventy-two hours is very important in terms of reducing the loss of life. The existence and optimal placement of earthquake containers should be taken into consideration during disaster preparedness. Such containers can be considered as facilities to ensure the survival of people in the event of disasters and to ensure that the first response is performed correctly and in a timely manner. In this study, it is aimed to determine the optimum locations of two containers which are planned to be placed for a limited area. In the analysis of the study, which is modeled as a Multi-Criteria Decision Making Problem (MCDM), there are 5 criteria and 7 alternatives. The data of the study was obtained from the Provincial Directorate of AFAD and the authorities of the relevant region. Critic-Gray Relational Hybrid approach was used in the analysis process of the study. Calculations were made using the Microsoft Excell program. As a result of the conducted analyses; (A1) Bahçelievler was found to be the first place, (A5) Güzelbahçe the second and (A3) Demetevler the third location. The results of the study have been shared with provincial disaster coordination authorities. [ABSTRACT FROM AUTHOR]

Pursuing the overarching goal of saving both lives and healthcare costs, we introduce an approach to increase the expected participation in a preventive healthcare program, e.g., breast cancer screening. In contrast to sick people who need urgent medical attention, the clients in preventive healthcare decide whether to go to a specific facility (if this maximizes their utility) or not to take part in the program. We consider clients' utility functions to include decision variables denoting the waiting time for an appointment and the quality of care. Both variables are defined as functions of a facility's utilization. We employ a segmentation approach to formulate a mixed-integer linear program. Applying GAMS/CPLEX, we optimally solved instances with up to 400 demand nodes and 15 candidate locations based on both artificial data as well as in the context of a case study based on empirical data within one hour. We found that using a Benders decomposition of our problem decreases computational effort by more than 50%. We observe a nonlinear relationship between participation and the number of established facilities. The sensitivity analysis of the utility weights provides evidence on the optimal participation given a specific application (data set, empirical findings). [ABSTRACT FROM AUTHOR]