Team

On s’intéresse au problème de maximiser la valeur d’un flot dans un hypergraphe de décision. Ce formalisme permet de modéliser toute une classe de problèmes de découpe guillotine, en particulier le problème du sac à dos guillotine 2D. Je présenterai notre algorithme de résolution, basé sur un algorithme d’étiquettes muni de bornes supérieures améliorées, issues de la programmation linéaire.

En particulier, je rappellerai la méthodologie de génération d’hyperarcs déjà introduite dans la littérature qui permet de résoudre le LP très rapidement en pratique sur de grosses instances, puis je présenterai nos inégalités valides, ainsi qu’une manière dont les bornes peuvent être incluses dans un algorithme d’étiquettes. Je présenterai également les résultats expérimentaux, qui démontrent l’efficacité de notre algorithme par rapport aux autres méthodes proposées dans la littérature.

On s’intéresse au problème d’optimiser une fonction objectif \(g(W x) + c^T x\) pour \(x\) entier, où chaque coordonnée de \(x\) est contrainte dans un intervalle. On suppose que la matrice \(W\) est à coefficient entiers de valeur absolue bornée par \(\Delta\), et qu’elle projette \(x\) sur un espace de petite dimension \(m << n\). Ce problème est une généralisation du résultat de Hunkenschröder et al. dans lequel \(g\) est séparable convexe, et \(x\) est dans un \(0-1\) hypercube.

CATIE (Centre Aquitain des Technologies de l’Information et Électroniques) is a non-profit organization created in 2014 based in the Région Nouvelle-Aquitaine. As a technology resources center specialized in digital technology, its main mission is to support SMEs and intermediate size companies in their digital transformation and to help them embracing and integrating related technologies.

Our collaboration with CATIE is about machine learning and optimization. We focus on problems related to shortest path problem with side constraints.

RTE is France’s Transmission System Operator. It is in charge of the high and ultra-high voltage electricity transmission network in France and of the electricity exchanges with the neighbouring countries. Its main role is to guarantee in real time the balance between electricity production and consumption.

In 2019, a contract was signed with RTE for a PhD on algorithms to speedup Benders’ decomposition. The PhD student was Xavier Blanchot under the supervision of François Clautiaux and Aurélien Froger.

In this internal workshop, we review the recent literature on Lagrangian variable fixing techniques.

The presentation is about the following submitted paper:

Xavier Blanchot, François Clautiaux, Aurélien Froger, Manuel Ruiz. (2023). Modeling and solving a stochastic generation and transmission expansion planning problem with a “Loss Of Load Expectation” reliability criterion. (hal-03957750v2)

Many real-life decision-making problems under uncertainty include some form of interaction between the actions of the decision-maker and the realization of uncertain parameters. For instance, in medical appointment scheduling, no-shows of the patients are typically related to the schedules themselves whereas, in long-term medical treatments, the state of a patient evolves depending on past medication (decision-dependent uncertainty). On the other hand, in planning organ transplants, the uncertainty related to the compatibility of donors and patients needs to be investigated via expensive medical tests (information discovery) under a given budget constraint. It is therefore essential to incorporate the interactions of the decision-maker with the uncertain parameters within optimization under uncertainty models. This project proposes the study and solution of robust optimization models formalizing such interactions under a single mathematical framework with decision-dependent uncertainty sets.

Robust optimization has evolved as a key paradigm for handling data uncertainty within mathematical optimization problems: it requires little historical information, can be used without characterizing probability distributions and often leads to tractable optimization problems that can be treated with existing deterministic optimization paradigms. However, the picture is more complex when some of the decisions (referred to as recourse decisions) can be adjusted after the uncertain data is known, to mitigate the effects of uncertainty, leading to adjustable robust optimization problems. Adjustable problems with discrete variables or multiple decision periods are particularly difficult to solve and, up to now, no scalable exact method has emerged. Project DROI proposes to study primal and dual approximations for such problems.

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 is centered around the PhD thesis of Pierre Pinet.

