Reproduction de : Thèse de doctorat : informatique et mathématiques appliquées : Grenoble 1 : 1988. / Titre provenant de l'écran-titre.

Thesis (doctoral)--Technische Universiteit Delft, 2003. / Includes bibliographical references (p. 167-181).

Le problème d'approvisionnement de stations d'essence consiste à livrer des carburants à l'aide d'une flotte de camions-citernes compartimentés en maximisant une fonction de revenu du transporteur. Il convient essentiellement de déterminer les quantités à livrer de chaque produit, de les affecter aux compartiments des véhicules et de construire les routes permettant leur livraison. Cette thèse comporte trois articles présentant chacun une version différente de ce problème d'approvisionnement. / Nous proposons, dans le premier article, une méthode exacte de résolution applicable au cas où la flotte est illimitée et le nombre de stations par route limité à deux. Le problème y est décomposé en un sous-problème d'affectation des produits aux compartiments des véhicules et un sous-problème de routage. L'affectation des produits aux compartiments repose sur un algorithme classique d'affectation dans un graphe bipartite suivi d'un test d'optimalité, et recourt éventuellement à la résolution d'un programme linéaire en nombres entiers. Puisqu'un voyage ne peut desservir plus de deux stations, le problème de routage est réduit à un problème de couplage de coût minimal clans un graphe non bipartite. Deux stratégies sont alors proposées : rechercher un chargement admissible des produits dans les compartiments pour tous les couples possibles de stations, puis résoudre le problème de couplage correspondant, ou générer les routes en résolvant le problème de couplage a priori pour ensuite tester l'existence d'un chargement admissible pour chacune, cette procédure étant répétée aussi longtemps qu'une route non admissible est générée. / Nous présentons dans le second article une heuristique appliquée au problème d'approvisionnement sur plusieurs périodes avec cette fois un nombre limité de camions-citernes. Dans cette version du problème d'approvisionnement, l'objectif est de déterminer pour chacjue période, les stations, les produits et les quantités à livrer, d'affecter les pioduits aux compartiments des camions-citernes et de construire les routes. L'affectation des stations aux différentes périodes est déterminée par un algorithme récursif incluant une procédure d'anticipation des livraisons. Nous proposons par ailleurs une procédure d'affectation des routes aux véhicules (route packing) par laquelle les routes sont affectées aux véhicules. / Dans le troisième article, nous nous intéressons à nouveau au problème monopé¬riode en intégrant cette fois la gestion des fenêtres de temps en dehors desquelles les livraisons ne peuvent avoir lieu. Nous y considérons par ailleurs le cas d'une flotte limitée et relaxons l'hypothèse de limitation des routes à deux stations. Une formulation différente de celle proposée dans le premier article est présentée. Elle repose sur une sélection de routes respectant les contraintes horaires à partir d'un ensemble de routes admissibles générées a priori et éventuellement présélectionnées. De cette formulation, deux heuristiques sont développées reposant sur une présélection des arcs du graphe c

