Global Optimization Algorithm for the Multi-Weber Problem with Polyhedral Barriers

Kepalas, Mindaugas; Žilinskas, Julius

doi:10.15388/25-INFOR610

Informatica

Global Optimization Algorithm for the Multi-Weber Problem with Polyhedral Barriers

Volume 36, Issue 4 (2025), pp. 875–902

Mindaugas Kepalas Julius Žilinskas

https://doi.org/10.15388/25-INFOR610

Pub. online: 21 November 2025 Type: Research Article

Open Access

Received
1 August 2025

Accepted
1 November 2025

Published
21 November 2025

Abstract

In this paper, we consider the multi-Weber problem with polyhedral barriers. For this problem, a set of obstacles are introduced where travelling or placement is prohibited, which makes the distance metric non-convex and requires constructing a special graph for calculating the distances between pairs of points. For obtaining the global solution of the problem, we build a branch and bound algorithm with pruning criteria based on dividing clients into groups and analysing them separately. We have managed to obtain global solutions to several multi-Weber with polyhedral barriers problem size instances which to our knowledge have not been reported before.

References

Aloise, D., Hansen, P., Liberti, L. (2012). An improved column generation algorithm for minimum sum-of-squares clustering. Mathematical Programming, 131, 195–220.

Aneja, Y.P., Parlar, M. (1994). Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel. Transportation Science, 28(1), 70–76.

Bischoff, M., Klamroth, K. (2007). An efficient solution method for Weber problems with barriers based on genetic algorithms. European Journal of Operational Research, 177(1), 22–41.

Bischoff, M., Fleischmann, T., Klamroth, K. (2009). The multi-facility location–allocation problem with polyhedral barriers. Computers & Operations Research, 36(5), 1376–1392.

Cooper, L. (1964). Heuristic methods for location-allocation problems. SIAM Review, 6(1), 37–53.

Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271.

Drezner, Z., Klamroth, K., Schöbel, A., Wesolowsky, G. (2002). The Weber Problem. Facility Location: Applications and Theory, 1–36.

du Merle, O., Villeneuve, D., Desrosiers, J., Hansen, P. (1999). Stabilized column generation. Discrete Mathematics, 194(1), 229–237.

Gilmore, P.C., Gomory, R.E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849–859.

Hamacher, H.W., Nickel, S. (1995). Restricted planar location problems and applications. Naval Research Logistics (NRL), 42(6), 967–992.

Kepalas, M., Žilinskas, J. (2024). Solving net-constrained clustering problem. Journal of Nonlinear and Variational Analysis, 8, 987–1012.

Klamroth, K. (2002). Single Facility Location Problems with Barriers. Springer, New York.

Koenker, R. (2025). quantreg: Quantile Regression.

Krau, S. (1997). Extensions du problème de Weber. PhD thesis, École Polytechnique de Montréal.

Oğuz, M., Bektaş, T., Bennell, J.A., Fliege, J. (2016). A modelling framework for solving restricted planar location problems using phi-objects. The Journal of the Operational Research Society, 67(8), 1080–1096.

Paulavičius, R., Žilinskas, J. (2013). Simplicial Global Optimization. Springer, New York.

Rosing, K.E. (1992). An optimal method for solving the (generalized) multi-Weber problem. European Journal of Operational Research, 58(3), 414–426.

Sedgewick, R., Wayne, K. (2011). Algorithms, 4th ed. Addison-Wesley Professional, Princeton.

Sumner, M. (2025). sfdct: Constrained Triangulation for Simple Features.

Viegas, J., Hansen, P. (1985). Finding shortest paths in the plane in the presence of barriers to travel (for any lp – norm). European Journal of Operational Research, 20(3), 373–381.

Biographies

Kepalas Mindaugas

mindaugas.kepalas@mif.stud.vu.lt

M. Kepalas is a PhD student at the Institute of Data Science and Digital Technologies, Vilnius University, Lithuania. His research interests are global optimization, location problems with constraints, net-constrained clustering, mathematical programming, optimization algorithms and applications.

Žilinskas Julius

julius.zilinskas@mif.vu.lt

J. Žilinskas is a research professor and a head of Global optimization group at the Institute of Data Science and Digital Technologies, Vilnius University, Lithuania. His research interests are global optimization, parallel computing, data analysis and visualization. He published around 100 international journal papers and 4 books. He is a member of editorial boards of 10 international journals. He is a vice president of the International Society of Global Optimization.

Full article Related articles

Open access article under the CC BY license.

Keywords

multi-Weber problem with barriers clustering problems with centre location constraints global optimization

Metrics

since January 2020

Article info
views

Full article
views

PDF
downloads

XML
downloads

RSS

Authors

Abstract

References

Biographies

Export citation

Copy and paste formatted citation

Download citation in file