1. Home
  2. Issues
  3. Volume 36, Issue 4 (2025)
  4. Global Optimization Algorithm for the Mu ...

Informatica


Global Optimization Algorithm for the Multi-Weber Problem with Polyhedral Barriers
Volume 36, Issue 4 (2025), pp. 875–902
Pub. online: 21 November 2025      Type: Research Article      Open accessOpen 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 PDF XML
Full article Related articles PDF XML

Copyright
© 2025 Vilnius University
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
121

Article info
views

81

Full article
views

56

PDF
downloads

23

XML
downloads


Share


RSS