Ce mémoire propose une formulation pour le problème de confection d'horaire pour résidents, un problème peu étudiée dans la litérature. Les services hospitaliers mentionnés dans ce mémoire sont le service de pédiatrie du CHUL (Centre Hospitalier de l'Université Laval) et le service des urgences de l'Hôpital Enfant-Jésus à Québec. La contribution principale de ce mémoîre est la proposition d'un cadre d'analyse pour l’analyse de techniques manuelles utilisées dans des problèmes de confection d'horaires, souvent décrits comme des problèmes d'optimisation très complexes. Nous montrons qu'il est possible d'utiliser des techniques manuelles pour établir un ensemble réduit de contraintes sur lequel la recherche d’optimisation va se focaliser. Les techniques utilisées peuvent varier d’un horaire à l’autre et vont déterminer la qualité finale de l’horaire. La qualité d’un horaire est influencée par les choix qu’un planificateur fait dans l’utilisation de techniques spécifiques; cette technique reflète alors la perception du planificateur de la notion qualité de l’horaire. Le cadre d’analyse montre qu'un planificateur est capable de sélectionner un ensemble réduit de contraintes, lui permettant d’obtenir des horaires de très bonne qualité. Le fait que l'approche du planificateur est efficace devient clair lorsque ses horaires sont comparés aux solutions heuristiques. Pour ce faire, nous avons transposées les techniques manuelles en un algorithme afin de comparer les résultats avec les solutions manuelles. Mots clés: Confection d’horaires, Confection d’horaires pour résidents, Creation manuelle d’horaires, Heuristiques de confection d’horaires, Méthodes de recherche locale / This thesis provides a problem formulation for the resident scheduling problem, a problem on which very little research has been done. The hospital departments mentioned in this thesis are the paediatrics department of the CHUL (Centre Hospitalier de l’Université Laval) and the emergency department of the Hôpital Enfant-Jésus in Québec City. The main contribution of this thesis is the proposal of a framework for the analysis of manual techniques used in scheduling problems, often described as highly constrained optimisation problems. We show that it is possible to use manual scheduling techniques to establish a reduced set of constraints to focus the search on. The techniques used can differ from one schedule type to another and will determine the quality of the final solution. Since a scheduler manually makes the schedule, the techniques used reflect the scheduler’s notion of schedule quality. The framework shows that a scheduler is capable of selecting a reduced set of constraints, producing manual schedules that often are of very high quality. The fact that a scheduler’s approach is efficient becomes clear when his schedules are compared to heuristics solutions. We therefore translated the manual techniques into an algorithm so that the scheduler’s notion of schedule quality was used for the local search and show the results that were obtained. Key words: Timetable scheduling, Resident scheduling, Manual scheduling, Heuristic schedule generation, Local search methods

Computational Grids are large infrastructures composed of several components such as clusters, or massively parallel machines, generally spread across a country or the world, linked together through some network such as Internet, and allowing a transparent access to any resource. Grids have become unavoidable for a large part of the scientific community requiring computational power such as high-energy physics, bioinformatics or earth observation. Large projects are emerging, often at an international level, but even if Grids are on the way of being efficient and user-friendly systems, computer scientists and engineers still have a huge amount of work to do in order to improve their efficiency. Amongst a large number of problems to solve or to improve upon, the problem of scheduling the work and balancing the load is of first importance.<p><p><p>This work concentrates on the way the work is dispatched on such systems, and mainly on how the first level of scheduling – generally name brokering, or meta-sheduling – is performed. We deeply analyze the behavior of popular strategies, compare their efficiency, and propose a new very efficient brokering policy providing notable performances, attested by the large number of simulations we performed and provided in the document.<p><p><p>The work is mainly split in two parts. After introducing the mathematical framework on which the following of the manuscript is based, we study systems where the grid brokering is done without any feed-back information, i.e. without knowing the current state of the clusters when the resource broker – the grid component receiving jobs from clients and performing the brokering – makes its decision. We show here how a computational grid behaves if the brokering is done is such a way that each cluster receives a quantity of work proportional to its computational capacity.<p><p><p>The second part of this work is rather independent from the first one, and consists in the presentation of a brokering strategy, based on Whittle's indices, trying to minimize as much as possible the average sojourn time of jobs. We show how efficient the proposed strategy is for computational grids, compared to the ones popular in production systems. We also show its robustness to several parameter changes, and provide several very efficient algorithms allowing to make the required computations for this index policy. We finally extend our model in several directions.<p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished

Ce mémoire traite du problème de la planification intégrée de la maintenance préventive et de la production, au niveau tactique, et ce dans le cas d'une entreprise produisant des biens pour satisfaire une demande client périodique. Le plan de production global obtenu s'étale sur un horizon de planification donné. Le système de production considéré est un système multi-états pouvant travailler à des états de fonctionnement intermédiaires entre le fonctionnement de tous les composants et l'arrêt total. Les composants du système sont assujettis à des pannes aléatoires au cours de l'horizon de planification. Dans le but de fournir un plan global de production et de maintenance, nous proposons la résolution de ce problème de planification visant à minimiser le coût global des activités de production et de maintenance, sous différents types de contraintes. Notre apport réside dans le développement et l'implementation de deux méthodes heuristiques utilisant la recherche à voisinage variable et les algorithmes génétiques, dans le but de résoudre ce problème de planification intégrée. Nous procédons ensuite à l'analyse et à la discussion des résultats obtenus afin d'évaluer les performances des heuristiques conçues.

Ces dernières années, le transport de marchandises est devenu un défi logistique à multiples facettes. L’immense volume de fret a considérablement augmenté le flux de marchandises dans tous les modes de transport. Malgré le rôle vital du transport de marchandises dans le développement économique, il a également des répercussions négatives sur l’environnement et la santé humaine. Dans les zones locales et régionales, une partie importante des livraisons de marchandises est transportée par camions, qui émettent une grande quantité de polluants. Le Transport routier de marchandises est un contributeur majeur aux émissions de gaz à effet de serre (GES) et à la consommation de carburant. Au Canada, les principaux réseaux routiers continuent de faire face à des problèmes de congestion. Pour réduire significativement l’impact des émissions de GES reliées au transport de marchandises sur l’environnement, de nouvelles stratégies de planification directement liées aux opérations de routage sont nécessaires aux niveaux opérationnel, environnemental et temporel. Dans les grandes zones urbaines, les camions doivent voyager à la vitesse imposée par la circulation. Les embouteillages ont des conséquences défavorables sur la vitesse, le temps de déplacement et les émissions de GES, notamment à certaines périodes de la journée. Cette variabilité de la vitesse dans le temps a un impact significatif sur le routage et la planification du transport. Dans une perspective plus large, notre recherche aborde les Problèmes de distribution temporels (Time-Dependent Distribution Problems – TDDP) en considérant des chemins dynamiques dans le temps et les émissions de GES. Considérant que la vitesse d’un véhicule varie en fonction de la congestion dans le temps, l’objectif est de minimiser la fonction de coût de transport total intégrant les coûts des conducteurs et des émissions de GES tout en respectant les contraintes de capacité et les restrictions de temps de service. En outre, les informations géographiques et de trafic peuvent être utilisées pour construire des multigraphes modélisant la flexibilité des chemins sur les grands réseaux routiers, en tant qu’extension du réseau classique des clients. Le réseau physique sous-jacent entre chaque paire de clients pour chaque expédition est explicitement considéré pour trouver des chemins de connexion. Les décisions de sélection de chemins complètent celles de routage, affectant le coût global, les émissions de GES, et le temps de parcours entre les nœuds. Alors que l’espace de recherche augmente, la résolution des Problèmes de distribution temporels prenant en compte les chemins dynamiques et les vitesses variables dans le temps offre une nouvelle possibilité d’améliorer l’efficacité des plans de transport... Mots clés : Routage dépendant du temps; chemins les plus rapides dépendant du temps; congestion; réseau routier; heuristique; émissions de gaz à effet de serre; modèles d’émission; apprentissage supervisé / In recent years, freight transportation has evolved into a multi-faceted logistics challenge. The immense volume of freight has considerably increased the flow of commodities in all transport modes. Despite the vital role of freight transportation in the economic development, it also negatively impacts both the environment and human health. At the local and regional areas, a significant portion of goods delivery is transported by trucks, which emit a large amount of pollutants. Road freight transportation is a major contributor to greenhouse gas (GHG) emissions and to fuel consumption. To reduce the significant impact of freight transportation emissions on environment, new alternative planning and coordination strategies directly related to routing and scheduling operations are required at the operational, environmental and temporal dimensions. In large urban areas, trucks must travel at the speed imposed by traffic, and congestion events have major adverse consequences on speed level, travel time and GHG emissions particularly at certain periods of day. This variability in speed over time has a significant impact on routing and scheduling. From a broader perspective, our research addresses Time-Dependent Distribution Problems (TDDPs) considering dynamic paths and GHG emissions. Considering that vehicle speeds vary according to time-dependent congestion, the goal is to minimize the total travel cost function incorporating driver and GHG emissions costs while respecting capacity constraints and service time restrictions. Further, geographical and traffic information can be used to construct a multigraph modeling path flexibility on large road networks, as an extension to the classical customers network. The underlying physical sub-network between each pair of customers for each shipment is explicitly considered to find connecting road paths. Path selection decisions complement routing ones, impacting the overall cost, GHG emissions, the travel time between nodes, and thus the set of a feasible time-dependent least cost paths. While the search space increases, solving TDDPs considering dynamic paths and time-varying speeds may provide a new scope for enhancing the effectiveness of route plans. One way to reduce emissions is to consider congestion and being able to route traffic around it. Accounting for and avoiding congested paths is possible as the required traffic data is available and, at the same time, has a great potential for both energy and cost savings. Hence, we perform a large empirical analysis of historical traffic and shipping data. Therefore, we introduce the Time-dependent Quickest Path Problem with Emission Minimization, in which the objective function comprises GHG emissions, driver and congestion costs. Travel costs are impacted by traffic due to changing congestion levels depending on the time of the day, vehicle types and carried load. We also develop time-dependent lower and upper bounds, which are both accurate and fast to compute. Computational experiments are performed on real-life instances that incorporate the variation of traffic throughout the day. We then study the quality of obtained paths considering time-varying speeds over the one based only on fixed speeds... Keywords : Time-dependent routing; time-dependent quickest paths; traffic congestion; road network; heuristic; greenhouse gas emissions; emission models; supervised learning.

