A Heuristic Constraint Programming Method for the p-Median Problem With Distance Constraints

Abstract

In a facility location problem, we seek to locate a set of facilities in an area, where demand points (clients) may be present, so that some criterion is optimized. A well-known facility location problem is the p-median problem, where we seek to minimize the sum of distances between demand points and their nearest facility. We consider a variant of the p-median problem where distance constraints exist between facilities and between facilities and demand points. This problem can be used to model the requirements that arise when locating semi-obnoxious facilities. We first introduce integer linear programming and constraint programming (CP) models and implement them in Gurobi and OR-Tools, respectively. Then, we describe a greedy heuristic that can be used to prune branches during a search within an incomplete CP solver. We also introduce a number of domain-specific value ordering heuristics that can be applied within such a solver. The developed method is evaluated under different problem generation models, and compared to Gurobi and OR-Tools. The results demonstrate that our method is more robust than the two complete solvers, significantly outperforming either of them in certain classes of problems, both in terms of run times and the quality of the solutions found.

Keywords

constraint programming facility location distance constraints value ordering optimization

Get full access to this article

View all access options for this article.

References

Balinski

(1965). Integer programming: Methods, uses, computations. Management Science, 12(3), 253–313. https://doi.org/10.1287/mnsc.12.3.253

Beasley

J. E.

(1985). A note on solving large p-median problems. European Journal of Operational Research, 21(2), 270–273. https://doi.org/10.1016/0377-2217(85)90040-2

Beltran

Tadonki

Vial

J. P.

(2006). Solving the p-median problem with a semi-lagrangian relaxation. Computational Optimization and Applications, 35(2), 239–260. https://doi.org/10.1007/s10589-006-6513-6

Berman

Huang

(2008). The minimum weighted covering location problem with distance constraints. Computers and Operations Research, 35(12), 356–372. https://doi.org/10.1016/j.cor.2006.03.003

Bessiere

(2006). Constraint propagation. In Foundations of artificial intelligence (Vol. 2, pp. 29–83). Elsevier. https://doi.org/10.1016/S1574-6526(06)80007-6

Boussemart

Hemery

Lecoutre

Sais

(2004). Boosting systematic search by weighting constraints. In Proceedings of the 16th European conference on artificial intelligence, ECAI’04 (pp. 146–150). IOS Press.

Brimberg

Juel

(1998). A minisum model with forbidden regions for locating a semi-desirable facility in the plane. Location Science, 6(1), 109–120. https://doi.org/10.1016/S0966-8349(98)00050-3

Cambazard

Mehta

O’Sullivan

Quesada

(2012). A computational geometry-based local search algorithm for planar location problems. In N. Beldiceanu, N. Jussien, & É. Pinson (Eds.), Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 97–112). Springer. https://doi.org/10.1007/978-3-642-29828-8_7

Carrizosa

Plastria

(1999). Location of semi-obnoxious facilities. Studies in Locational Analysis, 12(1999), 1–27. https://www.researchgate.net/profile/Frank-Plastria-2/publication/246714839_Location_of_semi-obnoxious_facilities/links/543ec2810cf21c84f23cb2e3/Location-of-semi-obnoxious-facilities.pdf

10.

Chaudhry

S. S.

McCormick

S. T.

Moon

I. D.

(1986). Locating independent facilities with maximum weight: Greedy heuristics. International Journal of Management Science, 14(5), 383–389. https://doi.org/10.1016/0305-0483(86)90079-4

11.

Church

R. L.

(2003). Cobra: A new formulation of the classic p-median location problem. Annals of Operations Research, 122, 103–120. https://doi.org/10.1023/A:1026142406234

12.

Church

R. L.

Meadows

M. E.

(1977). Results of a new approach to solving the p-median problem with maximum distance constraints. Geographical Analysis, 9(4), 364–378. https://doi.org/10.1111/j.1538-4632.1977.tb00589.x

13.

Chvatal

(1979). A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3), 233–235. https://doi.org/10.1287/moor.4.3.233

