Alumni

Vehicle routing problems (VRPs) are a fundamental piece of logistics planning. Exact methods for the classic capacitated VRP (CVRP) have seen significant advancements over the last ten years, pushing the boundaries of problem sizes that can be efficiently solved to optimality. Standard benchmark CVRP instances having hundreds of customers can be solved to proven optimality within seconds or a few minutes. Nevertheless, the picture is far less promising for other CVRP variants, especially variants that embed delivery decisions in the modelling. For some of these problems, instances with fewer than one hundred – or even a few dozen – customers can be challenging enough. We develop Branch-cut-and-price (BCP) algorithms, the current state-of-the-art approach for solving CVRP problems exactly, for two VRP variants with delivery decisions, namely the split delivery VRP with (SDVRPTW) or without time windows (SDVRP), and the inventory routing problem (IRP). For these problems, the best performing approaches in the literature are mainly Branch-and-cut (B&C) algorithms. Thus, we aim at designing BCP algorithms, adapting state-of-the-art BCP algorithmic components designed for the CVRP to these problems, to assess whether these algorithms can solve large instances and be competitive with tailored B&C for these problems.

[Read more]

We consider general aggregation/disaggregation techniques to address optimization problems that are expressed with the help of sequential decision processes. Our main goals are threefold: a generic formalism that encompasses the aforementioned techniques ; more efficient algorithms to control the aggregation procedures ; open-source codes that leverage and integrate these algorithms to efficiently solve hard combinatorial problems in different application fields.
[Read more]

Authors: Luis Marques, François Clautiaux, Aurélien Froger
Abstract: We study the problem of designing a cabinet made up of a set of shelves that contain compartments whose contents slide forward on opening. Considering a set of items candidate to be stored in the cabinet over a given time horizon, the problem is to d [Read more]

In this thesis, we are interested in problems that can be formulated as a sequence of decisions, where dynamic programming is a suitable modeling paradigm. To solve large-scale problems, we study aggregation and disaggregation methods that allow us to construct relaxations of the problem, which are solved to obtain optimistic solutions to these problems. Iterative algorithms are then designed from these relaxations, where the relaxations provide less optimistic solutions as the number of iterations increases. In this thesis, we first provide a literature review of the aggregation and disaggregation methods in the context of dynamic programming formulations. Then, we propose a problem modeling the aggregation of vertices in decision graphs of dynamic programs to construct relaxations and show that many aggregation methods in the literature are special cases of this problem. We then study an application of network flow formulations in a decision hypergraph, and extend some aggregation methods to this case. To validate our approaches, we present computational results on a set of different problems and compare them to similar approaches in the literature. We conclude this thesis with a discussion on the results obtained and propose some perspectives for future work.

[Read more]

We consider general aggregation/disaggregation techniques to address optimization problems that are expressed with the help of sequential decision processes. Our main goals are threefold: a generic formalism that encompasses the aforementioned techniques ; more efficient algorithms to control the aggregation procedures ; open-source codes that leverage and integrate these algorithms to efficiently solve hard combinatorial problems in different application fields.
[Read more]

Authors: Najib Errami, Eduardo Queiroga, Ruslan Sadykov, Eduardo Uchoa
Abstract: The optimization community has made significant progress in solving Vehicle Routing Problems (VRPs) to optimality using sophisticated Branch-Cut-and-Price (BCP) algorithms. VRPSolver is a BCP algorithm with excellent performance in many VRP variants. [Read more]

This project aims at proposing theoretical and practical results for hard combinatorial optimization problems in an uncertain environment. These problems have in common the fact that the parameters needed to assess the validity of the solution and compute its cost are unknown. Uncertainty in decision making can be caused by several external factors. The most common are related to stochastic parameters (service demand, time needed for a task, prices, …). Incomplete information can also come from the presence of competitors whose policies are not known to the decision maker.

[Read more]

This thesis focuses on the modeling and solution methods for facility location and network design problems under uncertainty, with a particular emphasis on robust optimization with integer recourse. The application studied concerns the blood supply chain in the context of disasters, where demand is uncertain, infrastructures may be damaged, and an emergency response must be implemented.