Dans cette thèse, nous traitons essentiellement des problèmes de lot sizing en désassemblage avec une structure de produits à désassembler à deux niveaux sans composants communs. Nous traitons deux problèmes différents. Dans le premier problème, nous considérons un seul produit et la contribution porte sur le développement de deux modèles de programmation en nombres entiers. Le premier modèle est considéré sans ventes perdues où toutes les demandes doivent être satisfaites, et le deuxième est considéré avec ventes perdues où les demandes peuvent ne pas être satisfaites. Pour la résolution de ce problème, nous développons d’abord une approche analytique permettant de calculer les stocks de surplus (avant la résolution du problème) à la fin de l’horizon de planification. Ensuite, nous adaptons trois heuristiques connues pour leurs performances et largement utilisées dans le problème lot sizing en production « Silver Meal, Part Period Balancing et Least Unit Cost ». Dans le deuxième problème, nous considérons plusieurs produits avec contrainte de capacité et la contribution porte sur l’extension des deux modèles précédents. Le premier est également considéré sans ventes perdues et le deuxième avec ventes perdues. En ce qui concerne la résolution de ce problème et compte tenu de sa complexité, un algorithme génétique est d’abord proposé. Ensuite, afin d’améliorer cet algorithme, nous intégrons une heuristique Fix-and-Optimize dans ce dernier tout en proposant une approche hybride. Finalement, des tests sont effectués sur de nombreuses instances de la littérature afin de montrer l’efficacité et les limites de chaque approche de résolution / In this thesis, we mainly deal with lot sizing problems by disassembling with a structure of products to disassemble with two levels and without commonality components. We treat two different problems. In the first problem, we consider a single product whose contribution focuses on developing the two programming models integers. The first model is considered without lost sales where all demands must be satisfied, and the second one is considered with lost sales where demands may not be met. To solve this problem, we first develop an analytical approach to calculate the surplus stocks (before solving the problem) at the end of the planning horizon. Then we adapt three heuristics known for their performance and widely used in the lot sizing problem of production "Silver Meal, Part Period Balancing and Least Unit Cost". In the second problem, we consider a number of products with capacity constraint, and the contribution relates to the extension of the two previous models. The first is considered without lost sales and the second with lost sales. Regarding the resolution of this problem and given its complexity, a genetic algorithm is first proposed. Then, to improve this algorithm, we integrate a Fix-and-Optimize heuristic in the latter while offering a hybrid approach. Finally, various tests are performed on different literature instances to demonstrate the effectiveness and limitations of each solving approach

