Inverse 2-Center Location Problem for Unweighted Tree Networks (A Case Study)

Document Type : Research Paper

Authors

Department of Industrial Engineering, University of Bojnourd, North Khorasan, Iran

Abstract

This paper studies the inverse 2-center location problem by increasing and decreasing the edge length on unweighted tree networks. The goal is to increase and decrease the edge lengths at minimum total cost subject to the given modification bounds such that the predetermined vertices becomes absolute 2-center. In order to demonstrate the practical application of this issue, we consider Bojnourd urban network and two important fire stations of the city as center locations. Moreover, an example is generated for computational analysis. Results show that when the predetermined vertices are close to the ends of the tree, higher cost will be imposed. Yet, in most cases, this condition is impossible.

Keywords

Main Subjects

References

1. Hakimi, S. L. (1965). "Optimum distribution of switching centers in a communication network and some related graph theoretic problems." Operations Research, Vol. 13, No. 3, pp. 462-475.
2. Daskin, M. (1997). Network and discrete location:Modeles, algorithms and applications. Wiley, New York.
3. Drezner, Z., Hamacher, H. W. (Eds.). (2001). Facility location: applications and theory. Springer Science and Business Media.‌
‌4. Love, R. F., Morris, J. G., and Wesolowsky, G. O. (1988). Facilities location. Chapter, 3, pp. 51-60.‌
5. Burton, D., and Toint, P. L. (1992). "On an instance of the inverse shortest paths problem." Mathematical Programming, Vol. 53, No. 1, pp. 45-61.‌
6. Heuberger, C. (2004). "Inverse combinatorial optimization: A survey on problems, methods, and results." Journal of combinatorial optimization, Vol. 8, No. 3, pp. 329-361.
7. Cai, M. C., Yang, X. G., and Zhang, J. Z. (1999). "The complexity analysis of the inverse center location problem." Journal of Global Optimization,‌ Vol. 15, No. 2, pp. 213-218.
8. Yang, X., and Zhang, J. (2008). "Inverse center location problem on a tree." Journal of Systems Science and Complexity, Vol. 21, No. 4, pp. 651–664.
9. Burkard, R. E., Pleschiutschnig, C., and Zhang, J. (2004). "Inverse median problems." Discrete Optimization, Vol. 1, No. 1, pp. 23-39.
10. Burkard, R. E., Pleschiutschnig, C., and Zhang, J. (2008). "The inverse 1-median problem on a cycle." Discrete Optimization, Vol. 5, No. 2, pp. 242-253.
11. Alizadeh, B., Burkard, R. E., and Pferschy, U. (2009). "Inverse 1-center location problems with edge length augmentation on trees." Computing, Vol. 86, No. 4, pp. 331-343.‌
12. Alizadeh, B., Burkard, R. E. (2011). "Combinatorial algorithms for inverse absolute and vertex 1‐center location problems on trees." Networks, Vol. 58, No. 3, pp. 190-200.
13.Hartman, J. M., and Kincaid, R. K. (2014). "P-Median Problems with Edge Reduction." Systems and Information Engineering Design Symposium, pp. 159-161.
14. Nguyen, K. T., Sepasian, A. R. (2016). "The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance."  Combinatorial Optimization, Vol. 32, No. 3, pp. 872-884.
15. Nguyen, K. T., Chassein, A. (2015). "The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance." European Journal of Operational Research, Vol. 247, No. 3, pp. 774-781.
16. Nguyen, K. T., and Anh, L. Q. (2015). "Inverse k-centrum problem on trees with variable vertex weights." Mathematical Methods of Operations Research, Vol. 82, No. 1, pp. 19-30.
17. Nguyen, K. T. (2016). "Reverse 1-center problem on weighted trees." Optimization, ‌Vol. 65, No. 1, pp. 253-264.
18. Wolsey, L., Nemhauser, G. (1999). "Integer and Combinatorial Optimization."
19.Rashidifard, N., et al., (2014). "Optimal locate fire stations in urban traffic networks to aid the earthquake (Case study: Dehdasht)." Scientific- Research Quarterly of Geograghical data (SEPEHR), Article 6, Vol. 23, pp. 48-53, (In Persian).
Advances in Industrial Engineering
Volume 52, Issue 1
April 2018
Pages 37-48

Files

Share

How to cite

Statistics