Au cours des dernières décennies, de grands efforts en recherche et développement ont été faits pour développer et promouvoir les véhicules électriques (VEs). La plupart de ces recherches portent essentiellement sur le développement des moteurs électriques de ces véhicules et des technologies de batteries de recharge. Cependant, un des obstacles majeurs pour le déploiement des VEs à grande échelle réside dans l'incertitude d’assister et de guider les conducteurs de ce type de véhicule d’une façon appropriée pour atteindre les stations de recharge tout en satisfaisant leurs souhaits (points de recharge disponibles, moins d’attente possible, proposition d’autres points d’intérêts : restaurant, shopping, etc.). Afin de remédier à ce manque, nous proposons dans ce travail de thèse une approche distribuée et adaptative orientée modèles pour la gestion de l'énergie pour la recharge des VEs. Pour ce faire, nous nous somme focalisés sur la modélisation des processus de recharge en utilisant une approche formelle basée sur des outils de systèmes à événements discrets, à savoir l'algèbre (max, +) et les réseaux de Petri. Les modèles développés ont permis d’étudier, d’analyser et d’évaluer le comportement du système de recharge. De plus, une approche d'optimisation basée sur la programmation linéaire est proposée afin d’affecter et d’orienter d'une façon optimale les VEs vers les stations de recharge appropriées et ordonnancer leurs opérations de recharge. Afin de prédire le taux et la durée de recharge moyens des VEs compte tenu des dates d’arrivée des demandes de recharge et l'état de recharge de chaque véhicule, une approche dédiée basée sur une fonction prédictive est proposée. En utilisant cette approche, les opérations de recharge pourraient être planifiées en minimisant les temps d'attente des VEs au sein des stations de recharge et en assurant un taux de recharge acceptable pour chaque demande. Les résultats d’analyse et de simulations obtenus ont montré que les approches de modélisation, d’optimisation et de prédiction proposées permettent d’affecter de façon adéquate et optimale les VEs aux stations de recharge tout en satisfaisant toutes les contraintes du processus de recharge. / In the last decades, very great research and development efforts have been made to develop and promote electric vehicles (EVs). Most efforts have been made to further develop the power engine of these vehicles and batteries technologies. However, one of the major obstacles to the large deployment of EVs is the uncertainty of drivers to get a suitable and vacant place at a charging station (CS). In this manuscript, we focus on the charging process modelling using formal approaches based on discrete event system tools namely (max,+) algebra and Petri nets. In addition, an optimization approach based on linear programming is proposed to optimally assign and reroute EVs to the suitable CSs and schedule their charging operations. In order to predict, manage and handle charging needs of EVs, a dedicated model based on a predictive function is introduced. The aim is to predict the average charging rate and time while considering the inter-arrival of charging requests and the state of charging of EVs. Using this approach, charging operations could be planned while minimizing waiting times of EVs and avoiding queuing situations within CSs. Simulation results showed that the proposed approaches allow assigning adequately and optimally EVs to CSs while satisfying all process constraints.

Les villes sont des systèmes complexes que les modèles urbains peuvent aider à comprendre. Des modèles les plus simplistes aux modèles les plus sophistiqués, la modélisation urbaine a permis de mieux comprendre la question urbaine et ses implications sociétales. Dans ce contexte, les modèles peuvent avoir une valeur-ajoutée appréciable dans le processus de décision publique. Encore faut-il que ces modèles deviennent pratiques et répondent aux contraintes opérationnelles de la chaîne de décision. Dans ce sens, peu de recherches s’est intéressée à la question de praticité des modèles urbains et leur utilisation en situation opérationnelle. À ce jour, les modèles urbains standard qui reposent sur une description agrégée de l’espace sont parmi les approches de modélisation les plus opérationnelles et aussi les plus répandues. De par sa relative praticité, cette approche standard est attractive et simple à mettre en oeuvre. Toutefois, l’agrégation spatiale peut aussi être une source de biais statistiques préjudiciables à la qualité de la modélisation. C’est en particulier, le cas des modèles intégrés Transport-Urbanisme ou des modèles de transport à quatre étapes.La présente thèse a pour objectif d’étudier la question de l’agrégation spatiale dans les modèles transport et plus particulièrement dans les modèles d’affectation des déplacements. Les modèles d’affectation servent à calculer les temps de parcours et les conditions de déplacement sous congestion, présents et futurs, des personnes et des marchandises. Ils servent aussi à calculer les accessibilités nécessaires aux modèles d’usage des sols dont les modèles de choix de localisation des ménages et des entreprises. Toute erreur ou biais dans l’affectation des déplacements peut compromettre la validité et la qualité globales de la modélisation. Dans ce cadre, une attention particulière doit être allouée au problème d’agrégation spatiale dans les modèles d’affectation. Dans ces modèles, l’agrégation spatiale consiste à regrouper les observations individuelles enutilisant une description agrégée de l’espace, i.e. des zones. Par nature, l’utilisation d’une description agrégée à la place d’une représentation continue engendre une omission de l’information et de sa variabilité et donc un biais statistique dans la modélisation. C’est le cas par exemple avec l’utilisation des connecteurs de zones ou avec l’omission des trafics intrazones dans les modèles d’affectation.En reposant sur les zones comme unité spatiale de base, les modèles de transport recourent à l’utilisation des connecteurs de zones pour relier les centroïdes de zones au réseau de transport. Les connecteurs sont des liens fictifs qui modélisent les conditions moyennes d’entrée et de sortie du réseau de transport. Pour ce faire, la majorité des modèles de transport reposent sur une méthode simpliste sujette au problème d’agrégation spatiale. La présente thèse examine en détail l’impact de cette description simpliste sur les résultats et la qualité d’un modèle d’affectation des déplacements en transports en commun. Cette thèse propose aussi une nouvelle méthode de modélisation des connecteurs de zones afin de s’affranchir partiellement du biaisd’agrégation spatiale dans la modélisation des conditions d’accès au réseau des transports en commun.L’utilisation des zones comme unité spatiale de base a aussi pour conséquence l’omission des trafics intrazones de l’affectation des déplacements. Les trafics intrazones ont pour origine et pour destination la même zone et de ce fait ne sont pas pris en compte par les modèles standard d’affectation. Cette omission a souvent été ignorée et son impact sur la qualité de la modélisation demeure non évalué. Cette thèse développe une méthode stochastique pour l’évaluation de cet impact... / Cities are complex systems that urban models can help to comprehend. From simplistic models to more sophisticated ones, urban models have pushed forward our understanding the urban phenomenon and its intricacies. In this context, models can be of great value to policy makers providing that these tools become practical. In this regard, research has put little emphasis on the practicality of urban models and their use under operational conditions.To date, urban models which rely on spatial aggregation are the closest possibility to come to practical models. For this reason, the spatially aggregated modeling framework is widely used. This framework is relatively practical when compared to other modeling frameworks like microsimulation. Nevertheless, spatial aggregation is a serious source of bias in these models. This is especially the case of Land-Use and Transport Interaction (LUTI) models and more particularly of Four Step Models.The current PhD is committed to the study of spatial aggregation issues in traffic assignment models. Traffic assignment is responsable for the computation of travel times and travel conditions of present and future travel demand. Accessibility measurement, which is at the core of LUTI models, is tightly dependent on traffic assignment modeling and outcomes. Any bias in traffic assignment is likely to corrupt the overall modeling framework. In this context, a special attention is to be paid to spatial aggregation in traffic assignment models.In traffic assignment, spatial aggregation consists in grouping observations using zones or traffic analysis zones instead of using a continuous representation of space. By design, aggregation bears an implicit omission in data variability and thus a potential bias if this omission is not random. This is the case with the definition of centroid connectors and the omission of intrazonal demand in traffic assignment. With the use of zones as the basic spatial units, transport models require the use of centroid connectors to attach zones to the transportation network. Centroid connectors are introduced to model average access and egress conditions to and from the network. Nevertheless, average accessibility conditions are found to be too crude to render accurately accessibility conditions as encountered by trip makers. The current PhD explores the extent of the impact of this spatial aggregation bias in the case of transit models and suggests a new modeling strategy to overcome such modeling errors.The use of zones as spatial units induces a loss of intrazonal data. The omission of intrazonal trips in traffic assignment models is an example of such omission. This research introduces an uncertainty framework to study the statistical impact of ignoring intrazonal trips in traffic assignment models. Findings from this research are used to design new assignment strategies that are more robust towards the omission bias and more generally towards the spatial aggregation bias.

Ce travail présente une méthode et des outils pour l'ordonnancement en temps réel d'atelier lorsque des contraintes complexes issues du terrain sont à prendre en compte. L'approche retenue vise à caractériser non pas une solution au problème d'ordonnancement, mais un ensemble de solutions sous la forme de groupes d'opérations permutables. Dans ce contexte, on considère un ensemble d'ordres de fabrication, chacun comportant une date de livraison et une date de début au plus tôt et étant composé d'un ensemble d'opérations d'exécution. Chaque opération d'exécution nécessite simultanément pour sa réalisation un ensemble de ressources cumulatives ou disjonctives, chacune d'elles devant être sélectionnée dans un ensemble prédéfini appelé pool. Les contraintes de précédence entre les opérations d'exécution d'un même ordre de fabrication sont définies par des gammes non linéaires. On propose de caractériser l'activité de préparation nécessaire sur un sous-ensemble des ressources requises pour réaliser une opération d'exécution, par un enchaînement de trois opérations élémentaires de préparation : le démontage, le changement de type et le montage. Chaque activité de préparation dépend de la séquence des opérations d'exécution et chaque opération de préparation peut nécessiter également des ressources complémentaires. Un graphe potentiels-tâches particulier est utilisé pour représenter une séquence de groupes. Basé sur une exploration de ce graphe, un algorithme polynomial d'insertion d'une opération dans un ordonnancement visant à minimiser la conséquence de cette insertion sur les dates de livraison, est défini. Cet algorithme est utilisé dans les méthodes proposées pour générer une séquence de groupes initiale et pour l'amélioration de type tabou de cette séquence. Ces méthodes sont validées sur des problèmes classiques d'ordonnancement de projet et sur des problèmes d'ordonnancement d' atelier avec préparation générés aléatoirement. Un système interactif d'aide à la décision est proposé pour l'ordonnancement en temps réel d'un atelier avec préparation, basé sur l'exploitation de la séquence de groupes. La nouvelle version du logiciel d'ordonnancement en temps réel ORDO basée sur ce travail est déjà installée sur plusieurs sites industriels.

Les établissements de santé sont confrontés à de nouveaux défis tels que le vieillissement de la population, la hausse des coûts des soins et les progrès rapides des technologies médicales. Les nouvelles politiques de contrôle du budget des soins ont été introduites pour augmenter l'efficacité, réduire les déchets et remodeler le système de santé.Ces établissements cibles présentent des réseaux complexes incluant de ressources humaines,financières, structurelles et technologiques visant à garantir les meilleurs soins. Ces enjeux concernent d'autant plus les services d'urgence engorgés par l'afflux massif des passages, qui doivent fournir des décisions rapides et assurer le dimensionnement de ses ressources afin de réduire les délais d'attente des patients sans compromettre la qualité de soin.L'objectif de cette thèse est de proposer des solutions appropriées aux services d'urgences permettant d'améliorer la prise en charge des patients en termes de temps d'attente. Nous avons commencé par analyser les problématiques de la filière des urgences afin d'engager une démarche d'amélioration. Par la suite, nous avons modélisé le processus de prise en charge des patients au service d'accueil des urgences à l'aide d'un système multi-agent ouvert et dynamique. Le système proposé permet de fournir une aide à la décision sur la planification de l'activité médicale et l'affectation des ressources humaines dans une unité où on se trouve souvent face à une situation d'urgence nécessitant une prise en charge rapide et efficace. Dans ce contexte, nous abordons le problème réactif d'optimisation de l'ordonnancement des opérations de soin et le problème de coordination du personnel médical. Nous nous intéressons au dimensionnement des ressources humaines au SU en adoptant une approche de prise en compte des compétences maîtrisées dans le but de trouver une adéquation avec celles requises par l'activité médicale afin avant tout d'accroitre la qualité, réduire les délais d'attente et permettre de dégager des gains de gestion

Cette thèse s'intéresse à l'allocation de ressources des réseaux WMAN (Wireless Metropolitan Area Networks) utilisant l'OFDMA (Orthogonal Frequency Division Multiple Access). Les applications récentes destinées aux réseaux sans fils requièrent des débits importants. L'OFDMA, technique d'accès multiple basée sur l'OFDM(Orthogonal Frequency Division Multiplexing), permet d'obtenir des débits élevés en tirant avantage de la diversité multiutilisateur. Dans une première partie, l'allocation de ressources est considérée au niveau de la couche physique (affectation des fréquences et de la puissance). Dans un contexte monocellulaire, un algorithme est proposé afin de maximiser le débit de la cellule tout en assurant des débits individuels aux utilisateurs (problème RA, Rate Adaptive optimization). L'impact de la sous canalisation sur le débit global est analysé. Puis, un algorithme est proposé dans un contexte multicellulaire pour adapter dynamiquement le facteur de réutilisation fréquentiel. Dans une deuxième partie, l'ordonnancement est traité. L'objectif est de garantir les délais du trafic temps réel, de maximiser le débit du trafic non temps réel tout en assurant une équité proportionnelle entre les flux. Pour cela, les extensions du GPS (Global Processor Sharing) sont étudiées. Deux algorithmes, extensions du WFS (Wireless Fair Service) pour l'OFDMA, sont proposés. Leurs performances sont comparées au WFS et aux algorithmes existants en OFDMA. L'une des propositions, l'OWFS (Opportunist Wireless Fair Service) est particulièrement adaptée pour maximiser le débit du trafic non temps réel et comporte un paramètre, le poids de délai, qui permet de maintenir un taux de pertes acceptable pour le trafic temps réel.

Le contexte général de mes travaux se situe dans les réseaux orientés connexions, que ce soit des réseaux optiques à multiplexage en longueur d'onde (WDM), des réseaux MPLS (multi-protocol label switching), ou encore des réseaux à faisceaux hertziens (wireless backhaul networks). Dans ces réseaux, je m'intéresse à router les flux d'information, à agréger des flux d'information bas débits dans des flux de plus hauts débits, à faire évoluer le routage en cas de variations dans la quantité de trafic à transporter ou dans la topologie du réseau, et à assurer la continuité du trafic en cas de panne simple ou multiple. Pour aborder ces questions, j'utilise des outils variés de l'algorithmique, de la théorie des graphes et de l'optimisation combinatoire.<br /> L'ensemble des résultats présentés dans ce document est le fruit de travaux collaboratifs avec les membres de l'équipe-projet MASCOTTE, des collègues d'autres universités, française ou étrangères, et des collègues de France Télécom, Alcatel-Lucent et 3Roam. L'introduction de ce manuscrit résume nos travaux sur le routage, le groupage de trafic, la tolérance aux pannes et la reconfiguration, ainsi que des travaux plus récents sur la minimisation du nombre d'étiquettes dans les réseaux MPLS, le dimensionnement de réseaux de collecte IP sans fil, et sur le routage disjoints d'ensembles particuliers de requêtes. Ensuite, je détaille nos travaux sur le groupage de trafic au travers d'un état de l'art dans le chapitre 3, nos contributions sur la notion de groupes de ressources partageant un risque dans le chapitre 4, et sur la reconfiguration de routages dans le chapitre 5. Le chapitre 6 conclut ce manuscrit en présentant avec quelques directions de recherches.

Les systèmes assemble-to-order (ATO) peuvent être considérés comme une affectation de ressources multiples qui induit planification de production, satisfaction des contraintes et affectation des stocks. Les systèmes ATO représentent une stratégie de logistique populaire utilisée en gestion de fabrication. En raison de la complexité croissante des systèmes de fabrication d'aujourd'hui, le défi pour les systèmes ATO est de gérer efficacement les stocks de composants et de trouver les décisions optimales de production et d'affectation.Nous étudions un système ATO avec un produit unique qui est assemblé à partir de plusieurs composants. Le système doit répondre à une demande non seulement du produit assemblé, mais aussi des composants individuels. Nous considérons le cas avec seulement des lost sales puis le cas mixte lost sales et backorders avec des temps de production suivant des lois de type exponentiel et une demande sous forme de loi de Poisson. Nous formulons le problème comme un Processus de décision markovien (MDP), et nous considérons deux critères d'optimalité qui sont le coût actualisé et le coût moyen par période. Nous caractérisons la structure de la politique optimale et étudions l'impact des différents paramètres du système sur cette politique. Nous présentons également plusieurs heuristiques pour le cas lost sales et le cas mixte lost sales et backorders. Ces heuristiques fournissent des méthodes simples, mais efficaces pour contrôler la production et l'affectation des stocks du système ATO

