The obnoxious p$p$‐median problem is a facility location problem where we maximise the sum of the distances between each client point and its nearest facility. Since it is nondeterministic ...polynomial‐time (NP)‐hard, most algorithms designed for the problem follow metaheuristic strategies to find high‐quality solutions in affordable time but with no optimality guarantee. In this paper, a variant of the iterated greedy algorithm is developed for the problem. It adopts the idea of increasing the search radius used in variable neighbourhood search by increasing the number of reconstructed components at each iteration with no improved solution, where the amount of the increase is determined dynamically based on the quality of the current solution. We demonstrate that the new algorithm significantly outperforms the current state‐of‐the‐art metaheuristic algorithms for this problem on standard datasets.
The k-medoids (k-median) problem is one of the best known unsupervised clustering problems. Due to its complexity, finding high-quality solutions for huge-scale datasets remains extremely ...challenging. The application of many approaches finding optimal or quality solutions is limited to only small and medium-size instances. On the other hand, many parallel, distributed algorithms that can handle huge-scale datasets usually provide very poor solutions. In this paper, we develop a first parallel, distributed primal–dual heuristic algorithm for the k-medoids problem. Its main component is a very efficient parallel subgradient column generation that solves a Lagrangian dual problem and finds a tight bound on solution quality. High-quality solutions are then produced by a parallel core selection technique. We considerably reduce computational burden and memory load by employing a nearest neighbor strategy to approximate the dissimilarity matrix. We demonstrate that our algorithm finds very close to optimal solutions, confirmed by the tightness of dual bounds, of instances that are much larger than those considered in the literature to date. Our experiments include clustering large-scale collections of face images into several thousand of clusters. We show that our approach outperforms parallel improved versions of the most popular k-medoids clustering algorithms, achieving nearly linear parallel speedup.
The p$p$‐median problem has been widely studied in the literature. However, there are several variants that include new constraints to the classical problem that make it more realistic. In this work, ...we study the variant that considers interconnected facilities, that is, the distances between each pair of facilities are less than or equal to a certain threshold r$r$. This optimization problem, usually known as the median location problem with interconnected facilities, consists of locating a set of interconnected facilities to minimize the distance between those interconnected facilities and the demand points. The large variety of real‐world applications that fit into this model makes it attractive to design an algorithm able to solve the problem efficiently. To this end, a procedure based on the variable neighborhood search methodology is designed and implemented by using problem‐dependent neighborhoods. Experimental results show that our proposal is able to reach most of the optimal solutions when they are known. Additionally, it outperforms previous state‐of‐the‐art methods in those instances where the optima are unknown. These results are further confirmed by conducting nonparametrical statistical tests.
Facility location models involve identifying locations for facilities that provide services to the customers which are also called demand points. The
p
-median problem is a facility location problem ...which deals with locating
p
facilities in such a way that the sumtotal of demand-weighted distances between each demand point and its respective closest facility is minimized. The
p
-median problem does not take into account the possibility of failure of the facilities, but rather considers that the facilities once located will always be available to serve the customers or demand points. But, in reality, some of the facilities may face unpredicted disruptions, thereby forcing the customers to seek services from other functioning facilities. The reliability
p
-median problem (RpMP) concerns with locating facilities which minimize the cost while considering the cost of facility failures. In this paper, we have proposed a hyper-heuristic approach with naive Bayes classifier for the RpMP and compared its performance on standard benchmark instances with two best performing approaches for RpMP, viz. a genetic algorithm and a scatter search approach available in the literature. The results show the effectiveness of our approach in terms of the solution quality.
In this paper we study the Hamiltonian p-median problem, in which we are given an edge-weighted graph and we are asked to determine p vertex-disjoint cycles spanning all vertices of the graph and ...having minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of edge variables. Each one of the families forbids solutions to the 2-factor relaxation of the problem that have less than p cycles. The inequalities in one of the families are associated with large cycles of the underlying graph and generalize known inequalities associated with Hamiltonian cycles. The other family involves inequalities for the case with p=n/3, associated with edge cuts and multi-cuts whose shores have specific cardinalities. We identify inequalities from both families that define facets of the polytope associated with the problem. We design branch-and-cut algorithms based on these families of inequalities and on inequalities associated with 2-opt moves removing sub-optimal solutions. Computational experiments on benchmark instances show that the proposed algorithms exhibit a comparable performance with respect to existing exact methods from the literature. Moreover the algorithms solve to optimality new instances with up to 400 vertices.
•The Hamiltonian p-Median problem is a location-routing problem.•Its formulation involving edge variables is studied from a polyhedral perspective.•Valid inequalities are introduced along with facet-defining conditions.•Inequalities are introduced for the cases p=n/3 along with facet-defining conditions.•Related branch-and-cut algorithms are tested on instances with up to 400 nodes.
The obnoxious p-median problem can be formulated as a constrained binary linear program. It is NP-hard, and has a lot of real world applications. In this paper, a hybrid binary particle swarm ...optimization is proposed to solve the obnoxious p-median problem. A new position updating rule is presented to inherit the good structure of previous high quality solutions. Furthermore, two tabu based mutation operators are used to avoid the premature convergence and guide the search to a promising area. A greedy repair procedure is developed to repair infeasible solutions. In addition, an iterated greedy local search procedure is utilized to enhance the exploitation ability. Extensive experiments are done on a set of 72 benchmark instances from the literature. Experimental results and comparisons with some existing algorithms demonstrate the effectiveness of the proposed algorithm. In particular, the proposed algorithm finds new best solutions for 15 instances. Compared with existing algorithms, the proposed algorithm is able to find better average objective function value in a short average computing time.
In the humanitarian relief efforts after an earthquake strikes, local capabilities are critical in the first hours to assess the situation and deliver relief supplies to the victims. Usually, the ...relief goods required by victims are unlikely to be found in the impacted areas, and resources from other places need time to be mobilized to the affected areas. Often in earthquakes in cities in developing countries, relief goods do not arrive on time causing victims to suffer even more. In this paper, we present the mathematical formulations and solutions techniques for designing a short-distance distribution network of relief goods, which can be managed by local governments. In the preparation phase, as a part of the immediate response plan based on scenarios, the facilities location and the preliminary distribution paths must be determined. Hence, a p-median problem and a multi-depot heterogeneous fleet vehicle routing problem (MDHFVRP) must be solved. These problems are usually small and there is time to find a solution. However, in the response phase, a dynamical VRP must be solved.
The Emergency Department (ED) is one part of a hospital that provides initial treatment for patients who suffer from illness and injury, which can threaten their survival. The importance of ...integrated care in the ED is one of the keys to successfully treating patients at an advanced level. This becomes complex because the ED works in a team consisting of various multi-disciplinary sciences and limited human resources, facilities, and infrastructure. In the City of Palembang, 23 hospitals have emergency room facilities from 18 Sub-Districts, by using the TOPSIS (Technique for Others Reference by Similarity to Ideal Solution) method to vary the distance (radius) the optimal location of the emergency department is obtained according to the number of hospitals that have emergency room facilities, namely Ilir Timur I District, Ilir Barat I District, Sukarami District, and Plaju District. Based on the formulation of the p-median model and the completion of the TOPSIS method, the order of Districts that have optimal locations from 18 Sub-Districts that have emergency department facilities in the City of Palembang is obtained.
Clustering addresses the problem of assigning similar objects to groups. Since the size of the clusters is often constrained in practical clustering applications, various capacitated clustering ...problems have received increasing attention. We consider here the capacitated p-median problem (CPMP) in which p objects are selected as cluster centers (medians) such that the total distance from these medians to their assigned objects is minimized. Each object is associated with a weight, and the total weight in each cluster must not exceed a given capacity. Numerous exact and heuristic solution approaches have been proposed for the CPMP. The state-of-the-art approach performs well for instances with up to 5,000 objects but becomes computationally expensive for instances with a much larger number of objects. We propose a matheuristic with new problem decomposition strategies that can deal with instances comprising up to 500,000 objects. In a computational experiment, the proposed matheuristic consistently outperformed the state-of-the-art approach on medium- and large-scale instances while having similar performance for small-scale instances. As an extension, we show that our matheuristic can be applied to related capacitated clustering problems, such as the capacitated centered clustering problem (CCCP). For several test instances of the CCCP, our matheuristic found new best-known solutions.
•We introduce a scalable matheuristic for the capacitated p-median problem.•We achieve scalability with novel problem decomposition strategies.•We introduce new large-scale test instances with up to around 500,000 objects.•Our matheuristic represents the new state-of-the-art approach for large instances.•Our matheuristic shows leading performance for other capacitated clustering problems.
The input to a PPNC instance is integers n and p, and a non-negative real weighting of the edges of the clique Kn on the vertex set {1,..., n}. We are asked to find a set of p disjoint cycles ...spanning {1,..., n} and subject to this such that the sum of the weights of the edges is minimized. We provide an efficient approximation algorithm for the metric version of this problem which has an approximation ratio of 4 if p ≤ n/5 and an approximation ratio of 51 for larger p.
For p > n/5, our algorithm uses a subroutine which approximately solves the Mod 3 T-join With Slack problem. The input to an instance of Mod k T-join with Slack consists of integers n and B, a non-negative weighting of the edges of the clique Kn, and a label l(v) from {0,1,..., k - 1} on each vertex of Kn. We are asked to find the minimum weight spanning forest F from amongst those satisfying ∑T∈F((∑v∈V(T)l(v)) mod k) ≤ B. If k = 2 and B = 0 this is the well-studied T-join problem which can be solved exactly in polynomial time.
PDF
