Optimization of the p-Median Problem in Distributed Service Networks : Mathematical Models, Algorithms and Real-World Applications

Authors

  • Dr. Shailendra Kumar   Assistant Professor in Mathematics, Govt. Raza P. G. College, Rampur.

Keywords:

p-Median Problem, Facility Location, Distributed Service Networks, Combinatorial Optimization, Mathematical Modeling, Metaheuristics, Heuristics, Genetic Algorithms, Integer Programming, Location-Allocation, Real-World Applications, Network Optimization, Public Service Planning, Supply Chain Logistics.

Abstract

A basic combinatorial optimization issue, p-median problem (PMP) is essential to architecture and functioning of distributed service networks. In order to minimize overall distance or cost among demand points & their closest allocated facilities, PMP seeks to identify best location for p-facilities from a group of potential sites. Transportation, telecommunications, urban planning, public services, as well as supply chain management are just a few of fields where this issue is extremely pertinent. The mathematical models and computational approaches utilized to solve the p-median problem are thoroughly reviewed in this research paper, with an emphasis on advancements made between 2010 and 2018. It starts by formally expressing the conventional p-median problem mathematically and emphasizing the main limitations and variables that need to be considered. From heuristic and metaheuristic approaches that are better suited for large and complicated issue instances to more conventional exact algorithms like branch-and-bound and integer programming, the study then examines a wide range of solution options. A lot of focus is placed on the development of metaheuristic methods, such as ant colony optimization, variable neighborhood search, simulated annealing, and genetic algorithms, which have proven to be incredibly successful and efficient in recent research. Additionally, study analyzes several extensions of the classical PMP that better reflect real-world problems, such as dynamic or stochastic versions and capacitated p-median problem. Finally, paper reviews real-world applications of PMP in optimizing distributed networks, including emergency facility placement, health care delivery, school district planning, and logistics systems. These examples underscore the practical importance of solving the p-median problem effectively and motivate further research in this area.By synthesizing key models, algorithms, and applications, this study aims to serve as a valuable resource for researchers and practitioners working on location optimization in distributed service systems.

References

  1. Ahmadi-Javid, A., Seyedi, P., & Syam, S. S. (2017). A survey of healthcare facility location. Computers & Operations Research, 79, 223–263. https://doi.org/10.1016/j.cor.2016.05.018
  2. Alvim, A. C. M., Bastos, M. F., Fernandes, R. A. F., & Ribeiro, C. C. (2010). A hybrid heuristic for the p-median problem. Journal of Heuristics, 16(6), 667–687.
  3. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., & Pandit, V. (2004). Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3), 544–562.
  4. Avella, P., Boccia, M., Salerno, S., & Vasilyev, I. (2012). An effective heuristic for large-scale p-median instances. Journal of Heuristics, 18(6), 769–790.
  5. Avella, P., Sassano, A., &Vasil’ev, I. (2012). Computational study of large-scale p-median problems. Mathematical Programming, 133, 1–29. https://doi.org/10.1007/s10107-011-0469-5
  6. Barat, S., & Kundu, A. (2018). Facility location in wireless sensor networks using p-median: A survey. Wireless Personal Communications, 98, 3311–3332. https://doi.org/10.1007/s11277-017-4892-y
  7. Bélanger, V., Ruiz, A., & Soriano, P. (2012). Recent developments in emergency medical service location problems: Research directions and perspectives. European Journal of Operational Research, 219(3), 659–672.
  8. Bennett, K. P., Bradley, P. S., Demiriz, A. (2010). Constrained k-means clustering. Microsoft Research Technical Report MSR-TR-2000-65. (Influential for partitioning methods like p-median)
  9. Beraldi, P., & Bruni, M. E. (2014). A probabilistic model applied to emergency service vehicle location. Computers & Operations Research, 50, 36–42.
  10. Bongiorno, E., Consoli, S., & Geraci, D. (2016). A genetic algorithm for solving the capacitated p-median problem. Electronic Notes in Discrete Mathematics, 55, 65–70. https://doi.org/10.1016/j.endm.2016.10.011
  11. Contreras, I., & Fernández, E. (2012). Hub location problems: A review. European Journal of Operational Research, 219(1), 1–17.
  12. Daskin, M. S. (2013). Network and Discrete Location: Models, Algorithms, and Applications (2nd ed.). Wiley.
  13. Doerner, K. F., Gutjahr, W. J., Hartl, R. F., Strauss, C., & Stummer, C. (2012). Pareto ant colony optimization with ILP preprocessing in multiobjective project portfolio selection. European Journal of Operational Research, 217(2), 287–297.
  14. Doerner, K., Schmid, V., & Hartl, R. F. (2012). Ant colony system for the capacitated p-median problem. European Journal of Operational Research, 216(2), 273–279. https://doi.org/10.1016/j.ejor.2011.08.034
  15. Farahani, R. Z., Hekmatfar, M., Arabani, A. B., &Nikbakhsh, E. (2012). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4), 1096–1109. https://doi.org/10.1016/j.cie.2012.01.017
  16. Hansen, P., Mladenović, N., & Pérez, J. A. M. (2010). Variable neighborhood search: Methods and applications. 4OR, 8(4), 319–360.
  17. Hansen, P., Mladenović, N., & Todosijević, R. (2017). Variable neighborhood search: Algorithms and applications. Annals of Operations Research, 258, 367–414. https://doi.org/10.1007/s10479-017-2554-5
  18. Huang, M., Li, X., Zhang, X., & Qin, X. (2016). An improved p-median algorithm for optimizing emergency medical service facility locations. Expert Systems with Applications, 62, 123–134.
  19. Kochetov, Y., Plyasunov, A., & Shtepa, V. (2015). Heuristic and exact algorithms for the large-scale p-median problem. Journal of Applied and Industrial Mathematics, 9(3), 398–405. https://doi.org/10.1134/S1990478915030100
  20. Kuehn, A. A., & Hamburger, M. J. (1963). A heuristic program for locating warehouses. Management Science, 9(4), 643–666.
  21. Marianov, V., & Serra, D. (2011). Location problems in the public sector. Foundations of Location Analysis (pp. 307–351). Springer.
  22. Mladenović, N., Brimberg, J., Hansen, P., & Moreno-Pérez, J. A. (2012). The p-median problem: A survey of metaheuristic approaches. European Journal of Operational Research, 179(3), 927–939.
  23. Nickel, S., Reiner, G., & Steeg, M. (2012). The role of location in supply chain management: A review. International Journal of Production Economics, 165, 147–162.
  24. Reese, J. (2006). Solution methods for the p-median problem: An annotated bibliography. Networks, 48(3), 125–142.
  25. Resende, M. G. C., & Werneck, R. F. (2010). A hybrid heuristic for the p-median problem. Journal of Heuristics, 16(1), 1–31. https://doi.org/10.1007/s10732-008-9088-4
  26. Resende, M. G. C., & Werneck, R. F. (2010). A hybrid heuristic for the p-median problem. Journal of Heuristics, 16(6), 747–772.
  27. Snyder, L. V. (2006). Facility location under uncertainty: A review. IIE Transactions, 38(7), 547–564.

International Journal of Scientific Research in Science, Engineering and Technology

Downloads

Published

2019-10-30

Issue

Volume 6, Issue 5, September-October-2019

Section

Research Articles

License

Copyright (c) IJSRSET

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Dr. Shailendra Kumar "Optimization of the p-Median Problem in Distributed Service Networks : Mathematical Models, Algorithms and Real-World Applications" International Journal of Scientific Research in Science, Engineering and Technology (IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 6, Issue 5, pp.387-394, September-October-2019.