Adjustable robust optimization problems, as a subclass of multi-stage optimization under uncertainty problems, constitute a class of problems that are very difficult to solve in practice. Although the exact solution of these problems under certain special cases may be possible, for the general case, there are no known exact solution algorithms. Instead, approximate solution methods have been developed, often restricting the functional form of recourse actions, these are generally referred to as “decision rules“. In this talk, we will present a review of existing decision rule approximations including affine and extended affine decision rules, uncertainty set partitioning schemes and finite-adaptability. We will discuss the reformulations and solution algorithms that result from these approximations. We will point out existing challenges in practical use of these decision rules, and identify current and future research directions. When possible we will emphasize the connections to multi-stage stochastic programming literature.

Many real-life decision-making problems under uncertainty include some form of interaction between the actions of the decision-maker and the realization of uncertain parameters. For instance, in medical appointment scheduling, no-shows of the patients are typically related to the schedules themselves whereas, in long-term medical treatments, the state of a patient evolves depending on past medication (decision-dependent uncertainty). On the other hand, in planning organ transplants, the uncertainty related to the compatibility of donors and patients needs to be investigated via expensive medical tests (information discovery) under a given budget constraint. It is therefore essential to incorporate the interactions of the decision-maker with the uncertain parameters within optimization under uncertainty models. This project proposes the study and solution of robust optimization models formalizing such interactions under a single mathematical framework with decision-dependent uncertainty sets.

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.

Robust optimization has evolved as a key paradigm for handling data uncertainty within mathematical optimization problems: it requires little historical information, can be used without characterizing probability distributions and often leads to tractable optimization problems that can be treated with existing deterministic optimization paradigms. However, the picture is more complex when some of the decisions (referred to as recourse decisions) can be adjusted after the uncertain data is known, to mitigate the effects of uncertainty, leading to adjustable robust optimization problems. Adjustable problems with discrete variables or multiple decision periods are particularly difficult to solve and, up to now, no scalable exact method has emerged. Project DROI proposes to study primal and dual approximations for such problems.

The project:

Strategic Power Systems Development for the Future (PowerDev), funded by PEPR TASE, studies optimization methods and reliability/resilience engineering applied to large-scale electrical power systems. The project is led by CentraleSupélec at the University of Paris Saclay and is composed of a consortium of higher education institutions across France (CentraleSupelec, UVSQ, University Grenoble Alpes), as well as research organizations (Inria, CNRS).

Research topic and objectives:

Modern power systems are expected to become increasingly complex to design and operate due to the growing number of renewable energy sources (RES). Renewable energy generation is, by nature, intermittent and introduces an amount of uncertainty that severely affects the physical responses of the power system, particularly in terms of voltage control and frequency regulation [1]. Moreover, RES integration within the power system requires the introduction of many new power electronic devices, which add to the system’s complexity and increase its possible failure modes [2,3]. Combined with unexpected initiating events, these two main features can lead to cascading failure risks, triggering disastrous consequences to the power grid and, most notably, large-scale blackouts [4-7]. The economic and societal consequences to the impacted regions are usually massive, with economic loss measured in the tens of billions of dollars [8]. The main objective of this project is to evaluate and optimize the resilience of power systems in the context of a massive insertion of renewable energies. The project aims to elaborate a comprehensive and integrated set of decision support tools by considering extreme events in present and future climates, the complexity of the power grid, and socio-economic scenarios.

EDF is the major French multinational electric utility company owned by the French state.

Optimizing nuclear unit outages is of significant economic importance for the French electricity company EDF, as these outages induce a substitute production by other more expensive means to fulfill electricity demand. This problem is quite challenging given the specific operating constraints of nuclear units, the stochasticity of both the demand and non-nuclear units availability, and the scale of the instances. To tackle these difficulties we used a combined decomposition approach. The operating constraints of the nuclear units were built into a Dantzig-Wolfe pricing subproblem whose solutions define the columns of a demand covering formulation. The scenarios of demand and non-nuclear units availability are handled in a Benders decomposition. Our approach is shown to scale up to the real-life instances of the French nuclear fleet.

RTE is France’s Transmission System Operator. It is in charge of the high and ultra-high voltage electricity transmission network in France and of the electricity exchanges with the neighbouring countries. Its main role is to guarantee in real time the balance between electricity production and consumption.

In 2019, a contract was signed with RTE for a PhD on algorithms to speedup Benders’ decomposition. The PhD student was Xavier Blanchot under the supervision of François Clautiaux and Aurélien Froger.