In this thesis we focus on Stochastic combinatorial Optimization Problems (SCOPs), a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed.<p><p>Optimization problems under uncertainty are complex and difficult, and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others, are emerging as successful alternatives to classical approaches.<p><p>In this thesis, metaheuristics that have been applied so far to SCOPs are introduced and the related literature is thoroughly reviewed. In particular, two properties of metaheuristics emerge from the survey: they are a valid alternative to exact classical methods for addressing real-sized SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics: <p>(1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm;<p>(2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation;<p>(3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances. <p><p>We investigate the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we consider the Ant Colony Optimization metaheuristic and we design efficient local search algorithms that can enhance its performance. We obtain state-of-the-art algorithms, but we show that they are effective only for instances above a certain level of stochasticity, otherwise it is more convenient to solve the problem as if it were deterministic.<p>The algorithmic variants based on an estimation of the objective function by sampling obtain worse results, but qualitatively have the same behavior of the algorithms based on the exact objective function, with respect to the level of stochasticity. Moreover, we show that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and that the effect on local search of ad hoc approximations can be very degrading.<p><p>Finally, we briefly address another SCOP belonging to the class of vehicle routing problems: the Vehicle Routing Problem with Stochastic Demands (VRPSD). For this problem, we have implemented and tested several metaheuristics, and we have studied the impact of integrating in them different ad hoc approximations.<p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

<p>A metaheuristic is a generic algorithmic template that, once properly instantiated, can be used for finding high quality solutions of combinatorial optimization problems.<p>For obtaining a fully functioning algorithm, a metaheuristic needs to be configured: typically some modules need to be instantiated and some parameters need to be tuned. For the sake of precision, we use the expression <em>parametric tuning</em> for referring to the tuning of numerical parameters, either continuous or discrete but in any case ordinal. <p>On the other hand, we use the expression <em>structural tuning</em> for referring to the problem of defining which modules should be included and, in general, to the problem of tuning parameters that are either boolean or categorical. Finally, with <em>tuning</em> we refer to the composite <em>structural and parametric tuning</em>.</p><p><p><p>Tuning metaheuristics is a very sensitive issue both in practical applications and in academic studies. Nevertheless, a precise definition of the tuning problem is missing in the literature. In this thesis, we argue that the problem of tuning a metaheuristic can be profitably described and solved as a machine learning problem.</p><p><p><p>Indeed, looking at the problem of tuning metaheuristics from a machine learning perspective, we are in the position of giving a formal statement of the tuning problem and to propose an algorithm, called F-Race, for tackling the problem itself. Moreover, always from this standpoint, we are able to highlight and discuss some catches and faults in the current research methodology in the metaheuristics field, and to propose some guidelines.</p><p><p><p>The thesis contains experimental results on the use of F-Race and some examples of practical applications. Among others, we present a feasibility study carried out by the German-based software company <em>SAP</em>, that concerned the possible use of F-Race for tuning a commercial computer program for vehicle routing and scheduling problems. Moreover, we discuss the successful use of F-Race for tuning the best performing algorithm submitted to the <em>International Timetabling Competition</em> organized in 2003 by the <em>Metaheuristics Network</em> and sponsored by <em>PATAT</em>, the international series of conferences on the <em>Practice and Theory of Automated Timetabling</em>.</p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished