The Planar Two-Center and Two-Median Problems

Zvi Drezner
Zvi Drezner
The University of Michigan-Dearborn, Dearborn, Michigan
Search for more papers by this author

The University of Michigan-Dearborn, Dearborn, Michigan

Published Online:1 Nov 1984https://doi.org/10.1287/trsc.18.4.351

Abstract

We present algorithms for the solution of planar location-allocation problems with two new facilities. Euclidean distances are assumed. We address both the minimax (or “two-center”), and minisum (or “two-median”) problems. Computational results are presented.

Cited by
- Two hybrid genetic algorithms for the continuous p -centre problem
  6 January 2026 | Engineering Optimization, Vol. 3
- Prioritizing the location of vaccination centres during the COVID-19 pandemic by bike in The Netherlands
  3 March 2025 | Geospatial Health, Vol. 20, No. 1
- Dispersed starting solutions in facility location: The case of the planar p -median problem
  Computers & Operations Research, Vol. 169
- A hybrid modified PSO algorithm for the inverse p-median location problem in fuzzy random environment
  Theoretical Computer Science, Vol. 1000
- An Efficient Algorithm for the 2-Central Path Problem
  15 November 2024 | International Journal of Computational Geometry & Applications, Vol. 34, No. 01n02
- Mean–variance value at risk criterion for solving a p-median location problem on networks with type-2 intuitionistic fuzzy weights
  Journal of Computational and Applied Mathematics, Vol. 437
- A trajectory based heuristic for the planar p -median problem
  Computers & Operations Research, Vol. 158
- Fuzzy random classical and inverse median location problems
  11 April 2023 | Soft Computing, Vol. 27, No. 13
- A planar facility location–allocation problem with fixed and/or variable cost structures for rural electrification
  Computers & Operations Research, Vol. 154
- Intersecting disks using two congruent disks
  Computational Geometry, Vol. 110
- A PROBABILISTIC ℓ1 METHOD FOR CLUSTERING HIGH-DIMENSIONAL DATA
  5 April 2021 | Probability in the Engineering and Informational Sciences, Vol. 36, No. 2
- Continuous Facility Location Problems
  8 July 2022
- An Efficient Algorithm for the Proximity Connected Two Center Problem
  29 May 2022
- Intersecting Disks Using Two Congruent Disks
  30 June 2021
- Bi-level programming enabled design of an intelligent maritime search and rescue system
  Advanced Engineering Informatics, Vol. 46
- The complete vertex p-center problem
  EURO Journal on Computational Optimization, Vol. 8, No. 3-4
- Minimum Perimeter-Sum Partitions in the Plane
  6 February 2019 | Discrete & Computational Geometry, Vol. 63, No. 2
- Classical and Inverse Median Location Problems under Uncertain Environment
  11 April 2020 | Acta Mathematicae Applicatae Sinica, English Series, Vol. 36, No. 2
- A Comparison of the Effectiveness of Two Novel Clustering-Based Heuristics for the p-Centre Problem
  3 January 2020
- Where will the next emergency event occur? Predicting ambulance demand in emergency medical services using artificial intelligence
  Computers, Environment and Urban Systems, Vol. 76
- My Career and Contributions
  8 October 2019
- The Mean-Value-at-Risk Median Problem on a Network with Random Demand Weights
  8 October 2019
- Neighbourhood Reduction in Global and Combinatorial Optimization: The Case of the p-Centre Problem
  8 October 2019
- An iterative solution approach to a multi-objective facility location problem
  Applied Soft Computing, Vol. 62
- Incorporating neighborhood reduction for the solution of the planar p-median problem
  12 August 2015 | Annals of Operations Research, Vol. 258, No. 2
- A Two-echelon joint continuous-discrete location model
  European Journal of Operational Research, Vol. 262, No. 3
- Sequential location of two facilities: comparing random to optimal location of the first facility
  19 August 2014 | Annals of Operations Research, Vol. 246, No. 1-2
