TY - JOUR

T1 - Optimization strategies for the bilevel network design problem with affine cost functions

AU - Krylatov, Alexander

AU - Raevskaya, Anastasiya

AU - Ageev, Petr

N1 - Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Nature Switzerland AG.

PY - 2023/6/1

Y1 - 2023/6/1

N2 - Today artificial intelligence systems support efficient management in different fields of social activities. In particular, congestion control in modern networks seems to be impossible without proper mathematical models of traffic flow assignment. Thus, the network design problem can be referred to as Stackelberg game with independent lower-level drivers acting in a non-cooperative manner to minimize individual costs. In turn, upper-level decision-maker seeks to minimize overall travel time in the network by investing in its capacity. Hence, the decision-maker faces the challenge with a hierarchical structure which solution important due to its influence on the sustainable development of modern large cities. However, it is well-known that a bilevel programming problem is often strongly NP-hard, while the hierarchical optimization structure of a bilevel problem raises such difficulties as non-convexity and discontinuity. The present paper is devoted to the network design problem with affine cost functions. First of all, we obtain exact optimality conditions to the network design problem in a case of a single-commodity network with non-interfering routes. Secondly, we show that obtained conditions can be exploited as optimization strategies for solving the network design problem in the case of an arbitrary network with affine cost functions. These findings give fresh managerial insights to traffic engineers dealing with network design.

AB - Today artificial intelligence systems support efficient management in different fields of social activities. In particular, congestion control in modern networks seems to be impossible without proper mathematical models of traffic flow assignment. Thus, the network design problem can be referred to as Stackelberg game with independent lower-level drivers acting in a non-cooperative manner to minimize individual costs. In turn, upper-level decision-maker seeks to minimize overall travel time in the network by investing in its capacity. Hence, the decision-maker faces the challenge with a hierarchical structure which solution important due to its influence on the sustainable development of modern large cities. However, it is well-known that a bilevel programming problem is often strongly NP-hard, while the hierarchical optimization structure of a bilevel problem raises such difficulties as non-convexity and discontinuity. The present paper is devoted to the network design problem with affine cost functions. First of all, we obtain exact optimality conditions to the network design problem in a case of a single-commodity network with non-interfering routes. Secondly, we show that obtained conditions can be exploited as optimization strategies for solving the network design problem in the case of an arbitrary network with affine cost functions. These findings give fresh managerial insights to traffic engineers dealing with network design.

KW - Affine cost functions

KW - Bilevel optimization

KW - Congestion games

KW - Network design problem

KW - Optimization strategies

UR - http://www.scopus.com/inward/record.url?scp=85143895701&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/f69f1c25-b204-3b0b-9a8a-55757dd1d1fb/

U2 - 10.1007/s10472-022-09828-9

DO - 10.1007/s10472-022-09828-9

M3 - Article

AN - SCOPUS:85143895701

VL - 91

SP - 329

EP - 347

JO - Annals of Mathematics and Artificial Intelligence

JF - Annals of Mathematics and Artificial Intelligence

SN - 1012-2443

IS - 2

ER -