SNCF is the French Railway operator. This project was funded by TER Nouvelle Aquitaine.

This collaboration funded the PhD thesis of Mohamed Benkirane. The subject of the thesis was an integrated optimization approach for timetable and rolling stock rotations planning in the context of passenger railway traffic. Our approach was based on a time-space hyper-graph model, which can handle trains composed by multiple self-powered railcars on part of their paths.

In this talk, we will introduce a new exact algorithm to solve two-stage stochastic linear programs. Based on the multicut Benders reformulation of such problems, with one subproblem for each scenario, this method relies on a partition of the subproblems into batches. The key idea is to solve at most iterations only a small proportion of the subproblems by detecting as soon as possible that a first-stage candidate solution cannot be proven optimal. We also propose a general framework to stabilize our algorithm, and show its finite convergence and exact behavior. We report an extensive computational study on large-scale instances of stochastic optimization literature that shows the efficiency of the proposed algorithm compared to nine alternative algorithms from the literature. We also obtain significant additional computational time savings using the primal stabilization schemes.

Les systèmes traditionnels de livraison urbaine reposent sur des véhicules, infrastructures et flux dédiés. Avec la croissance de la demande en milieu urbain et à la nécessité de réduire le trafic, l’utilisation des infrastructures du réseau de transport public pour le transport middle-mile des colis apparaît comme une alternative.

Dans cette présentation, nous traitons le problème de planification à court terme pour la livraison urbaine de colis sur le segment middle-mile, en intégrant les opérations de fret au sein des réseaux de transport public. En s’appuyant sur le principe de la consolidation et conteneurisation, nous proposons un modèle PLNE qui optimise conjointement la conteneurisation des colis et le routage des conteneurs sur un réseau multi-lignes et multi-modes. Notre approche repose sur une représentation multi-graphe du réseau, permettant de modéliser précisément les différentes lignes, modes de transport et options de transfert. Deux types de graphes sont construits à partir du réseau de transport public réel: un graphe espace-temps pour les conteneurs et un graphe pour les colis, ajoutant la dimension du conteneur utilisé. Pour valider notre approche, nous évoquerons une étude de cas basée sur des données réelles de la ville de Bordeaux.

The project:

Strategic Power Systems Development for the Future (PowerDev), funded by PEPR TASE, studies optimization methods and reliability/resilience engineering applied to large-scale electrical power systems. The project is led by CentraleSupélec at the University of Paris Saclay and is composed of a consortium of higher education institutions across France (CentraleSupelec, UVSQ, University Grenoble Alpes), as well as research organizations (Inria, CNRS).

Research topic and objectives:

Modern power systems are expected to become increasingly complex to design and operate due to the growing number of renewable energy sources (RES). Renewable energy generation is, by nature, intermittent and introduces an amount of uncertainty that severely affects the physical responses of the power system, particularly in terms of voltage control and frequency regulation [1]. Moreover, RES integration within the power system requires the introduction of many new power electronic devices, which add to the system’s complexity and increase its possible failure modes [2,3]. Combined with unexpected initiating events, these two main features can lead to cascading failure risks, triggering disastrous consequences to the power grid and, most notably, large-scale blackouts [4-7]. The economic and societal consequences to the impacted regions are usually massive, with economic loss measured in the tens of billions of dollars [8]. The main objective of this project is to evaluate and optimize the resilience of power systems in the context of a massive insertion of renewable energies. The project aims to elaborate a comprehensive and integrated set of decision support tools by considering extreme events in present and future climates, the complexity of the power grid, and socio-economic scenarios.

Nous souhaitons optimiser un ensemble de décisions stratégiques pour améliorer la résilience de réseaux électriques afin de prévenir des scénarios de blackouts. Pour un réseau fixé, nous envisageons les sous-problèmes suivants : 1. Phase de réponse : nous avons identifié deux contre-mesures principales : le délestage et la neutralisation de lignes électriques. 2. Phase de conception : nous avons identifié deux leviers principaux : la mise en place de contrats visant à influencer le comportement des consommateurs et le déploiement de batteries afin de mieux équilibrer les flux de puissance au sein du réseau.

The project:

Project ACME is funded by PEPR MOBIDEC. The program aims to mobilize the national research community and transportation ecosystem stakeholders to:

1. Understand mobility of goods and peopleand anticipate the mobility of goods and people
2. Help collect, structure, and interpret mobility data
3. Provide decision-making tools to simulate the impact of public policies and evaluate the relevance of new transport solutions

Our projet studies optimization methods for horizontal collaboration in logistics.

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.

The aim of the Grip4All project is to make industry more competitive by developing a new palletising cell adapted to the severe constraints imposed on the logistics flow when handling mixed products (of varying dimensions and weight) and arranging them on a pallet, without having to sort them manually upstream. This new type of palletising meets a strong demand from a number of sectors, notably mass distribution and the food industry. It meets the demand for handling heterogeneous products without imposing constraints on their packaging, which significantly improves productivity and eliminates tedious human tasks. No similar solution currently exists on the market. The flexible robotics issues addressed will be transposable to other logistics processes in the factory of the future.

The project:

Strategic Power Systems Development for the Future (PowerDev), funded by PEPR TASE, studies optimization methods and reliability/resilience engineering applied to large-scale electrical power systems. The project is led by CentraleSupélec at the University of Paris Saclay and is composed of a consortium of higher education institutions across France (CentraleSupelec, UVSQ, University Grenoble Alpes), as well as research organizations (Inria, CNRS).

Research topic and objectives:

Modern power systems are expected to become increasingly complex to design and operate due to the growing number of renewable energy sources (RES). Renewable energy generation is, by nature, intermittent and introduces an amount of uncertainty that severely affects the physical responses of the power system, particularly in terms of voltage control and frequency regulation [1]. Moreover, RES integration within the power system requires the introduction of many new power electronic devices, which add to the system’s complexity and increase its possible failure modes [2,3]. Combined with unexpected initiating events, these two main features can lead to cascading failure risks, triggering disastrous consequences to the power grid and, most notably, large-scale blackouts [4-7]. The economic and societal consequences to the impacted regions are usually massive, with economic loss measured in the tens of billions of dollars [8]. The main objective of this project is to evaluate and optimize the resilience of power systems in the context of a massive insertion of renewable energies. The project aims to elaborate a comprehensive and integrated set of decision support tools by considering extreme events in present and future climates, the complexity of the power grid, and socio-economic scenarios.

CATIE (Centre Aquitain des Technologies de l’Information et Électroniques) is a non-profit organization created in 2014 based in the Région Nouvelle-Aquitaine. As a technology resources center specialized in digital technology, its main mission is to support SMEs and intermediate size companies in their digital transformation and to help them embracing and integrating related technologies.

Our collaboration with CATIE is about machine learning and optimization. We focus on problems related to shortest path problem with side constraints.

Renault is a French multinational automobile manufacturer established in 1899. The company produces a range of cars and vans and in the past, has manufactured trucks, tractors, tanks, buses/coaches, aircraft and aircraft engines, and autorail vehicles.

RTE is France’s Transmission System Operator. It is in charge of the high and ultra-high voltage electricity transmission network in France and of the electricity exchanges with the neighbouring countries. Its main role is to guarantee in real time the balance between electricity production and consumption.

In 2019, a contract was signed with RTE for a PhD on algorithms to speedup Benders’ decomposition. The PhD student was Xavier Blanchot under the supervision of François Clautiaux and Aurélien Froger.

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.

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 is centered around the PhD thesis of Pierre Pinet.

SNCF is the French Railway operator. This project was funded by TER Nouvelle Aquitaine.

This collaboration funded the PhD thesis of Mohamed Benkirane. The subject of the thesis was an integrated optimization approach for timetable and rolling stock rotations planning in the context of passenger railway traffic. Our approach was based on a time-space hyper-graph model, which can handle trains composed by multiple self-powered railcars on part of their paths.

The presentation is about the following submitted paper:

François Clautiaux, Siham Essodaigui, Alain Nguyen, Ruslan Sadykov, Nawel Younes. (2023). Models and algorithms for configuring and testing prototype cars. (hal-04185248)

CATIE (Centre Aquitain des Technologies de l’Information et Électroniques) is a non-profit organization created in 2014 based in the Région Nouvelle-Aquitaine. As a technology resources center specialized in digital technology, its main mission is to support SMEs and intermediate size companies in their digital transformation and to help them embracing and integrating related technologies.

