1,721,187 research outputs found
Vehicule routing problems and industrial application to reduce the ecological footprint
No full textDans cette thèse, nous nous sommes intéressés à la résolution approchée de problèmes de tournées de véhicules. Nous avons exploité des travaux menés sur les graphes d'intervalles et des propriétés de dominance relatives aux tournées saturées pour traiter les problèmes de tournées sélectives plus efficacement. Des approches basées sur un algorithme d'optimisation par essaim particulaire et un algorithme mémétique ont été proposées. Les métaheuristiques développées font appel à un ensemble de techniques particulièrement efficaces telles que le découpage optimal, les opérateurs de croisement génétiques ainsi que des méthodes de recherches locales. Nous nous sommes intéressés également aux problèmes de tournées classiques avec fenêtres de temps. Différents prétraitements ont été introduits pour obtenir des bornes inférieures sur le nombre de véhicules. Ces prétraitements s'inspirent de méthodes issues de modèles de graphes, de problème d'ordonnancement et de problèmes de bin packing avec conflits. Nous avons montré également l'utilité des méthodes développées dans un contexte industriel à travers la réalisation d'un portail de services mobilité.In this thesis, we focused on the development of heuristic approaches for solvingvehicle routing problems. We exploited researches conducted on interval graphsand dominance properties of saturated tours to deal more efficiently with selectivevehicle routing problems. An adaptation of a particle swarm optimization algorithmand a memetic algorithm is proposed. The metaheuristics that we developed arebased on effective techniques such as optimal split, genetic crossover operatorsand local searches. We are also interested in classical vehicle problems with timewindows. Various pre-processing methods are introduced to obtain lower boundson the number of vehicles. These methods are based on many approaches usinggraph models, scheduling problems and bin packing problems with conflicts. Wealso showed the effectiveness of the developed methods with an industrial applicationby implementing a portal of mobility services
Problèmes d’acheminement sélectif des véhicules lors de feux de forêt
No full textLors de la dernière décennie, environ 82 millions d’hectares de végétation ont été détruites dans des feux de forêt. Ces incendies mettent en danger la nature mais aussi, dans les zones urbaines, des vies humaines et les infrastructures. Le danger croissant des incendies, exacerbé par le changement climatique, incite au développement d’outils stratégiques pour y répondre efficacement, notamment par le biais du projet GEO-SAFE. Parmi les nombreuses problématiques liées, les travaux de cette thèse se concentrent sur le problème de protection des biens (APP), et sa version perturbée, D-APP. Ces problèmes visent à déployer des flottes de pompiers pour assurer des opérations préventives de protection. Les méthodes de résolution exactes existantes, en particulier de programmation linéaire en nombres entiers (PLNE) pour APP, ne sont pas efficaces. Nous avons étudié la structure du problème afin d’obtenir de franches améliorations, notamment via l’introduction de trois ensembles d’inégalités valides. Ces améliorations ont non seulement grandement réduit les temps de résolution, ils ont permis d’avoir une méthode de résolution stable pour les petites instances. En parallèle, une nouvelle formulation PLNE de D-APP, plus efficace, a été proposée, basée sur une relation de dominance entre les solutions. Toutefois, les méthodes de résolution exactes sont mal adaptées à des scénarios en temps réel : cette thèse introduit également deux méthodes de résolution heuristique adaptées à notre problème. La première, reposant sur la reformulation, utilise une approche relax-and-fix. La seconde implémente un algorithme génétique. Ces méthodes ont généré des solutions approchées de bonne qualité en temps limité, permettant de déployer des réponses rapidement et efficacement. A travers ces contributions, ces travaux s’inscrivent dans la lutte contre les incendies, en renforçant la synergie entre techniques d’optimisation et gestion de crises.In the last 10 years, around 82 million hectares of forests have been destroyed by wildfires. These fires pose imminent threats to the wildlife, as well as in urban areas, to human lives and critical infrastructure. The need for a strategic and resource-efficient response to the growing threat of wildfires, exacerbated by climate change, led to the launch of the GEO-SAFE project. Among its many challenges, this thesis focuses on the Asset Protection Problem during escaped wildfires (APP) and its disrupted counterpart, D-APP. These problems aim to route firefighting crews to carry out protection operations on community assets. Existing exact methods, particularly the Mixed Integer Program (MIP) for APP, struggled with efficiency. We performed a structural analysis that led to significant enhancements, notably the introduction of three sets of valid inequalities. These improvements not only decreased solution times but also stabilized an exact solution method for smaller instances. In parallel, D-APP’s complex replanning requirements for larger instances were met through a novel reformulation based on a dominance relation on the solutions of the problem. Acknowledging the limitations of exact methods in real-time scenarios, this thesis introduces two heuristic approaches tailored for D-APP. The first, based on the new formulation, uses a relax-and-fix approach, while the second implements a genetic algorithm. These methods generated good approximate solutions in a limited time, paving the way for rapid and effective wildfire response strategies. Through these contributions, this work stands as a testament to the ongoing battle against wildfires, reinforcing the synergy between computational techniques and real-world disaster management
Modelisation and conception of algorithms for timetabling problems
No full textLes problèmes de planification font référence à des situations où il faut prendre des décisions sur l’affectation de ressources limitées pour réaliser certaines tâches ou atteindre des objectifs donnés, tout en respectant un ensemble de contraintes. Nous avons étudié dans cette thèse deux problèmes de planification : le problème de planification de cours de l’UTC (University Course TimeTabling Problem of UTC university, UTCUCTTP) et le problème de planification d’équipes de pompiers de l’institution INFOCA (FireFighters Timetabling Problem, FFTP). Les deux problèmes sont issus de situations réelles. Pour les deux problèmes étudiés, nous avons défini l’ensemble des données et des contraintes suite aux échanges avec le SME de l’UTC et les pompiers de l’institution INFOCA. Un générateur d’instances a été développé pour chaque problème afin de pouvoir générer un benchmark pour tester les méthodes proposées pour résoudre chacun des deux problèmes. Les institutions de formation font face à des problèmes complexes de planification. La conception des plannings devient un enjeu majeur dans un cadre budgétaire contraint. Nous avons étudié dans le premier problème traité, le problème de planification de cours de l’UTC (UTC-UCTTP). Le problème consiste à programmer des activités d’enseignement dans des salles et des timeslots, et les affecter à des enseignants. L’enjeu est d’obtenir des emplois du temps de bonne qualité en respectant les différentes contraintes du problème. Nous avons proposé un modèle ILP, une heuristique AIDCH et une métaheuristique ALNS. Les approches proposées ont été testées à l’aide d’un benchmark de vingt instances que nous avons générées à partir de données réelles. Les résultats obtenus par la méthode ALNS sont satisfaisants dans des temps de traitement raisonnables. Le deuxième problème que nous avons étudié est le problème de planification d’équipes de pompiers FFTP de l’institution INFOCA pour lequel les équipes de pompiers doivent être affectées à des quarts de travail au cours de la période à haut risque de feux de forêt. L’enjeu est d’obtenir une capacité opérationnelle maximale en considérant les contraintes qui permettent d’atteindre cette capacité opérationnelle, en plus des contraintes liées à la réglementation du travail. Nous avons présenté un modèle ILP, une matheuristique ILPH et une métaheuristique ALNS. Les approches proposées ont été testées à l’aide de quatre datasets de taille croissante que nous avons généré à partir de données réelles. L’ALNS a obtenu tous les résultats optimaux atteints en utilisant le modèle ILP sur les plus petites instances. Pour les plus grandes instances, les résultats sont de meilleure qualité par rapport à ceux obtenus par la matheuristique ILPH, et les temps de traitement sont significativement réduits.Planning problems refer to situations where decisions must be made on the allocation of limited resources to carry out certain tasks or achieve given objectives, while respecting a set of constraints. We studied in this thesis two timetabling problems: the UTC course timetabling problem (University Course TimeTabling Problem of UTC university, UTC-UCTTP) and the firefighters timetabling problem of the INFOCA institution (Firefighters Timetabling Problem, FFTP). Both problems stem from real-life situations. For the two problems studied, we defined all the data and constraints following discussions with the SME of UTC and the firefighters of the INFOCA institution. An instance generator was developed for each problem in order to be able to generate a benchmark to test the methods proposed to solve each of the two problem. Universities face complex planning problems. The design of schedules becomes a major issue in a constrained budgetary framework. We studied in the first problem treated, the UTC course timetabling problem (UTC-UCTTP). The problem is t schedule activities in rooms and timeslots, and assign them to lecturers. The challenge is to obtain good quality timetables while respecting the different constraints of the problem. We proposed an ILP model, an AIDCH heuristic and an Al-NS metaheuristic. The proposed approaches were tested using a benchmark of twenty instances that we generate from real data. The results obtained by the ALNS method are satisfactory within reasonable processing time. The second problem we studied is the INFOCA institution firefighters timetabling problem for which fire crews need to be assigned to shifts during the high wildfire risk period. The challenge is to obtain maximum operational capacity by considering the constraints which make it possible to achieve this operational capacity, in addition to the constraints linked to labor regulations. We presented an ILP model, an ILPH matheuristic and an Al-NS metaheuristic. The proposed approaches were tested using four datasets of increasing size that we generated from real data. Al-NS achieved all the optimal results achieved using the Il-P model on the smallest instances. For larger instances, the results are of better quality compared to those obtained by Il-PH matheuristics, and processing times are significantly reduced
Resource planning and scheduling of tasks in the inter and intra hospital logistics chain
No full textLes hôpitaux doivent prendre en compte la logistique pour améliorer les liens entre les systèmes de santé (entre les établissements et entre les divisions au sein d’un hôpital) afin de promouvoir la cohérence et l’efficacité. La logistique hospitalière implique une bonne coordination des services de prise en charge des patients. Les patients en situation d’urgence se rendent généralement en premier lieu au service des urgences. Une visite aux urgences peut révéler qu’un patient a besoin d’une intervention chirurgicale à programmer plus tard. Cela crée des patients en chirurgie élective. Dans le cadre de l’ANR OIILH, nous avons proposé des solutions pour le problème d’ordonnancement des tâches de parcours de soins de patients. Nous avons également étudié le problème de planification d’interventions chirurgicales. Pour le problème des urgences, nous avons considéré en premier lieu le cas statique. Nous avons réalisé un générateur d’instances basé sur les données réelles du service d’urgence du CHU Jeanne de Flandres de Lille. Nous avons implémenté une approche heuristique constructive permettant de gérer les ressources en suivant deux règles métier utilisées par les praticiens. Nous avons proposé une modélisation mathématique du problème. Le modèle a été implémenté et utilisé pour obtenir des solutions de références pour les instances générées. Nous avons élaboré une approche heuristique itérative basée sur la destruction et la construction d’une solution. Les résultats montrent que des solutions de meilleure qualité par rapport à l’heuristique constructive peuvent être obtenues en des temps raisonnables. Des solutions optimales peuvent être trouvées pour les petites instances. Ensuite, nous avons élaboré une méta-heuristique « Adaptive Large Neighborhood Search (ALNS) » plus efficace. Les résultats expérimentaux montrent l’efficacité de cette approche avec des temps de calcul faibles qui sont adéquats par rapport à la réactivité requise dans le cas dynamique du problème. Nous avons proposé une approche de planification prédictive et réactive pour le cas dynamique. Nous construisons, modifions et améliorons le planning en utilisant les méthodes de résolution du cas statique. Pour le service de chirurgie, des interventions chirurgicales non urgentes et non immédiates doivent être programmées à l’avance. Nous avons développé deux approches de résolution pour ce problème en aval du service des urgences. Nous avons proposé une heuristique en deux phases et une approche ALNS qui donnent des résultats strictement meilleurs que ceux de la littérature.Hospitals must take into account logistics to improve the connections between healthcare systems (between facilities and within hospital divisions) in order to promote consistency and efficiency. Hospital logistics involves effectiv coordination of patient care services. Patients in emergency situations typically first go to the emergency department. A visit to the emergency department may reveal that a patient needs a surgical intervention to be scheduled later. This creates elective surgery patients. As part of the ANR OIILH project, we proposed solutions to the patient care pathway scheduling problem. We also studied the problem of scheduling surgical interventions. For the emergency department problem, we first considered the static case. We developed an instance generator based on real data from the emergency department at CHU Jeanne de Flandres in Lille. We implemented a constructive heuristic approach to manage resources following two business rule used by practitioners. We proposed a mathematical modeling of the problem. The model was implemented and used to obtain reference solutions for generated instances. We developed an iterative heuristic approach based on the destruction and construction of a solution. The results show that solutions of higher quality compared to the constructiv heuristic can be obtained in reasonable time frames. Optimal solutions can be found for small instances. Then, we developed a more efficient Adaptive Large Neighborhood Search (ALNS) metaheuristic. Experimental results demonstrat the effectiveness of this approach With Iow computing times suitable for the required responsiveness in dynamic proble cases. We proposed a predictive and reactive planning approach for the dynamic case. We build, modify, and improve the plan using static case resolution methods. For the surgery service, non-urgent and non-immediate surgical interventions need to be scheduled in advance. We developed two resolution approaches for this problem downstream from the emergency department. We proposed a two-phase heuristic and an ALNS approach that produce results strictly better than those in the literature
Problèmes de tournées sélectives dans les réseaux collaboratifs de transport urbain
No full textLe but de ce travail de thèse réside dans la planification de la distribution urbaine des marchandises dans un système de transport collaboratif. Cette collaboration consiste à échanger les demandes de transport entre transporteurs afin d'améliorer l'efficacité de leurs opérations. Cela revient à minimiser la distance parcourue par les camions et à maximiser le profit collecté des clients, notamment en recourant à des variantes du problème de tournées de véhicules plus adaptées au contexte collaboratif. Le problème opérationnel sous-jacent est donc le problème de tournées de véhicules sélectives dans lequel le service de tous les clients n'est pas obligatoire par contre un "profit" est collecté lors du service d'un client. Dans cette thèse, nous traitons le problème de tournées de véhicules sélectives avec contraintes de temps et de capacité (Capacitated Team Orienteering Problem - CTOP). Nous proposons une métaheuristique qui alterne entre deux espaces de recherche. Des procédures de découpage optimal et de concaténation permettent de passer d'un espace à un autre. D'autre part, en considérant des demandes de collecte et de livraison, nous traitons deux variantes sélectives du problème de collecte et de livraison (Pickup and Delivery Problem - PDP) : le PDP avec fenêtres de temps et demandes obligatoires (PDPTWPR) et le PDPTWPR avec demandes groupées. La première variante consiste à choisir parmi les demandes de transport optionnelles quelles demandes à servir en plus des demandes obligatoires. Nous développons des métaheuristiques pour traiter les cas mono-objectif et multi-objectif du problème. Le PDPTWPR avec demandes groupées prend en considération les demandes de transport qui doivent être servies par un même transporteur. Finalement, nous considérons la variante sélective dans laquelle les marchandises sont distribuées d'un même dépôt vers les clients (Capacitated Profitable Tour Problem - CPTP). L'objectif est de maximiser la différence entre le coût et le profit. Pour résoudre ce problème, nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers à laquelle nous ajoutons plusieurs inégalités valides spécifiques à ce problème. Des expérimentations ont été conduites sur plusieurs classes d'instances afin de montrer l'efficacité de nos approches.The goal of this thesis is to plan urban freight distribution in a collaborative logistic system. The collaboration consists in exchanging transportation requests between carriers to increase the efficiency of their operations. More precisely, when solving variants of the wellknown vehicle's routing problems in collaborative context, less kilometers can be driven and higher prices can be collected. The underlying operational problem is therefore the selective vehicle routing problem in which not all customers can be served, but a "profit" is gained for each served one. In this thesis, we firstly address the Capacitated Team Orienteering Problem (CTOP), a selective variant of the VRP in which capacity and travel time limitations are imposed to vehicles. We propose a variable space search metaheuristic that alternates between two different search spaces to solve CTOP. Then, we consider pickup and delivery requests to study two variants of the selective pickup and delivery problem: the PDP with Time Windows and Reserved requests (PDPTWPR) and the Clustered PDPTWPR. The first aims to choose suitable selective requests to be transported in addition to reserved ones. Metaheuristics are proposed to deal with the single-objective and the multi-objective sides of the problem. The second takes into consideration groups of requests that must be served by only one carrier. Finally, we consider the Capacitated Profitable Tour Problem (CPTP) in which goods need to be distributed from the depot to customers. We propose an exact method based on Integer Linear Programming to solve this problem. A set of cuts specific to CPTP is proposed in order to speed up the solution process. Experiments were conducted on a variety of instances of different sizes to demonstrate the effectiveness of our solution methods
Scheduling problems with production and consumption of resources
No full textLa plupart des travaux de recherches sur les problèmes d'ordonnancement traitent le cas des ressources renouvelables, c'est-à-dire des ressources qui sont exigées en début d'exécution de chaque tâche et sont restituées en fin d'exécution. Peu d'entre eux abordent les problèmes à ressources consommables, c'est-à-dire des ressources non restituées en fin d'exécution. Le problème de gestion de projet à contraintes de ressources (RCPSP) est le problème à ressources renouvelables le plus traité dans la littérature. Dans le cadre de cette thèse, nous nous sommes intéressés à une généralisation du problème RCPSP qui correspond au cas où les tâches sont remplacées par des événements liés par des relations de précédence étendues. Chaque événement peut produire ou consommer une quantité de ressources à sa date d'occurrence et la fonction économique reste la durée totale à minimiser. Nous avons nommé cette généralisation ERCPSP (Extended RCPSP). Nous avons élaboré des modèles de programmation linéaire pour résoudre ce problème. Nous avons proposé plusieurs bornes inférieures algorithmiques exploitant les travaux de la littérature sur les problèmes cumulatifs. Ensuite, nous avons élargi la portée des méthodes utilisées pour la mise en place de méthodes de séparation et évaluation. Nous avons traité aussi des cas particuliers par des méthodes basées sur la programmation dynamique.This thesis investigates the Extended Resource Constrained Project Scheduling Problem (ERCPSP). ERCPSP is a general scheduling problem where the availability of a resource is depleted and replenished at the occurrence times of a set of events. It is an extension of the Resource Constrained Project Scheduling Problem (RCPSP) where activities are replaced by events, which have to be scheduled subject to generalized precedence relations. We are interested in this thesis in proposing new methodologies and approaches to solve ERCPSP. First, we study some polynomial cases of this problem and we propose a dynamic programming algorithm to solve the parallel chain case. Then, we propose lower bounds, mixed integer programming models, and a branch-and-bound method to solve ERCPSP. Finally, we develop an instance generator dedicated to this problem
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Problèmes de tournées de véhicules avec profits, méthodes exactes et approchées
No full textNous nous intéressons dans cette thèse à la résolution du problème de tournées sélectives (Team Orienteering Problem - TOP) et ses variantes. Ce problème est une extension du problème de tournées de véhicules en imposan tcertaines limitations de ressources. Nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers (PLNE) en ajoutant plusieurs inégalités valides capables d’accélérer la résolution. D’autre part, en considérant des périodes de travail strictes pour chaque véhicule durant sa tournée, nous traitons une des variantes du TOP qui est le problème de tournées sélectives multipériodique (multiperiod TOP - mTOP) pour lequel nous développons une métaheuristique basée sur l’optimisation par essaim pour le résoudre. Un découpage optimal est proposé pour extraire la solution optimale de chaque particule en considérant les tournées saturées et pseudo saturées .Finalement, afin de prendre en considération la disponibilité des clients, une fenêtre de temps est associée à chacun d’entre eux, durant laquelle ils doivent être servis. La variante qui en résulte est le problème de tournées sélectives avec fenêtres de temps (TOP with Time Windows - TOPTW). Deux algorithmes exacts sont proposés pour résoudre ce problème. Le premier est basé sur la génération de colonnes et le deuxième sur la PLNE à laquelle nous ajoutons plusieurs coupes spécifiques à ce problème.We focus in this thesis on developing new algorithms to solve the Team Orienteering Problem (TOP) and two of its variants. This problem derives from the well-known vehicle routing problem by imposing some resource limitations .We propose an exact method based on Mixed Integer Linear Programming (MILP) to solve this problem by adding valid inequalities to speed up its solution process. Then, by considering strict working periods for each vehicle during its route, we treat one of the variants of TOP, which is the multi-period TOP (mTOP) for which we develop a metaheuristic based on the particle swarm optimization approach to solve it. An optimal split procedure is proposed to extract the optimal solution from each particle by considering saturated and pseudo-saturated routes. Finally, in order to take into consideration the availability of customers, a time window is associated with each of them, during which they must be served. The resulting variant is the TOP with Time Windows (TOPTW). Two exact algorithms are proposed to solve this problem. The first algorithm is based on column generation approach and the second one on the MILP to which we add additional cuts specific for this problem. The comparison between our exact and heuristic methods with the existing one in the literature shows the effectiveness of our approaches
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
