On pricing-based equilibrium for network expansion planning. A multi-period bilevel approach under uncertainty

This study focuses on the development of a mixed binary primal-dual bilinear model for multi-period bilevel network expansion planning under uncertainty, where pricing-based equilibrated strategic and operational decisions are to be made. The periodwise dependent parameters’ uncertainty is represented by a finite set of scenarios. Pricing-based equilibrium is required in the models to be optimized at the nodes of a multi-period scenario tree. Given the size of the models, it is unrealistic to seek an optimal solution. Several versions of a Stochastic Nested Decomposition matheuristic algorithm are presented for problem solving. Additionally, an approach based on a stagewise-related Stochastic Lagrangean Decomposition is also considered together with a Frank-Wolfe Progressive Hedging-based algorithm. The state step variables device is key for the performance of both approaches. The solution’s optimality gap is computed for three out of the four solution providers that are presented. An extension of the Toll Assignment Problem is considered as a pilot case. A broad computational experience is reported.