This master thesis addresses large-scale two-stage network design problems. In this class of problems, a first-stage decision consists in designing an infrastructure (a network) connecting several sites, while the second-stage decision consists in routing a set of demands over the network previously built. Such problems arise notably in transportation and logistics, and are characterized by a strong interaction between design and routing decisions. For large-scale instances, which involve routing a large number of demands, exact solution methods struggle to converge to the optimal solution.
The objective of this work is to develop approaches that yield high-quality solutions, together with guarantees on the optimal value, while preserving good scalability. Two complementary contributions are proposed.
The first contribution strengthens exact methods by introducing new lower bounds that exploit the integer structure of the problems under study. These bounds reduce the search space and improve the performance of branch-and-bound algorithms.
The second contribution introduces a paradigm shift through a demand sampling approach. The idea consists in approximating the original problem using only a random subset of demands, suitably rescaled. We show that this deterministic problem can be reinterpreted within a stochastic framework, which allows us to leverage the tools of stochastic programming to obtain statistical estimators of the optimal value, as well as valid lower and upper bounds.
The proposed approaches are analyzed theoretically and evaluated experimentally on instances from the literature, demonstrating their effectiveness and their ability to handle large-scale instances.
| Date | 26 Jun 2026 |
|---|
| Original language | French |
|---|
| Awarding Institution | - École de technologie supérieure
|
|---|
| Supervisor | Fausto Errico (Supervisor) |
|---|
Jusseau, J. (Author),
Errico (Supervisor),
26 Jun 2026Student thesis: Master's thesis › Master in Engineering: Information Technology Engineering