Algorithmes de branch-price-and-cut pour ...
Document type :
Thèse
Title :
Algorithmes de branch-price-and-cut pour des problèmes d'optimisation intégrés en transport et santé
English title :
Branch-price-and-cut algorithms for integrated optimisation problems in transportation and healthcare
Author(s) :
Thesis director(s) :
Frédéric Semet
Defence date :
2023-09-20
Jury president :
Yves Crama [Président]
Renata Mansini [Rapporteur]
Stephan Ropke [Rapporteur]
Roberto Roberti
Claudia Archetti
Diego Cattaruzza
Maxime Ogier
Renata Mansini [Rapporteur]
Stephan Ropke [Rapporteur]
Roberto Roberti
Claudia Archetti
Diego Cattaruzza
Maxime Ogier
Jury member(s) :
Yves Crama [Président]
Renata Mansini [Rapporteur]
Stephan Ropke [Rapporteur]
Roberto Roberti
Claudia Archetti
Diego Cattaruzza
Maxime Ogier
Renata Mansini [Rapporteur]
Stephan Ropke [Rapporteur]
Roberto Roberti
Claudia Archetti
Diego Cattaruzza
Maxime Ogier
Accredited body :
Centrale Lille Institut
Doctoral school :
École doctorale Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....)
NNT :
2023CLIL0021
Keyword(s) :
Génération de colonnes
Probèmes opérationnels intégrés
Problèmes de tournées de véhicules
Problèmes d'échanges de reins
Probèmes opérationnels intégrés
Problèmes de tournées de véhicules
Problèmes d'échanges de reins
English keyword(s) :
Column generation
Integrated operational problems
Vehicle routing problems
Kidney exchange problems
Integrated operational problems
Vehicle routing problems
Kidney exchange problems
HAL domain(s) :
Sciences cognitives/Informatique
French abstract :
Dans cette thèse, nous étudions des problèmes d'optimisation en transport et santé.Pour les applications en transport, nous considérons les problèmes de tournées de véhicules avec plusieurs produits.Plus précisément, nous ...
Show more >Dans cette thèse, nous étudions des problèmes d'optimisation en transport et santé.Pour les applications en transport, nous considérons les problèmes de tournées de véhicules avec plusieurs produits.Plus précisément, nous traitons le problème nommé Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP) dont l'objectif est de minimiser les coûts de transport pour livrer un ensemble de clients à partir d'un seul dépôt avec des véhicules.Les demandes des clients sont composées de plusieurs produits.Afin de minimiser les coûts, plusieurs véhicules peuvent livrer un client, cependant la demande d'un produit doit être livrée par un seul véhicule.Ensuite, nous considérons une extension du C-SDVRP définie sur deux échelons, le Multi-Commodity two-echelon Distribution Problem (MC2DP).Dans le MC2DP, les produits sont collectés au premier échelon par des trajets directs entre les centres de distribution et les fournisseurs, puis au second échelon les produits sont livrés aux clients à partir de chaque centre de distribution comme dans le C-SDVRP.Pour les applications en santé, nous considérons les problèmes qui se posent dans les programmes d'échange de reins.En particulier, nous étudions le Kidney Exchange Problem (KEP), dont l'objectif est de trouver le meilleur ensemble de greffes, en termes de bénéfice médical, dans un pool de donneurs et de patients.Ensuite, nous avons examiné la collaboration et l'équité dans un contexte où différents pays adhèrent à un programme commun d'échange de reins.Un tel problème est appelé International Kidney Exchange Problem (IKEP).Tous les problèmes que nous considérons ont une structure commune : ils se réduisent à la recherche du meilleur ensemble de chemins dans un graphe. Nous les avons modélisés au moyen de formulations étendues où les variables correspondent aux chemins ; et nous les avons résolus par des méthodes heuristiques ou exactes basées sur un paradigme de type branch-and-priceShow less >
Show more >Dans cette thèse, nous étudions des problèmes d'optimisation en transport et santé.Pour les applications en transport, nous considérons les problèmes de tournées de véhicules avec plusieurs produits.Plus précisément, nous traitons le problème nommé Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP) dont l'objectif est de minimiser les coûts de transport pour livrer un ensemble de clients à partir d'un seul dépôt avec des véhicules.Les demandes des clients sont composées de plusieurs produits.Afin de minimiser les coûts, plusieurs véhicules peuvent livrer un client, cependant la demande d'un produit doit être livrée par un seul véhicule.Ensuite, nous considérons une extension du C-SDVRP définie sur deux échelons, le Multi-Commodity two-echelon Distribution Problem (MC2DP).Dans le MC2DP, les produits sont collectés au premier échelon par des trajets directs entre les centres de distribution et les fournisseurs, puis au second échelon les produits sont livrés aux clients à partir de chaque centre de distribution comme dans le C-SDVRP.Pour les applications en santé, nous considérons les problèmes qui se posent dans les programmes d'échange de reins.En particulier, nous étudions le Kidney Exchange Problem (KEP), dont l'objectif est de trouver le meilleur ensemble de greffes, en termes de bénéfice médical, dans un pool de donneurs et de patients.Ensuite, nous avons examiné la collaboration et l'équité dans un contexte où différents pays adhèrent à un programme commun d'échange de reins.Un tel problème est appelé International Kidney Exchange Problem (IKEP).Tous les problèmes que nous considérons ont une structure commune : ils se réduisent à la recherche du meilleur ensemble de chemins dans un graphe. Nous les avons modélisés au moyen de formulations étendues où les variables correspondent aux chemins ; et nous les avons résolus par des méthodes heuristiques ou exactes basées sur un paradigme de type branch-and-priceShow less >
English abstract : [en]
In this thesis, we study optimisation problems in transportation and healthcare.For transportation applications, we consider vehicle routing problems with multiple commodities.Precisely, we address the Commodity constrained ...
Show more >In this thesis, we study optimisation problems in transportation and healthcare.For transportation applications, we consider vehicle routing problems with multiple commodities.Precisely, we address the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP) whose aim is to minimise the transportation costs to deliver a set of customers from a single depot with capacitated vehicles.Customer demands are composed of multiple commodities.In order to minimize the costs, several vehicles can deliver a customer, however, the demand for a single commodity must be delivered by one vehicle only.Then, we consider an extension of the C-SDVRP defined on two echelons, the Multi-Commodity two-echelon Distribution Problem (MC2DP).In the MC2DP, commodities are collected in the first echelon by direct round trips between distribution centres and suppliers, and then in the second echelon, commodities are delivered to the customers from each distribution centre as in the C-SDVRP.For healthcare applications, we consider problems arising in kidney exchange programs.Specifically, we study the Kidney Exchange Problem (KEP), whose aim is to find the best set of transplants, in terms of medical benefit, in a pool of donors and patients.Then, we considered collaboration and fairness in a setting where different countries join a common kidney exchange program.Such a problem is referred to as International Kidney Exchange Problem (IKEP).All the problems we consider share a common structure: they reduce in finding the best set of paths in a graph. We modelled them by means of extended formulations where the variables correspond to the paths, and we solve them by heuristic or exact methods based on the branch-and-price paradigmShow less >
Show more >In this thesis, we study optimisation problems in transportation and healthcare.For transportation applications, we consider vehicle routing problems with multiple commodities.Precisely, we address the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP) whose aim is to minimise the transportation costs to deliver a set of customers from a single depot with capacitated vehicles.Customer demands are composed of multiple commodities.In order to minimize the costs, several vehicles can deliver a customer, however, the demand for a single commodity must be delivered by one vehicle only.Then, we consider an extension of the C-SDVRP defined on two echelons, the Multi-Commodity two-echelon Distribution Problem (MC2DP).In the MC2DP, commodities are collected in the first echelon by direct round trips between distribution centres and suppliers, and then in the second echelon, commodities are delivered to the customers from each distribution centre as in the C-SDVRP.For healthcare applications, we consider problems arising in kidney exchange programs.Specifically, we study the Kidney Exchange Problem (KEP), whose aim is to find the best set of transplants, in terms of medical benefit, in a pool of donors and patients.Then, we considered collaboration and fairness in a setting where different countries join a common kidney exchange program.Such a problem is referred to as International Kidney Exchange Problem (IKEP).All the problems we consider share a common structure: they reduce in finding the best set of paths in a graph. We modelled them by means of extended formulations where the variables correspond to the paths, and we solve them by heuristic or exact methods based on the branch-and-price paradigmShow less >
Language :
Anglais
Collections :
Source :
Files
- document
- Open access
- Access the document
- PhD_thesis_Matteo_Petris.pdf
- Open access
- Access the document