14.

Comley

W. J.

(1995). The location of ambivalent facilities: Use of a quadratic zero-one programming algorithm. Applied Mathematical Modeling, 19(1), 26–29. https://doi.org/10.1016/0307-904X(94)00004-P

15.

Cornuejols

Nemhauser

G. L.

Wolsey

L. A.

(1980). A canonical representation of simple plant location problems and its applications. SIAM Journal on Algebraic Discrete Methods, 1(3), 261–272. https://doi.org/10.1137/0601030

16.

Densham

P. J.

Rushton

(1992). Strategies for solving large location-allocation problems by heuristic methods. Environment and Planning A, 24(2), 289–304. https://doi.org/10.1068/a240289

17.

Drezner

Schöbel

(2018). The Weber obnoxious facility location model: A big arc small arc approach. Computers and Operations Research, 98, 240–250. https://doi.org/10.1016/j.cor.2018.06.006

18.

Drezner

Kalczynski

Salhi

(2019). The planar multiple obnoxious facilities location problem: A Voronoi based heuristic. Omega, 87, 105–116. https://doi.org/10.1016/j.omega.2018.08.013

19.

Fazel-Zarandi

M. M.

Beck

J. C.

(2009). Solving a location-allocation problem with logic-based benders’ decomposition. In I. P. Gent (Ed.), Principles and practice of constraint programming—CP 2009 (pp. 344–351). Springer. https://doi.org/10.1007/978-3-642-04244-7_28

20.

Guns

(2019). Increasing modeling language convenience with a universal n-dimensional array, CPpy as python-embedded example. In Proceedings of the 18th workshop on constraint modelling and reformulation at CP (Modref 2019) (Vol. 19). https://modref.github.io/papers/ModRef2019_Increasing%20modeling%20language%20convenience%20with%20a%20universal%20ndimensional%20array.pdf

21.

Gurobi Optimization, LLC (2023). Gurobi optimizer reference manual. https://www.gurobi.com.

22.

Hakimi

(1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3), 450–459. https://doi.org/10.1287/opre.12.3.450

23.

Hakimi

(1965). Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Operations Research, 13(3), 462–475. https://doi.org/10.1287/opre.13.3.462

24.

Iosif

Ploskas

Stergiou

(2024a). A heuristic constraint programming approach to the p-median problem with distance constraints. In Proceedings of the 13th Hellenic conference on artificial intelligence, SETN ’24 (Article 7, pp. 1–10). Association for Computing Machinery.

25.

Iosif

Ploskas

Stergiou

Tsouros

D. C.

(2024b). A CP/LS heuristic method for maxmin and minmax location problems with distance constraints. In P. Shaw (Ed.), 30th international conference on principles and practice of constraint programming, CP 2024, September 2–6, 2024, Girona, Spain, LIPIcs (Vol. 307, pp. 14:1–14:21). Schloss Dagstuhl—Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CP.2024.14

26.

Khumawala

B. M.

(1973). An efficient algorithm for the p-median problem with maximum distance constraints. Geographical Analysis, 5(4), 309–321. https://doi.org/10.1111/j.1538-4632.1973.tb00493.x

27.

Krarup

Pisinger

Plastria

(2002). Discrete location problems with push-pull objectives. Discrete Applied Mathematics, 123(1–3), 363–378. https://doi.org/10.1016/S0166-218X(01)00346-8

28.

Kuehn

A. A.

Hamburger

M. J.

(1963). A heuristic program for locating warehouses. Management Science, 9, 643–666. https://doi.org/10.1287/mnsc.9.4.643

29.

Mackworth

A. K.

(1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99–118. https://doi.org/10.1016/0004-3702(77)90007-8

30.

Maier

Hamacher

H. W.

(2019). Complexity results on planar multifacility location problems with forbidden regions. Mathematical Methods of Operations Research, 89, 433–484. https://doi.org/10.1007/s00186-019-00670-0

31.

Mladenović

Brimberg

Hansen

Moreno-Pérez

J. A.

(2007). The p-median problem: A survey of metaheuristic approaches. European Journal of Operational Research, 179(3), 927–939. https://doi.org/10.1016/j.ejor.2005.05.034

32.

Moon

D. I.

Chaudhry

S. S.

(1984). An analysis of network location problems with distance constraints. Management Science, 30(3), 290–307. https://doi.org/10.1287/mnsc.30.3.290

33.

Moon

I. D.

Papayanopoulos

(1991). Minimax location of two facilities with minimum separation: Interactive graphical solutions. Journal of the Operations Research Society, 42, 685–694. https://doi.org/10.1057/jors.1991.134

34.

Orloff

C. S.

(1977). A theoretical model of net accessibility in public facility location. Geographical Analysis, 9, 244–256. https://doi.org/10.1111/j.1538-4632.1977.tb00577.x

35.

Ortigosa

P. M.

Hendrix

E. M.

Redondo

J. L.

(2015). On heuristic bi-criterion methods for semi-obnoxious facility location. Computational Optimization and Applications, 61, 205–217. https://doi.org/10.1007/s10589-014-9709-1

36.

O.-T. Development Team (2024)OR-Tools, CP-SAT solver. https://developers.google.com/optimization/cp/cp-solver.

37.

Ploskas

Stergiou

(2022). Integer programming models for the semi-obnoxious p-median problem. https://arxiv.org/abs/2207.05590.

38.

Ploskas

Stergiou

Tsouros

D. C.

(2023). The p-dispersion problem with distance constraints. In R. H. C. Yap (Ed.), 29th International conference on principles and practice of constraint programming (CP 2023), Leibniz International Proceedings in Informatics (LIPIcs) (Vol. 280, pp. 30:1–30:18). Schloss Dagstuhl—Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CP.2023.30

39.

ReVelle

C. S.

Swain

R. W.

(1970). Central facilities location. Geographical Analysis, 2(1), 30–42. https://doi.org/10.1111/j.1538-4632.1970.tb00142.x

40.

Rosing

K. E.

ReVelle

Rosing-Vogelaar

(1979). The p-median and its linear programming relaxation: An approach to large problems. Journal of the Operational Research Society, 30(9), 815–823. https://doi.org/10.1057/jors.1979.192

41.

Rossi

Van Beek

Walsh

(2006). Handbook of constraint programming. Elsevier.

42.

Sabin

Freuder

E. C.

(1994). Contradicting conventional wisdom in constraint satisfaction. In A. Borning (Ed.), Principles and practice of constraint programming (pp. 10–20). Springer. https://doi.org/10.1007/3-540-58601-6_86

43.

Sorkhabi

S. Y. D.

Romero

D. A.

Beck

J. C.

Amon

C. H.

(2018). Constrained multi-objective wind farm layout optimization: Novel constraint handling approach based on constraint programming. Renewable Energy, 126(C), 341–353. https://doi.org/10.1016/j.renene.2018.03.053

44.

Tansel

B. C.

Francis

R. L.

Lowe

T. J.

Chen

(1982). Duality and distance constraints for the nonlinear p-center problem and covering problem on a tree network. Operations Research, 30(4), 725–744. https://doi.org/10.1287/opre.30.4.725

45.

Tutunchi

G. K.

Fathi

(2019). Effective methods for solving the bi-criteria p-center and p-dispersion problem. Computers & Operations Research, 101, 43–54. https://doi.org/10.1016/j.cor.2018.08.009

46.

Welch

Salhi

(1997). The obnoxious p facility network location problem with facility interaction. European Journal of Operations Research, 102, 302–319. https://doi.org/10.1016/S0377-2217(97)00111-2

47.

Yapicioglu

Smith

A. E.

Dozier

(2007). Solving the semi-desirable facility location problem using bi-objective particle swarm. European Journal of Operational Research, 177(2), 733–749. https://doi.org/10.1016/j.ejor.2005.11.020