Mathematical models and search algorithms for the capacitated p-center problem
From MaRDI portal
Publication:3386776
Abstract: The capacitated p-center problem requires to select p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. The problem is well known in the field of facility location, because of the many applications that it can model. In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems. We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0-1 disjunction and the solution of subset sum problems. We also develop an alternative search strategy that finds a balance between the traditional sequential search and binary search. This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search. We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets. All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3038 vertices.
Recommendations
- An exact algorithm for the capacitated vertex \(p\)-center problem
- The capacitated single-source \(p\)-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique
- Minimax models for capacitated \(p\)-center problem in uncertain environment
- A new formulation and resolution method for the \(p\)-center problem
- A maximal client coverage algorithm for the \(p\)-center problem
Cites work
- scientific article; zbMATH DE number 1746287 (Why is no real title available?)
- scientific article; zbMATH DE number 821272 (Why is no real title available?)
- A Best Possible Heuristic for the k-Center Problem
- A branch decomposition algorithm for the \(p\)-median problem
- A branch‐and‐price algorithm for the capacitated p‐median problem
- A column generation approach to capacitated \(p\)-median problems
- A cut and branch approach for the capacitated \(p\)-median problem based on Fenchel cutting planes
- A heuristic for the p-center problem in graphs
- A new formulation and resolution method for the \(p\)-center problem
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- An exact algorithm for the capacitated vertex \(p\)-center problem
- An implementation of exact knapsack separation
- Approximation algorithms for the \(k\)-center problem: an experimental evaluation
- Bee colony optimization for the \(p\)-center problem
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Capacitated p-center problem with failure foresight
- Disjunctive Programming
- Double bound method for solving the p-center location problem
- Fenchel Cutting Planes for Integer Programs
- Formulations and valid inequalities for the heterogeneous vehicle routing problem
- Generating Fenchel Cutting Planes for Knapsack Polyhedra
- Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent
- LP models for bin packing and cutting stock problems
- Lagrangean duals and exact solution to the capacitated \(p\)-center problem
- Large-scale local search heuristics for the capacitated vertexp-center problem
- Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
- Location science
- New relaxation-based algorithms for the optimal solution of the continuous and discrete \(p\)-center problems
- New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
- Solution methods for thep-median problem: An annotated bibliography
- Solving large \(p\)-median problems with a radius formulation
- Solving thep-Center problem with Tabu Search and Variable Neighborhood Search
- Technical Note—A Polynomial Algorithm for the Equal Capacity p-Center Problem on Trees
- The m-Center Problem
Cited in
(15)- Exploiting flat subspaces in local search for \(p\)-center problem and two fault-tolerant variants
- The stratified \(p\)-center problem
- A maximal client coverage algorithm for the \(p\)-center problem
- A constructive heuristic for the uniform capacitated vertex \(k\)-center problem
- Large-scale local search heuristics for the capacitated vertexp-center problem
- Exact solution approaches for the discrete α‐neighbor p‐center problem
- A scaleable projection-based branch-and-cut algorithm for the \(p\)-center problem
- Lagrangean duals and exact solution to the capacitated \(p\)-center problem
- An exact framework for the discrete parallel machine scheduling location problem
- The multi-period \(p\)-center problem with time-dependent travel times
- Minimax models for capacitated \(p\)-center problem in uncertain environment
- The capacitated single-source \(p\)-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique
- Arc flow formulations based on dynamic programming: theoretical foundations and applications
- Dynamically second-preferred \(p\)-center problem
- An exact algorithm for the capacitated vertex \(p\)-center problem
This page was built for publication: Mathematical models and search algorithms for the capacitated \(p\)-center problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386776)