- New local searches for solving the multi-source Weber problem
  5 February 2015 | Annals of Operations Research, Vol. 246, No. 1-2
- An adaptive perturbation-based heuristic: An application to the continuous p-centre problem
  Computers & Operations Research, Vol. 75
- A multi-objective model for locating search and rescue boats
  European Journal of Operational Research, Vol. 254, No. 1
- Planning the City Logistics Terminal Location by Applying the Green p -Median Model and Type-2 Neurofuzzy Network
  Computational Intelligence and Neuroscience, Vol. 2016
- Solving the planar p-median problem by variable neighborhood and concentric searches
  23 April 2014 | Journal of Global Optimization, Vol. 63, No. 3
- New heuristic algorithms for solving the planar p-median problem
  Computers & Operations Research, Vol. 62
- A Heuristic for the Multisource Weber Problem with Service Level Constraints
  Prahalad Venkateshan,
  Kamlesh Mathur
  4 September 2014 | Transportation Science, Vol. 49, No. 3
- The continuous p-centre problem: An investigation into variable neighbourhood search with memory
  European Journal of Operational Research, Vol. 241, No. 3
- Investigating Metaheuristics Applications for Capacitated Location Allocation Problem on Logistics Networks
  4 December 2014
- A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables
  European Journal of Operational Research, Vol. 232, No. 2
- The planar hub location problem: a probabilistic clustering approach
  1 June 2013 | Annals of Operations Research, Vol. 211, No. 1
- Covering and piercing disks with two centers
  Computational Geometry, Vol. 46, No. 3
- A new heuristic for solving the p-median problem in the plane
  Computers & Operations Research, Vol. 40, No. 1
- Solving the multi-commodity capacitated multi-facility Weber problem using Lagrangean relaxation and a subgradient-like algorithm
  21 December 2017 | Journal of the Operational Research Society, Vol. 63, No. 6
- Minimizing the Average Distance of Separated Points on the Plane in the L 1 -Distance
  Journal of information and communication convergence engineering, Vol. 10, No. 1
- On the 2-Central Path Problem
- Bee colony optimization for the p-center problem
  Computers & Operations Research, Vol. 38, No. 10
- Finding all pure strategy Nash equilibria in a planar location game
  European Journal of Operational Research, Vol. 214, No. 1
- Solving the conditional and unconditional -center problem with modified harmony search: A real case study
  Scientia Iranica, Vol. 18, No. 4
- A multi-dimensional shooting algorithm for the two-facility location–allocation problem with dense demand
  Computers & Operations Research, Vol. 38, No. 2
- The Weiszfeld Algorithm: Proof, Amendments, and Extensions
  13 January 2011
- Continuous Center Problems
  13 January 2011
- Covering and Piercing Disks with Two Centers
- A generalized Weiszfeld method for the multi-facility location problem
  Operations Research Letters, Vol. 38, No. 3
- The big cube small cube solution method for multidimensional facility location problems
  Computers & Operations Research, Vol. 37, No. 1
- New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems
  Computers & Operations Research, Vol. 36, No. 5
- BOUNDED-VELOCITY APPROXIMATION OF MOBILE EUCLIDEAN 2-CENTRES
  20 November 2011 | International Journal of Computational Geometry & Applications, Vol. 18, No. 03
- Facility location models for distribution system design
  European Journal of Operational Research, Vol. 162, No. 1
- A Genetic Algorithm Based Approach for the Uncapacitated Continuous Location–Allocation Problem
  Annals of Operations Research, Vol. 123, No. 1-4
- A fast algorithm for the alpha-connected two-center decision problem
  Information Processing Letters, Vol. 85, No. 4
- A generalization of the rectangular bounding method for continuous location models
  Computers & Mathematics with Applications, Vol. 44, No. 1-2
- The Newton Bracketing Method for Convex Minimization
  Computational Optimization and Applications, Vol. 21, No. 2
- The Weber Problem
- Continuous Covering Location Problems
- On solving unreliable planar location problems
  Computers & Operations Research, Vol. 28, No. 4
