The most probable allocation solution for the p-median problem

Document Type : Research Article

Author

• M. Zaferanieh

Department of Applied Mathematics, Faculty of Mathematics and computer sciences, Hakim Sabzevari University, Sabzevar, Iran.

10.22067/ijnao.v10i2.84892

Abstract

The most important purpose in location problems is usually to locate some facilities and allocate the demands of nodes so that the total transportation cost of the network is minimized. However, in real networks, there are some other influencing factors, aside from the transportation costs, for determin ing the allocation mode. In this paper, a minimum information approach is applied to the capacitated p-median problem to estimate the most likely allo cation solution based on some prior probabilities. Indeed, the most probable solution is achieved through minimizing a log-based objective function, while the total transportation cost should be less than or equal to a predetermined budget. The problem is solved by using a decomposition method combined with the Karush–Kuhn–Tucker optimality conditions, and some numerical examples are provided to verify the added value of the proposed model and solution approach.

Keywords

• Network
• Location problems
• Capacitated p-median
• Benders decomposition
• Minimum information

20.1001.1.24236977.2020.10.2.8.0

---

References

1. Abareshi, M. and Zaferanieh, M. A bi-level capacitated p-median facility location problem with the most likely allocation solution, Transport. Res. B-Meth. 123 (2019) 1–20.

2. Abareshi, M., Zaferanieh, M. and Keramati, B. Path flow estimator in an entropy model using a nonlinear L-shaped algorithm, Netw. Spat. Econ. 17(1) (2017) 293–315.

3. Bagajewicz, M.J. and Manousiouthakis, V. On the generalized Benders decomposition, Comput. Chem. Eng. 15(10) (1991) 691–700.

4. Bazaraa, M.S., Sherali H.D. and Shetty C.M. Nonlinear programming: Theory and algorithms, John Wiley and Sons; 2013 .

5. Beltran, C., Tadonki, C. and Vial, J.P. Solving the p-median problem with a semi-Lagrangian relaxation, Comput. Optim. Appl. 35(2) (2006) 239–260.

6. Benders, J.F. Partitioning procedures for solving mixed-variables program ming problems, Comput. Manag. Sci. 2(1) (2005) 3–19.

7. Bisschop, J. AIMMS optimization modeling, Lulu. com. 2006.

8. Ceselli, A. and Righini, G. A branch-and-price algorithm for the capacitated p-median problem, Networks. 45(3) (2005) 125–142.

9. Cover, T.M. Elements of information theory, John Wiley & Sons, 1999.

10. Diaz, J.A. and Fernandez, E. Hybrid scatter search and path relinking for the capacitated p-median problem, Eur. J. Oper. Res. 169(2) (2006) 570–785.

11. Dolan, E.D. and More, J.J. Benchmarking optimization software with performance profiles, Math. Program. 91(2) (2002) 201–213.

12. Fleszar, K. and Hindi, K.S. An effective VNS for the capacitated p-median problem, Eur. J. Oper. Res. 191(3) (2008) 612–622.

13. Floudas, C.A., Aggarwal, A. and Ciric, A.R. Global optimum search for nonconvex NLP and MINLP problems, Comput. Chem. Eng. 13(10) (1989) 11171-1132.

14. Garey, M.R. and Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, First Edition, W. H. Freeman, 1979.

15. Geoffrion, A.M. Duality in nonlinear programming: A simplified applications-oriented development, SIAM Rev. 13(1) (1971) 1–37.

16. Geoffrion, A.M. Generalized benders decomposition, J. Optim. Theory App. 10(4) (1972) 237–260.

17. Goldengorin, B., Krushinsky, D. and Pardalos, P.M. Cell formation in industrial engineering, New York, NY: Springer; 2013.

18. Hakimi, S.L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems,Oper. Res. 13(3) (1965) 462–475.

19. Jaynes, E.T. Information theory and statistical mechanics, Phys. Rev. 106(4) (1957) 620.

20. Kariv, O. and Hakimi, S.L. An algorithmic approach to network location problems II: the p-medians, SIAM J. Appl. Math. 37 (1979) 539–560.

21. Lorena, L.A. and Senne, E.L. A column generation approach to capacitated p-median problems, Comput. Oper. Res. 31(6) (2004) 863–876.

22. McFadden, D.L. Conditional logit analysis of qualitative choice behaviour, Zarembka, P. (ed.): Frontiers in Econometrics, Wiley, New York, 1973, 105–142.

23. Maniezzo, V., Mingozzi, A. and Baldacci, R. A bionomic approach to the capacitated p-median problem, J. Heuristics. 4(3) (1998) 263–280.

24. Neebe, A.W. Branch and Bound Algorithm for the p-Median Transportation Problem, J. Oper. Res. Soc. 29(10) (1978) 989–995.

25. Reese, J. Solution methods for the p-median problem: An annotated bibliography, Networks. 48(3) (2006) 125–142.

26. ReVelle, C.S. and Swain, R.W. Central facilities location, Geogr. Anal. 2(1) (1970) 30–42.

27. Shamsipoor, H., Sandidzadeh, M.A. and Yaghini, M. Solving capacitated p-median problem by a new structure of neural network, Int. J. Ind. Eng Theory. 19(8) (2012) 305–319.

28. Snickars, F. and Weibull, J.W. A minimum information principle: Theory and practice, Reg. Sci. Urban Econ. 7(1-2) (1977) 137–168.

29. Sule, D.R. Manufacturing facilities: Location, planning, and design, CRC press; 2008.

30. Tamir, A. An O (pn2) algorithm for the p-median and related problems on tree graphs, Oper. Res. Lett. 19(2) (1996) 59–64.

31. Teye, C., Bell, M.G. and Bliemer, M.C. Locating urban and regional container terminals in a competitive environment: An entropy maximising approach, Transp. Res. Proc. 23 (2017) 208–227.

32. Teye, C., Bell, M.G. and Bliemer, M.C.Entropy maximising facility lo cation model for port city intermodal terminals, Transp. Res. E Logist. Transp. Rev. 100 (2017) 1–6.

33. Teye, C., Bell, M.G. and Bliemer, M.C. Urban intermodal terminals: The entropy maximising facility location problem, Transport. Res. B-Meth. 100 (2017) 64–81.

34. Van Zuylen, H.J. and Willumsen, L.G. The most likely trip matrix estimated from traffic counts, Transport. Res. B-Meth. 14(3) (1980) 281–293.