This study addresses the bilevel network design problem (NDP) with congestion. The upper-level decision-maker (a network designer) selects a set of arcs to add to an existing transportation network, while the lower-level decision-makers (drivers) respond by choosing routes that minimize their individual travel times, resulting in user equilibrium. In this work, we propose two novel single-level reformulations: one based on strong duality and the other based on the value function of the lower-level problem. Unlike existing approaches in the literature, which are specialized for optimizing the total travel time of all drivers, our approach is flexible and can optimize other metrics related to individual travel times or fairness. We discuss the differences between the two reformulations, as well as their computational performance on academic test instances of the NDP. We then apply our methods to the EV charging station capacity expansion problem. We define a metric, the cost of sustainability, to measure the service quality experienced by individual EV drivers, and optimize the charging station locations to improve this metric. We present the results of experiments using the road network in Quebec, including public fast EV charging stations.
Article