- Randomized Algorithms for Geometric Optimization Problems
- The convergence of the Weiszfeld algorithm
  Computers & Mathematics with Applications, Vol. 40, No. 4-5
- Improvements and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem
  Jack Brimberg,
  Pierre Hansen,
  Nenad Mladenović,
  Eric D. Taillard,
  1 June 2000 | Operations Research, Vol. 48, No. 3
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
  SIAM Journal on Computing, Vol. 29, No. 3
- AN ALGORITHM FOR MINI-POWER-SUM FACILITIES LOCATION PROBLEM IN CONTINUOUS SPACE
  Journal of Architecture and Planning (Transactions of AIJ), Vol. 64, No. 521
- Efficient algorithms for geometric optimization
  1 December 1998 | ACM Computing Surveys, Vol. 30, No. 4
- Solving a Class of Two-Dimensional Uncapacitated Location-Allocation Problems by Dynamic Programming
  Jack Brimberg,
  Robert F. Love,
  1 October 1998 | Operations Research, Vol. 46, No. 5
- Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming
  Pey-Chun Chen,
  Pierre Hansen,
  Brigitte Jaumard,
  Hoang Tuy,
  1 August 1998 | Operations Research, Vol. 46, No. 4
- Kohonen maps for solving a class of location-allocation problems
  European Journal of Operational Research, Vol. 108, No. 1
- On the conditional p-median problem
  Computers & Operations Research, Vol. 22, No. 5
- Dynamic facility location: The progressive p-median problem
  Location Science, Vol. 3, No. 1
- Planar geometric location problems
  Algorithmica, Vol. 11, No. 2
- A sweepline algorithm to solve the two-center problem
  Information Processing Letters, Vol. 49, No. 4
- The conditionalp-center problem in the plane
  Naval Research Logistics, Vol. 40, No. 1
- A note on the Weber location problem
  Annals of Operations Research, Vol. 40, No. 1
- Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞-distance
  Discrete Applied Mathematics, Vol. 40, No. 3
- Algorithmic and technical improvements: Optimal solutions to the (Generalized) Multi-Weber Problem
  Papers in Regional Science, Vol. 71, No. 3
- An optimal method for solving the (generalized) multi-Weber problem
  European Journal of Operational Research, Vol. 58, No. 3
- Facility location when demand is time dependent
  Naval Research Logistics, Vol. 38, No. 5
- Towards the Solution of the (Generalised) Multi-Weber Problem
  1 September 1991 | Environment and Planning B: Planning and Design, Vol. 18, No. 3
- On weighted rectilinear 2-center and 3-center problems
  Information Sciences, Vol. 54, No. 1-2
- The weighted minimax location problem with set-up costs and extensions
  29 March 2011 | RAIRO - Operations Research, Vol. 25, No. 1
- Rectilinear m ‐Center problem
  10 December 2013 | Naval Research Logistics (NRL), Vol. 37, No. 3
- A new bounding method for single facility location models
  Annals of Operations Research, Vol. 18, No. 1
- Relaxation method for the solution of the minimax location-allocation problem in euclidean space
  Naval Research Logistics, Vol. 34, No. 6
- An Evaluation of the Dual as a Lower Bound in Facilities Location Problems
  9 July 2007 | IIE Transactions, Vol. 19, No. 2
- On the rectangularp-center problem
  Naval Research Logistics, Vol. 34, No. 2
- Bounding methods for facilities location algorithms
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 33, No. 4
- The p-cover problem
  European Journal of Operational Research, Vol. 26, No. 2

Volume 18, Issue 4

November 1984

Pages 315-414

Article Information

Metrics

Information

Published Online:November 01, 1984

Cite as

Zvi Drezner, (1984) The Planar Two-Center and Two-Median Problems. Transportation Science 18(4):351-361.

https://doi.org/10.1287/trsc.18.4.351

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

The Planar Two-Center and Two-Median Problems

Abstract

Volume 18, Issue 4

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News