This dissertation investigates optimization approaches applied to radiation therapy in cancer treatment. Since cancerous cells are surrounded by critical organs and normal tissues, there is conflicting objectives in the treatment design of providing sufficient radiation dose to tumor region, while avoiding normal healthy cells. In general, the goal of radiation therapy is to conform the spatial distribution of the prescribed dose to the tumor volume while minimizing the dose to the surrounding normal structures. A recent advanced technology, using multi-leaf collimator integrated into linear accelerator, provides much better opportunities to achieve this goal: the radiotherapy based on non-uniform radiation beams intensities is called Intensity-Modulated Radiation Therapy. My dissertation research offers a quadratic mixed integer programming approach to determine optimal beam orientations and beamlets intensity simultaneously. The problems generated from real patient cases are large-scale dense instances due to the physics of dose contributions from beamlets to volume elements. The research highlights computational techniques to improve solution times for these intractable instances. Furthermore, results from this research will provide plans that are clinically acceptable and superior in plan quality, thus directly improve the curity rate and lower the normal tissue complication for cancer patients.

L’objectif de cette thèse est de développer un cadre méthodologique pour les problèmes de tournées de véhicules riches (RVRPs). Nous présentons d’abord une taxonomie et une définition élaborée des RVRPs basée sur une analyse typologique réalisée en fonction de deux critères discriminatoires. Dans cette thèse, nous nous intéressons à la résolution du problème de tournées de véhicules multi-dépôt multi-compartiment multi-produits avec fenêtres de temps (MDMCMCm-VRPTW). Nous proposons une heuristique de génération de colonnes unifiée qui inclut une matheuristique de type VNS. La matheuristique combine plusieurs heuristiques de routage de type destruction et insertion ainsi que des procédures efficaces de contrôle de réalisabilité des contraintes afin de résoudre le MDMCMCm-VRPTW pour un seul véhicule. Deux voisinages de chargement, basés sur la résolution de programmes mathématiques sont proposées. Des études expérimentales approfondies sont conduites sur un ensemble de 191 instances pour des VRPs moins complexes. Les expérimentations valident la compétitivité de la matheuristique unifiée. Une analyse de sensibilité révèle l’importance de certains choix algorithmiques et des voisinages de chargement pour parvenir à des solutions de très bonne qualité. La matheuristique basée sur la méthode de VNS est intégrée dans l’heuristique de génération de colonnes pour résoudre le MDMCMCm-VRPTW. Nous proposons une méthode exacte de post-traitement capable d’optimiser l’affectation des clients aux tournées de véhicules. Enfin, nous résolvons un RVRP qui survient dans le processus de collecte de l’huile d’olive en Tunisie à l’aide d’un algorithme exact de type branch-and-cut / The purpose of this thesis is to develop a solution framework for Rich Vehicle Routing Problems (RVRPs). We first provide a comprehensive survey of the RVRP literature as well as a taxonomy. Selected papers addressing various variants are classified according to the proposed taxonomy. A cluster analysis based on two discriminating criteria is performed and leads to define RVRPs. In this thesis we are interested in solving a multi-depot multi-compartment multi-commodity vehicle routing problem with time windows (MDMCMCm-VRPTW). We propose a unified column generation heuristic cooperating with a variable neighborhood search (VNS) matheuristic. The VNS combines several removal and insertion routing heuristics as well as computationally efficient constraint checking. Two loading neighborhoods based on the solution of mathematical programs are proposed to intensify the search. On a set of 191 instances of less complex routing problems, the unified matheuristic turns to be competitive. A sensitivity analysis, performed on more complex generated instances reveals the importance of some algorithmic features and of loading neighborhoods for reaching high quality solutions. The VNS based matheuristic is embedded in a column generation heuristic to solve the MDMCMCm-VRPTW. We propose an exact post-processing method to optimize the assignment ofcustomers to vehicle routes. Last, we introduce, model and solve to optimality a RVRP arising in the olive oil collection process in Tunisia. We propose an exact branch-and-cut algorithm to solve the problem. We evaluate the performance of the algorithm on real data sets under different transportation scenarios

This thesis explores the use of a column generation method, a subgradient method, and a logic-based Benders decomposition method on a minimized makespan K-rural postman problem. The K-rural postman problem here describes a search and rescue mission using multiple identical unmanned aerial vehicles (UAVs) to cover an area, represented as a complete graph. Each decomposition method has a separate problem for each UAV. In the subgradient and column generation case, a heuristic is used to find an improved upper bound for the makespan. This upper bound can in turn be used to decrease the feasible regions of the subproblems. Moreover, because the subproblems are slow to solve, a maximum calculation time is used, resulting in a feasible solution and a lower bound for each subproblem. These two modifications to the decomposition methods result in a non-standard behaviour.  Multiple fictional problem instances of different sizes and numbers of UAVs were generated and used for evaluating the methods. A maximal time limit is used in these instances. We conclude that solving the original, non-decomposed, problem for smaller instances with a standard solver is faster and gives better results than the decomposition methods. For larger instances, solving the non-decomposed model led to memory issues on several occasions. However, the suggested subgradient and column generation methods can solve every problem. The logic-based Benders decomposition method performed best on instances with multiple UAVs, but had issues when fewer UAVs are utilized. / Den här masteruppsatsen utforskar användningen av en kolumngenereringsmetod, en subgradientmetod och en logikbaserad Benders dekompositionsmetod på en variant av lantbrevbärarproblemet. Vårat brevbärarprolem beskriver sök- och räddningsuppdrag där $K$ drönare används för att avsöka ett område med målfunktionen att minimera flygtiden för den långsammaste drönaren. Varje dekompositionsmetod använder sig av ett problem för varje drönare. I subgradient- och kolumngenereringsmetoden användes en heuristik för att hitta en bättre övre begränsning till drönarnas flygtid. Den förbättrade övre begränsningen kunde sedan användas för att minska det tillåtna området för de mindre problemen. Eftersom de mindre problem var svårlösta, användes en maximal beräkningstid vilket resulterade i att en tillåten lösning och undre gräns gavs för varje mindre problem. Dessa två modifikationer resulterade i icke typiska beteenden.  Metoderna utvärderades på flera fiktiva testinstanser av olika storlekar där antalet drönare varierar. En tidsbegränsning används på varje probleminstans. Slutsatserna från uppsatsen är de original brevbärare problemet ger bäst lösning och snabbast lösningstid i de mindre instanserna. Vid lösning av större probleminstanser, gav original problemet flerfaldiga gånger minnesproblem. Subgradient- och kolumngenereringsmetoden kunde däremot lösa varje probleminstans inom tidsbegränsningen, vilket gjorde de mer pålitliga. Logikbaserade Benders dekompositionsmetoden presterade bättre i instanser med flera drönare, men stötte på problem i instanser med färre drönare.