The network 1-median problem with discrete demand weights and traveling times

Document Type : Research Article

Authors

• M. Abareshi ¹
• M. Zaferanieh ²

¹ Hakim Sabzevari University, Sabzevar, Iran

² Hakim Sabzevari University, Sabzevar, Iran.

10.22067/ijnao.v9i1.68851

Abstract

In this paper, the 1-median location problem on an undirected network with discrete random demand weights and traveling times is investigated. The objective function is to maximize the probability that the expected sum of weighted distances from the existing nodes to the selected median does not exceed a prespecified given threshold. An analytical algorithm is proposed to get the optimal solution in small-sized networks. Then, by using the centrallimit theorem, the problem is studied in large-sized networks and reduced to a nonlinear problem. The numerical examples are given to illustrate the efficiency of the proposed methods.

Keywords

• Facility location, 1-median problem
• probabilistic weights
• probabilistic traveling times

20.1001.1.24236977.2019.9.1.4.7

---

References

1. Berman, O., Hajizadeh, I. and Krass, D. The maximum covering problem with travel time uncertainty, IIE Transactions, 45 (2013), 81–96.

2. Berman, O. and Wang, J. Probabilistic location problems with discrete demand weights, Networks, 44 (2004), 47–57.

3. Berman, O. and Wang, J. The network p-median problem with discrete probabilistic demand weights, Computers and Operations Research, 37(2010), 1455–1463.

4. Bieniek, M. A note on the facility location problem with stochastic demands, Omega, 55 (2015), 53–60.

5. Frank, H. Optimum locations on a graph with probabilistic demands, Operations Research, 14 (1966), 409–421.

6. Frank, H. Optimum locations on graphs with correlated normal demands, Operations Research, 15 (1967), 552–557.

7. Gavish, B. and Sridhar, S. Computing the 2-median on tree networks in O(n log n) time, Networks, 26 (1995), 305–317.

8. Gray, M.R. and Johnson D.S. Computers and intractability: A guide to the theory of Np-completeness W. H. Freeman. New York, 1979.

9. Goldman, A.J. Optimal center location in simple networks, Transportation Science, 5 (1971), 212–221.

10. Hakimi, S.L. Optimal locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12 (1964), 450–459.

11. Handler, G.Y. and Mirchandani, P.B. Location on networks: theory and algorithm, The MIT Press, Cambridge, 1979.

12. Kariv, O. and Hakimi, S.L. An algorithmic approach to network location problems. Part II: p-medians, SIAM Journal on Applied Mathematics, 37 (1979), 539–560.

13. Mirchandani, P.B. and Odoni, A.R. Location of medians on stochastic networks, Transportation Science, 13 (1979), 85–97.

14. Minieka, E. Anticenters and Antimedians of a Network, Networks, 13(1983), 359–365.

15. Nocedal, J. and Wright, S.J. Numerical Optimization, Springer-Verlag, New York, 2006.

16. Puga, M.S and Tancrez, J.S. A heuristic algorithm for solving large location-inventory problems with demand uncertainty, European Journal of Operational Research, 259 (2017), 413–423.

17. Stancu-Minasian, I.M. Fractional Programming: Theory, Methods and Applications, Springer, Netherlands, 1997.

18. Tamir, A. An O(pn2) algorithm for the p-median and related problems on tree graphs, Operations Research Letters, 19 (1996), 59–64.