Novel solution methods for bilevel network design problems and their application

RWTH Publications (RWTH Aachen)

Abstract

Network Design Problems (NDPs) are among the fundamental optimization problem classesas they combine strategic site planning with subsequent operational tasks in a single integratedmodel. NDPs are often modeled and solved using Mixed-Integer Programming (MIP)techniques, which offer the flexibility to adjust existing models while leveraging decades ofalgorithmic development. Numerous real-world applications in transportation, logistics, andmanufacturing have been solved this way. In such classical applications, the strategic networkdesign and the operational routing tasks are performed by the same entity. However, manyother settings violate this assumption. Examples include the Transit Network Design Problem(TNDP), where an operator designs a transit network to, e.g., pursue profit or sustainabilitywhile users minimize travel time, and market contexts where operators build networks to offerservices used by firms that run operations.The subclass of NDP that captures such non-cooperative interactions between the involvedactors is Bilevel Network Design Problem (BNDP). A BNDP consists of a network operator,referred to as the first level, and one or more agents who react to the operator’s decisionsby solving the associated operational tasks, collectively referred to as the second level. Theobjective is to determine the operator’s best decision subject to its own side constraints aswell as the non-cooperative behavior of the second level. The presence of an independentsecond-level objective substantially increases complexity, which makes BNDP notoriously hardto solve. Hence, scalable exact solution methods for real-world applications remain scarce inthe literature.Against this background, this dissertation develops new MIP-based solution methods forBNDP and provides evidence of their scalability by applying them to real-world applications.The thesis comprises a Preface that reviews the existing literature and summarizes the maincontributions, and a cumulative part containing six scientific papers. The cumulative part is organizedinto three parts. The first part consists of two papers that study the structure of binaryvalue functions — a modeling concept that arises naturally in BNDP. We analyze how thesevalue functions can be approximated using linear constraints, including methods for transferringapproximation guarantees. Moreover, we present an automated framework for generating cutcoefficients. We further introduce a novel concept of chained value functions and extend theautomated generation procedure to them, thereby enabling their use without problem-specificknowledge, making them accessible to practitioners who wish to solve their applications withoutdeveloping complex solution algorithms. Computational experiments show that the resulting algorithms outperform state-of-the-art bilevel solvers on diverse BNDP instances by an orderof magnitude.The second part consists of three papers in which we focus on TNDP. In the third paper, wepropose a novel enumeration-based preprocessing technique that yields tractable, compact MIPformulations for this problem class. We compare our approach with multiple MIP models fromthe literature and demonstrate its computational superiority for a large subclass of TNDP. Inthe papers four and five, we apply the developed model to two applications in sustainable transportation.The fourth paper addresses the planning of mobility hubs, i.e., facilities combiningmultiple mobility modes to simplify transfers and enable multi-modal travel. We conduct a casestudy for the city of Aachen, Germany, where we identify potential locations for mobility hubswhile accounting for individual user utility functions, and provide insights into the potential ofbike and car sharing in combination with mobility hubs and the resulting impact on traffic inthe transit network. In the fifth paper, we apply our model to the transportation system ofMunich and analyze the potential effects that a large-scale integration of car-free zones wouldhave on the network. Within this case study, we compare brownfield and greenfield approaches,study how the full electrification of the car fleet affects the results, and assess how car-free zonesinduce a shift in traffic.The third part consists of a single paper that combines the network design perspective with amarket analysis by studying a concrete application in which a monopolistic operator builds andoperates a Carbon Capture and Storage (CCS) pipeline. We develop a matheuristic frameworkthat combines a clustering algorithm, used to identify promising network configurations, witha bilevel model that recommends prices the operator should charge for network usage. Weapply the model to an extensive case study for Germany and provide recommendations forpolicymakers on how regulatory restrictions on pricing policy affect network structure and overallsystem performance.Overall, this dissertation contributes new state-of-the-art solution methods and deliversvaluable practical insights through the conducted case studies and the resulting managerialimplications. In the process, we also connect different theoretical research streams, especiallydecomposition techniques, which enables the transfer of insights between them. From a practitioner’spoint of view, the developed models either have a simple structure that is easy tounderstand or follow a modular design in which components can be exchanged to meet newrequirements. As a result, the developed algorithms are well suited for implementation andmaintenance in practice.

Authors 1

1. Vladimir Stadnichuk corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen