Đang chuẩn bị liên kết để tải về tài liệu:
Some variants of reverse selective center location problem on trees under the chebyshev and hamming norms

This paper is concerned with two variants of the reverse selective center location problems on tree graphs under the Hamming and Chebyshev cost norms in which the customers are existing on a selective subset of the vertices of the underlying tree. | Yugoslav Journal of Operations Research 27 (2017), Number 3, 367–384 DOI: 10.2298/YJOR160317012E SOME VARIANTS OF REVERSE SELECTIVE CENTER LOCATION PROBLEM ON TREES UNDER THE CHEBYSHEV AND HAMMING NORMS Roghayeh ETEMAD Department of Applied Mathematics, Faculty of Basic Sciences, Sahand University of Technology, Tabriz, Iran. r etemad@sut.ac.ir Behrooz ALIZADEH* Department of Applied Mathematics, Faculty of Basic Sciences, Sahand University of Technology, Tabriz, Iran alizadeh@sut.ac.ir, brz alizadeh@yahoo.com Received: March 2016 / Accepted: June 2016 Abstract: This paper is concerned with two variants of the reverse selective center location problems on tree graphs under the Hamming and Chebyshev cost norms in which the customers are existing on a selective subset of the vertices of the underlying tree. The first model aims to modify the edge lengths within a given modification budget until a prespecified facility location becomes as close as possible to the customer points. However, the other model wishes to change the edge lengths at the minimum total cost so that the distances between the prespecified facility and the customers satisfy a given upper bound. We develop novel combinatorial algorithms with polynomial time complexities for deriving the optimal solutions of the problems under investigation. Keywords: Center Location Problems, Combinatorial Optimization, Reverse Optimization, Tree Graphs, Time Complexity. MSC: 90C27; 90B80; 90B85; 90C35. *Corresponding author 368 R. Etemad, B. Alizadeh / Reverse Selective Center Location Problem 1. INTRODUCTION Facility location problems are fundamental optimization models in operations research which are concerned with locating facilities on a system in order to serve a given set of customers in an optimal way under certain assessment criteria. In recent years, different variants of these problems have found significant interest due to their applications in theory and practice. Two widely investigated .