We study a bilevel hub location problem where on the upper level, a shipment service provider –the leader–builds a transportation network and sets the prices of shipments on each possible transportation relation. Here, the leader has to take into account the customers’ reaction — the follower — who will only purchase transport services depending on their individual budget. The objective is to maximize the generated profit from the leader’s perspective.
Since the classical hub location problem is well known to be NP-hard, we focus on the additional complexity induced by the bilevel structure. We propose an oracle-based approach that assumes availability of an algorithm for the prize-collecting variant of the hub location problem. Our main contribution is an efficient reduction of our bilevel price-setting problem to the latter, showing that the bilevel problem is not significantly harder than this. We achieve the reduction through a novel Lagrangian decomposition approach in which the optimal multipliers can be determined analytically. Moreover, we prove that strong duality holds.
Computational experiments highlight the advantages of our method, that significantly outperforms a more standard single-level reformulation.
Furthermore, the proposed algorithm can be adapted to numerous price-setting variants of classical combinatorial optimization problems, even beyond logistics.
Article