Our collaboration with CATIE is about machine learning and optimization. We focus on problems related to shortest path problem with side constraints.

Many combinatorial optimization (CO) problems can be formulated as resource-constrained shortest path problems (RCSPPs) on directed acyclic multigraphs, which represent state-transition graphs defined under the dynamic programming (DP) paradigm. The number of vertices, arcs, and resource constraints depends on the size of the original problem instance. This reformulation is NP-hard. Exact methods require high-quality primal bounds to converge efficiently.

In this work, we focus on designing a generic constructive heuristic algorithm that can be applied to any problem once it is formulated as an RCSPP on a directed acyclic multigraph. Recent advances have demonstrated that combining machine learning (ML) with tree-based search strategies can enhance the solution of CO problems. Building on this idea, we propose an ML-enhanced beam search algorithm for RCSPPs. Our ML model leverages graph-based information to score candidate paths for expansion.

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.

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.

An energy community (EC) is a legal entity involving prosumers and consumers who produce, consume, and exchange energy. The members of these communities can cooperate to maximize the community’s social welfare. In practice, this naturally raises the question of cost sharing in the community, as the members may have different contributions to social welfare. In this presentation, we empirically highlight the benefits of cooperation for the community and the individual members. Then, we present some cost-sharing mechanisms that guarantee fairness and the stability of the grand coalition composed of all prosumers and consumers. Finally, we present some results on instances built with real-world data from our partner Sween’s demonstrator, Smart Lou Quila, in South France.

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.

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.

Robust optimization has evolved as a key paradigm for handling data uncertainty within mathematical optimization problems: it requires little historical information, can be used without characterizing probability distributions and often leads to tractable optimization problems that can be treated with existing deterministic optimization paradigms. However, the picture is more complex when some of the decisions (referred to as recourse decisions) can be adjusted after the uncertain data is known, to mitigate the effects of uncertainty, leading to adjustable robust optimization problems. Adjustable problems with discrete variables or multiple decision periods are particularly difficult to solve and, up to now, no scalable exact method has emerged. Project DROI proposes to study primal and dual approximations for such problems.

In this talk we consider two-stage linear adjustable robust optimization problems with continuous and fixed recourse. These problems have been the subject of exact solution approaches, notably, constraint generation (CG) and constraint-and-column generation (CCG). Both approaches repose on an exponential-sized reformulation of the problem which uses a large number of constraints or constraints and variables. The decomposition algorithms then solve and reinforce a relaxation of the aforementioned reformulation through the iterations which require the solution of bilinear separation problems. Here, we present an alternative approach reposing on a novel reformulation of the problem with an exponential number of semi-infinite constraints. We present a nested decomposition algorithm to deal with the exponential and semi-infinite natures of our formulation separately. We argue that our algorithm will lead to a reduced number of bilinear separation problems solved while providing a high quality relaxation. We perform a detailed numerical study that showcases the superior performance of our proposed approach compared to the state-of-the-art and evaluates the contribution of different algorithmic components.

The aim of the Grip4All project is to make industry more competitive by developing a new palletising cell adapted to the severe constraints imposed on the logistics flow when handling mixed products (of varying dimensions and weight) and arranging them on a pallet, without having to sort them manually upstream. This new type of palletising meets a strong demand from a number of sectors, notably mass distribution and the food industry. It meets the demand for handling heterogeneous products without imposing constraints on their packaging, which significantly improves productivity and eliminates tedious human tasks. No similar solution currently exists on the market. The flexible robotics issues addressed will be transposable to other logistics processes in the factory of the future.

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.

The presentation is about a working paper on the maximum chordal sub-graph problem

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 is centered around the PhD thesis of Pierre Pinet.

We study the Vehicle Routing Problem with Stochastic Demands (VRPSD), which involves optimizing delivery routes for vehicles with limited capacity to serve customers whose demands are unknown when designing the routes. The routes are designed taking into account the possibility that a route may have too much demand for the capacity of a vehicle to be delivered, in that case recourse actions can be taken, inducing a cost. This problem seeks to minimize routing costs and the expected recourse costs.

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.