Cette thèse se divise en trois parties. La première est consacrée à la conception d'une chaîne d'approvisionnement au niveau stratégique. Une approche systématique est proposée; elle est construite à partir de cinq macro-activités. Un logiciel a été développé à partir de cette approche. Il est présenté en détail.<br /><br />Dans la seconde partie de la thèse, des problèmes de recherche opérationnelle liés aux chaînes d'approvisionnement vues au niveau stratégique sont exposés. Il s'agit en particulier de problèmes relatifs à la sélection des partenaires d'une chaîne d'approvisionnement.<br /><br />Enfin, la dernière partie de la thèse est dédiée à des problèmes sensibles au niveau tactique dans l'environnement des chaînes d'approvisionnement. Il s'agit d'ordonnancement en temps réel d'assemblage lorsque les composants sont sous-traités et de la conception d'un processus de partage des bénéfices et des pertes entre partenaires.

Cette thèse porte sur les modèles d'équilibres dynamiques sur un réseau de transport et leurs applications à l'affectation de trafic. Elle tente d'en propose une formulation à la fois générale et mathématiquement rigoureuse. Une attention particulière est accordée à la représentation de la demande de transport. Plus spécifiquement, la modélisation de l'hétérogénéité dans les préférences des usagers d'un réseau de transport, ainsi que des stratégies de choix d'horaire dans les déplacements, occupe une place importante dans notre approche. Une caractéristique de ce travail est son fort recours au formalisme mathématique; cela nous permet d'obtenir une formulation concise et micro-économiquement cohérente des réseaux de transport et de la demande de transport dans un contexte dynamique. Cette thèse traite aussi de méthodes de résolution en lien avec les modèles d'équilibres dynamiques. Nous établissons analytiquement des équilibres sur des réseaux de petites tailles afin d'améliorer la connaissance qualitative de l'interaction entre offre et demande dans ce contexte. L'intuition retirée de ces exercices nous permet de concevoir des méthodes numériques de calculs qui peuvent être appliquées à des réseaux de transport de grande taille. Tout au long de la thèse plusieurs applications économiques de ces travaux sont explorées. Toutes traitent des politiques de tarification de la congestion et de leurs évaluation, notamment lorsque les automobilistes sont susceptibles d'ajuster leurs horaires de départ. En particulier une politique tarifaire conçue pour limiter la congestion lors des grands départs de vacances est testée. Elle consiste à mettre en place un péage sur le réseau autoroutier variant selon l'heure de la journée mais aussi de jour en jour. Ce type de péage est particulièrement intéressant pour les exploitants car il leur permet d'influencer à la fois sur l'heure et le jour de départ des vacanciers. Les méthodes développées dans cette thèse permettent d'établir que les gains en termes de réduction de la congestion sont substantiels.

Les problèmes d’optimisation discrète sont pour beaucoup difficiles à résoudre, de par leur nature combinatoire. Citons par exemple les problèmes de programmation linéaire en nombres entiers. Une approche couramment employée pour les résoudre exactement est l’approche de Séparation et Évaluation Progressive. Une approche différente appelée « Resolution Search » a été proposée par Chvátal en 1997 pour résoudre exactement des problèmes d’optimisation à variables 0-1, mais elle reste mal connue et n’a été que peu appliquée depuis. Cette thèse tente de remédier à cela, avec un succès partiel. Une première contribution consiste en la généralisation de Resolution Search à tout problème d’optimisation discrète, tout en introduisant de nouveaux concepts et définitions. Ensuite, afin de confirmer l’intérêt de cette approche, nous avons essayé de l’appliquer en pratique pour résoudre efficacement des problèmes bien connus. Bien que notre recherche n’ait pas abouti sur ce point, elle nous a amené à de nouvelles méthodes pour résoudre exactement les problèmes d’affectation généralisée et de localisation simple. Après avoir présenté ces méthodes, la thèse conclut avec un bilan et des perspectives sur l’application pratique de Resolution Search. / The combinatorial nature of discrete optimization problems often makes them diffi- cult to solve. Consider for instance integer linear programming problems, which are commonly solved using a Branch-and-Bound approach. An alternative approach, Resolution Search, was proposed by Chvátal in 1997 for solving 0-1 optimization problems, but remains little known to this day and as such has seen few practical applications. This thesis attempts to remedy this state of affairs, with partial success. Its first contribution consists in the generalization of Resolution Search to any discrete optimization problem, while introducing new definitions and concepts. Next, we tried to validate this approach by attempting to solve well-known problems efficiently with it. Although our research did not succeed in this respect, it lead us to new methods for solving the generalized assignment and uncapacitated facility location problems. After presenting these methods, this thesis concludes with a summary of our attempts at practical application of Resolution Search, along with further perspectives on this matter. / Thèse réalisée en cotutelle avec l'Université d'Avignon.