TY - GEN

T1 - Metaheuristics for Finding the Stability Radius in the Bilevel Facility Location and Uniform Pricing Problem

AU - Vodyan, Maxim

AU - Panin, Artem

AU - Plyasunov, Aleksandr

N1 - The work was supported by the Russian Science Foundation (project 23-21-00424). Публикация для корректировки.

PY - 2023

Y1 - 2023

N2 - We consider a threshold stability problem for the facility location and uniform pricing problem with median-type location. In the threshold stability problem, the deviation from current customer budgets is maximized. The value of the maximum deviation is called threshold stability radius. The solution of the problem is called feasible if the leader's revenue is not less than a predetermined value (threshold) and it satisfies all the constraints of the facility location and uniform pricing problem for any deviation of budgets that does not exceed the threshold stability radius. In this paper, we develop two approximate algorithms for solving the threshold stability problem based on variable neighborhood descent (VND) heuristics. These algorithms are based on the ideas of finding optimal facility location or good approximate facility location and on the ideas of finding optimal pricing in the facility location and uniform pricing problem. The algorithms differ in the way of comparing different facility locations, which eventually leads to different estimates of the threshold stability radius. The numerical experiment has shown the efficiency of the chosen approach, both in terms of the running time of the algorithms and the quality of the obtained solutions.

AB - We consider a threshold stability problem for the facility location and uniform pricing problem with median-type location. In the threshold stability problem, the deviation from current customer budgets is maximized. The value of the maximum deviation is called threshold stability radius. The solution of the problem is called feasible if the leader's revenue is not less than a predetermined value (threshold) and it satisfies all the constraints of the facility location and uniform pricing problem for any deviation of budgets that does not exceed the threshold stability radius. In this paper, we develop two approximate algorithms for solving the threshold stability problem based on variable neighborhood descent (VND) heuristics. These algorithms are based on the ideas of finding optimal facility location or good approximate facility location and on the ideas of finding optimal pricing in the facility location and uniform pricing problem. The algorithms differ in the way of comparing different facility locations, which eventually leads to different estimates of the threshold stability radius. The numerical experiment has shown the efficiency of the chosen approach, both in terms of the running time of the algorithms and the quality of the obtained solutions.

KW - bilevel optimization

KW - facility location

KW - pricing

KW - threshold stability problem

KW - threshold stability radius

KW - variable neighborhood descent

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85175491465&origin=inward&txGid=38e6133da246238f95b6882c21e102cc

UR - https://www.mendeley.com/catalogue/d89eafc7-5fb9-306d-80c7-a975d0b10929/

U2 - 10.1109/OPCS59592.2023.10275325

DO - 10.1109/OPCS59592.2023.10275325

M3 - Conference contribution

SN - 9798350331134

T3 - Proceedings - 2023 19th International Asian School-Seminar on Optimization Problems of Complex Systems, OPCS 2023

SP - 130

EP - 135

BT - Proceedings - 2023 19th International Asian School-Seminar on Optimization Problems of Complex Systems, OPCS 2023

PB - Institute of Electrical and Electronics Engineers Inc.

ER -