In this work, we developed several mathematical formulations based on discrete uncertainty sets, incorporating different risk measures: the expectation, the Conditional Value-at-Risk (CVaR), and the worst-case approach. To solve these models, we implemented decomposition techniques, including Benders decomposition (in its multi-cut and stabilized variants) and the Column-and-Constraint Generation (CCG) algorithm. To improve solution quality, especially for large-scale instances, we also proposed an adjustable robust model based on continuous uncertainty sets. Using different types of sets, we applied affine decision rules as well as a static approach for recourse decisions in order to ensure tractability.

[Read more]

Saint-Gobain Research Paris is an industrial research and development centre working for light and sustainable construction of the Saint-Gobain Group, the world leader in light and sustainable construction.

The collaboration was centered around the PhD thesis of Quentin Viaud.

[Read more]

Authors: François Clautiaux, Siham Essodaigui, Alain Nguyen, Ruslan Sadykov, Nawel Younes
Abstract: In this paper, we consider a new industrial problem, which occurs in the context of the automobile industry. This problem occurs during the testing phase of a new vehicle. It involves determining all the variants of the vehicle to be manufactured in [Read more]

Authors: Najib Errami, Eduardo Queiroga, Ruslan Sadykov, Eduardo Uchoa
Abstract: The optimization community has made significant progress in solving Vehicle Routing Problems (VRPs) to optimality using sophisticated Branch-Cut-and-Price (BCP) algorithms. VRPSolver is a BCP algorithm with excellent performance in many VRP variants. [Read more]

Authors: Sylvain Lichau, Ruslan Sadykov, Julien François, Rémy Dupas
Abstract: In this paper, we propose a new set-partitioning model for the two-echelon vehicle routing problem with drones (2E-VRP-D), where partial routes corresponding to drone movements are enumerated using an efficient dynamic program. To solve the model we [Read more]

Drones represent a promising complement to delivery logistics. They offer a fundamentally different performance profile than conventional trucks. They have lower operating costs and higher speeds, at the expense of reduced range and capacity. In scenarios where these limitations are manageable, drones can fully replace traditional delivery trucks. However, in most practical applications, these complementary vehicle types should be strategically combined to leverage their respective operational strengths. This thesis mainly proposes exact mathematical optimization methods for routing problems with drones.

[Read more]

In this work, we study a variant of the Vehicle Routing Problem with Time Windows (VRPTW), which integrates two operationally relevant features: flexible departure times from the depot and strict limits on route duration. The resulting problem, termed VRPTW with Route Duration Constraint (VRPTWDC), introduces a scheduling dimension that makes the routing computationally challenging and largely unexplored in the literature. We develop an exact branch-cut-and-price algorithm, having as its main feature a bi-bidirectional labeling algorithm for solving the complex pricing subproblem. Indeed, as the only previously proposed efficient labeling algorithm for the VRPTWDC has a mistake, we provide rigorous proofs of its correctness. Computational experiments on benchmark instances demonstrate the effectiveness of the approach.

[Read more]

Nous étudions un problème de découpe avec restes réutilisables et incertitudes sur les demandes. Dans la littérature, une formulation stochastique à deux étapes du problème a était proposé. Nous introduisons une formalisation du problème avec un nombre arbitraire d’étapes. Puis, nous introduisons des méthodes de résolutions exactes axées sur la reformulation du problème en problème de flots dans des graphes ou hypergraphes. Pour les instances du problème avec un grand nombre de scénarios, nous proposons des méthodes de relaxation afin de calculer des bornes inférieures quand la relaxation linéaire ne peux être obtenue. Enfin, nous testons la pertinence de l’approche stochastique à l’aide d’un horizon roulant et en testant différents types d’oracle. Nous comparons nos différentes formulations pour des instances à deux étapes avec les instances de la littérature. Nous comparons également nos bornes inférieures introduites et nous montrons que certaines permettent d’aller plus loin en nombre d’étapes que la relaxation linéaire. Enfin, nous montrons qu’effectuer un horizon roulant avec un oracle à trois étapes permet de faire plus d’économies comparé à un oracle à deux étapes sur les instances de la littérature.

[Read more]

Authors: Xavier Blanchot, François Clautiaux, Aurélien Froger, Manuel Ruiz
Abstract: In this paper, we study how a regulatory constraint limiting a measure of unserved demand, called Loss Of Load Expectation (LOLE), can be incorporated into a strategic version of a stochastic generation and transmission expansion planning problem. Th [Read more]