Discrete mathematics and mathematical cybernetics

Upper bound procedure for dynamic competitive facility location problem with profit targeting

V. L. Beresnev, A. A. Melnikov

Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: We consider a dynamic competitive facility location problem, where two competing parties (Leader and Follower) aim to capture customers in each time period of the planning horizon and get a profit from serving them. The Leader's objective function represents their regret composed of the cost of open facilities and a total shortage of income computed with respect to some predefined target income values set for each of the time periods. The Follower's goal is to maximize their profit on the whole planning horizon. In the model, the Leader makes their location decision once at the beginning of the planning horizon, while the Follower can open additional facilities at any time period.
In the present work, a procedure computing upper bounds for the Leader's objective function is proposed. It is based on using a high-point relaxation of the initial bi-level mathematical program and strengthening it with additional constraints (cuts). New procedures of generating additional cuts in a form of c-cuts and d-cuts, which are stronger than the ones proposed in earlier works, are presented.

Keywords: Competitive facility location, dynamic decision-making model, bi-level programming.

UDC: 519.8

MSC: 90B80

Received August 8, 2024, published November 1, 2024

Language: English

DOI: 10.33048/semi.2024.21.063