The inverse 1-median location problem on uncertain tree networks with tail value at risk criterion

• Published in: Information sciences 2020-01, Vol.506, p.383-394
• Main Authors: Soltanpour, Akram, Baroughi, Fahimeh, Alizadeh, Behrooz
• Format: Article
• Language: English
• Subjects: Inverse optimization; Median location; Tail value at risk; Time complexity; Uncertain programming
• ISSN: 0020-0255; 1872-6291
• DOI: 10.1016/j.ins.2019.08.018

•A necessary and sufficient condition for the α-1-median is obtained.•The uncertain inverse 1-median problem is transformed into a programming model with deterministic constraints.•A new model for the problem is developed.•An O(nlog n) time algorithm for the problem under weighted l1 norm is proposed. In an inverse 1-median location problem on a tree network, the goal is to modify the vertex weights of the underlying tree network at the minimum total cost such that a predetermined vertex becomes the 1-median. This paper investigates the case that the vertex weights and modification costs are considered as uncertain variables. We first obtain a necessary and sufficient condition for the α-1-median on uncertain trees. Based on this condition, we transform the problem into a linear programming model with deterministic constraints. Finally, we consider the proposed model with tail value at risk objective under the weighted l1 norm and present a solution algorithm for the problem with time complexity of O(nlog n).