L’interconnexion croissante dans les systèmes de transports a conduit à la modélisation de nouvelles contraintes, dites contraintes de synchronisation, dans les problèmes de tournées de véhicules. Dans cette thèse, nous nous intéressons à deux cas dans lesquels ce type de problématiques apparaît. Dans un premier temps, nous proposons une méthode heuristique pour un problème à deux échelons rencontré pour la distribution de marchandises en ville. Dans un second temps, nous étudions l’intégration d’un cross-dock dans des tournées de collectes et livraisons. Une première contribution à ce sujet concerne le problème de tournées de véhicules avec cross-docking, et une seconde contribution intègre, en plus, des contraintes de ressources au cross-dock dans le problème de routage. Une méthode pour un problème de chargement 3D, étudié lors d’un stage doctoral en entreprise, est également présentée. / Transportation systems are more and more interconnected, this has lead to a new kind of constraints, called synchronization constraints, in vehicle routing problems. In this thesis, we study two cases in which this type of constraints arises. First, we propose a heuristic method for a two-echelon problem arising in City Logistics. Second, we study the integration of a cross-dockin pickup and delivery vehicle routing problems. To that end we propose a matheuristic for the vehicule routing problem with cross-docking, and we propose an extension of this problem that integrates specific resource synchonization constraints arising at the cross-dock. A method for a 3D loading problem is also presented.

Nous constatons l'importante appropriation du concept de concertation par le discours politique, économique et social général ces dernières années, en France et dans d'autres pays. L'utilisation du terme "concertation" s'accompagne généralement d'un constat implicite d'un décalage croissant, dans les décisions publiques ou privées, entre ceux qui sont concernés par ces décisions d'une part et ceux qui en conduisent les processus d'autre part. Ce décalage est très contrasté pour les décisions publiques en particulier. Il prend la forme d'une profonde remise en cause des circuits traditionnels de la décision publique et du débat public. De nombreux auteurs montrent que de plus en plus les décisions qui émanent des institutions de représentation sont contestées, et parfois même violemment, par ceux sur qui ces décisions s'appliquent. Dans ces conditions, la concertation, présentée comme une démarche originale d'implication dans le processus de décision des différentes parties prenantes, est perçue comme une modalité alternative positive de la prise de décision publique. <br />De ce fait, les législateurs ont tenté, depuis plusieurs décennies en France, de préciser un contenu et des modalités de mise en œuvre d'une démarche de concertation. Néanmoins, de nombreux auteurs concluent de toute façon à un décalage persistant et croissant entre ce que préconisent les textes de loi et ce qu'est la pratique de la décision publique en matière d'environnement ou de questions liées aux transports. Les réflexions de ces auteurs les conduisent à relever également une évidente inadéquation à des démarches participatives, des outils actuellement mobilisés dans les processus de décision. Dans des contextes participatifs, il faut donc d'une part imaginer d'autres outils capables de supporter différents points de vue et différentes rationalités et d'autre part parvenir à en évaluer l'intérêt dans ce type de contexte. Notre thèse s'inscrit dans cette perspective.<br />L'objet de la thèse est en effet, d'identifier, dans le cadre des décisions publiques, la nature et la forme des outils d'aide à la décision qui peuvent instrumenter et rendre possible des démarches de concertation. De fait, le travail conduit à préciser ainsi la nature des liens et de la contribution des outils d'aide à la décision aux démarches de concertation.<br />Pour cela, nous construisons une grille de lecture des démarches de concertation fondée sur les concepts d'intégration et d'identification qui nous permet, dans une perspective d'abduction d'inférer des facteurs contextuels dont dépend la pertinence d'outils d'aide à la décision par rapport à une démarche de concertation.

La modélisation vibroacoustique d'un TGV peut être simplifiée par l'analyse des relations entre les paramètres mécaniques d'une structure, les paramètres acoustiques des signaux rayonnés et la perception du voyageur. Cette analyse indique quels éléments structuraux sont responsables du bruit perçu. L'étude de ces relations est menée en parallèle sur une voiture de TGV et sur un système constitué d'une plaque vibrante fermant une cavité. L'intérêt de cette structure plus simple est de tester et valider des méthodes d'analyses vibratoires, acoustiques et perceptives. L'étude se décompose donc en deux parties pour chacune des deux structures : la modélisation vibroacoustique et les tests perceptifs. Le comportement vibroacoustique du système plaque/cavité est décrit par une méthode modale analytique. Les expériences menées à l'intérieur d'un modèle expérimental et des comparaisons avec un logiciel de calcul par éléments finis ont validé cette méthode. Les tests perceptifs sur des signaux de synthèse et enregistrés mettent en évidence entre autres l'influence sur la perception du type de plaque et de l'amortissement des parois. Le comportement vibroacoustique du TGV est décrit par une analyse modale expérimentale sans connaissance a priori de la source excitatrice (méthodes LSCE, AR et SSI). Ces méthodes permettent aussi de resynthétiser des signaux à partir des paramètres modaux identifiés. Les tests perceptifs à partir de signaux enregistrés permettent de différencier la perception des architectures de voitures de trains, de la position à l'intérieur d'une voiture et de la vitesse du train.

Si certains conservent un objectif scientifique et expérimental, la plupart des projets spatiaux visent maintenant à développer des systèmes profitables soumis à de fortes contraintes opérationnelles. Dimensionner ces systèmes, "ni trop, ni trop peu", est donc un objectif majeur qui conditionne leur viabilité économique. Si trop de risques sont pris les investisseurs se feront rares, et si le système est surdimensionné son coût peut être également rapidement dissuasif. Dans ce contexte, l'étude de la Disponibilité Opérationnelle en phases d'avant-projet donne certains critères précieux pour évaluer le compromis coût / prise de risque et permet ainsi de guider très tôt certains choix de conception. Cependant la complexité et la taille croissante de ces systèmes ont rapidement mis en évidence certaines limites des méthodes classiques d'évaluation de cette grandeur. La théorie des réseaux de Petri, riche d'une trentaine d'années de recherche et principalement appliquée à l'analyse, l'évaluation et la commande des systèmes distribués, offre des perspectives intéressantes pour dépasser ces limites. La principale contribution de ce travail mené au sein de l'Agence française de l'Espace et d'un industriel du spatial a été de favoriser son utilisation pour l'étude de la Disponibilité Opérationnelle de système spatiaux complexes et dans le cadre très concret des phases d'avant-projets. On a tout d'abord justifié l'intérêt que les réseaux de Petri présentent tant pour la modélisation que pour l'évaluation de tels systèmes par comparaison aux approches classiques. Puis on a illustré leur utilisation sur des programmes bien réels et dans le cadre d'un travail intégré avec les équipes projets. Enfin, on a proposé les bases d'une démarche de modélisation orientée application dont le but est d'aider des non spécialistes à concevoir aisément des modèles de systèmes complexes. Ce sont ces trois grandes étapes qui sont ici présentées.

Esterel est un langage impératif concurrent pour la programmation des systèmes réactifs. A l'exception de l'instruction "pause", les primitives du langage s'exécutent sans consommer de temps logique. L'exécution se décompose donc en une suite d'instants. Dans ce contexte, les boucles peuvent poser deux types de problèmes: d'une part une boucle instantanée peut bloquer l'écoulement du temps; d'autre part un bloc de code peut être traversé plusieurs fois au cours du même instant, conduisant à un comportement du programme dit "schizophrène". Les boucles instantanées sont proscrites par la sémantique. Elles doivent donc être détectées par les compilateurs et les programmes correspondants doivent être rejetés. Par ailleurs, la compilation efficace des programmes schizophrènes est difficile. Ainsi, alors que plusieurs compilateurs pour Esterel sont disponibles, les algorithmes employés pour compiler les boucles ne sont ni portables, ni formellement spécifiés, et encore moins prouvés. Dans ce document, nous étudions les boucles en Esterel, établissant une correspondance formelle entre la sémantique opérationnelle du langage et l'implémentation concrète d'un compilateur. Après avoir spécifié les problèmes posés par les boucles, nous développons des techniques d'analyse statique efficaces pour les détecter dans un code Esterel quelconque. Puis, de façon à guérir la schizophrénie, c'est à dire transformer efficacement les programmes schizophrènes en programmes non schizophrènes, nous introduisons dans le langage une nouvelle primitive appelée "gotopause". Elle permet de transférer le contrôle d'un point du programme à un autre de façon non instantanée, mais sans contrainte de localité. Elle préserve le modèle de concurrence synchrone d'Esterel. Nous décrivons un premier algorithme qui, en dépliant les boucles à l'aide de cette nouvelle instruction, produit pour tout programme Esterel correct un programme non schizophrène équivalent. Enfin, en combinant analyse statique et réécriture, nous obtenons un préprocesseur qui rejette les boucles instantanées et guérit la schizophrénie, à la fois portable et très efficace. Nous l'avons implémenté. De plus, grâce à une approche formelle de bout en bout, nous avons pu prouver la correction de ce préprocesseur.

Cette thèse d'Habilitation à Diriger des Recherches revient sur une dizaine d'années de contributions théoriques et pratiques à l'optimisation combinatoire, contributions dont le domaine d'application privilégié est l'optimisation des systèmes de télécommunications (principalement les autocommutateurs pour la téléphonie cellulaire) et informatiques (en particulier les architectures de processeur parallèles, dites multi-cœurs). Ces travaux se caractérisent également par la résolution bout-en-bout de nombreux cas d'applications industriels concrets et difficiles, de la modélisation mathématique initiale jusqu'à la mise en œuvre d'algorithmes de résolution opérationnels en passant par les développements théoriques nécessaires à leurs fondements.

Cette synthèse de travaux de recherche concerne l'algorithmique dans les graphes et l'utilisation de la pro- grammation linéaire et semidéfinie positive (SDP) dans le cadre de la résolution exacte ou approchée de plusieurs problèmes fondamentaux de l'Optimisation Combinatoire. L'approche semidéfinie, qui conduit à des relaxations convexes mais non-linéaires, a permis d'obtenir de remarquables résultats théoriques en approximation et devient à présent utilisable en pratique (tout comme la programmation linéaire qui en est un cas particulier). Nos travaux comportent une forte composante algorithmique et des études de complexité de plusieurs problèmes d'optimisation dans les graphes. Nous considérons tout d'abord le problème de la recherche d'un sous-graphe dense de taille fixée pour lequel nous présentons un algorithme polynomial avec ga- ranties de performances fondé sur la programmation linéaire et quadratique. Puis, nous étudions les problèmes de multiflots entiers et de multicoupes pour lesquels nous avons identifié de nombreux cas po- lynomiaux dans des graphes particuliers importants en pratique : arborescences, grilles, anneaux. D'une part, les solutions fractionnaires fournies par certaines relaxations linéaires de ces problèmes sont le point de départ d'algorithmes de résolution efficaces. D'autre part, les propriétés des programmes linéaires uti- lisés nous permettent également d'élaborer des algorithmes purement combinatoires et de démontrer leur validité (matrices totalement unimodulaires, théorème des écarts complémentaires). Nous proposons également des approches systématiques pour élaborer des relaxations semidéfinies pour les programmes quadratiques, modèles de très nombreux problèmes combinatoires et continus. Plus précisément, nous étudions les liens entre relaxations semidéfinies et des relaxations lagrangiennes partielles de programmes quadratiques contenant des contraintes linéaires. En particulier, les fonctions quadratiques constantes sur une variété affine sont entièrement caractérisées. Ceci permet de facilement comparer les différentes familles de contraintes redondantes proposées dans la littérature dans l'approche semidéfinie dans le cadre unifié de l'approche lagrangienne. Puis, nous présentons un algorithme pour élaborer des relaxations semidéfinies à partir de relaxations linéaires existantes. L'objectif est de pro- fiter des résultats théoriques et expérimentaux obtenus dans l'approche linéaire. Nous avons développé un logiciel (SDP_S) grâce à ces résultats. Il permet de formuler automatiquement et facilement des relaxations semidéfinies pour tout problème pouvant être formulé comme un programme quadratique en variables bivalentes. Notre méthode peut se généraliser à certains programmes à variables mixtes. Enfin, nous appliquons les méthodes décrites précédemment à une série de problèmes combinatoires classiques. Nos expérimentations montrent que l'approche semidéfinie est à présent pertinente dans la pra- tique sous certaines conditions. Premièrement, nous présentons des méthodes de séparation/évaluation efficaces fondées sur la SDP pour la résolution exacte des problèmes max 2sat et Vertex-Cover. Deuxièmement, nous proposons plusieurs bornes par SDP de grande qualité pour des problèmes particu- lièrement difficiles à résoudre par les approches linéaires : k-cluster, CMAP (un problème de placement de tâches avec contraintes de ressources), et le problème de l'affectation quadratique (QAP). Pour ce dernier nous présentons également un algorithme de coupes performant fondé sur la programmation semidéfinie. Afin d'obtenir des algorithmes efficaces en pratique, nous mettons en oeuvre non seulement nos méthodes d'élaboration de relaxations SDP, mais également des techniques algorithmiques issues de l'approximation polynomiale, ainsi que des outils spécifiques de résolution numérique des programmes semidéfinis.

En raison de problèmes opérationnels et d'autres événements inattendus, un grand nombre d'incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d'entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d'incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d'Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d'envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d'analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d'algorithmes itératifs avec l'objectif d'améliorer progressivement la solution quand le temps d'exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d'un incident font qu'il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d'évaluer la probabilité qu'un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l'optimum pour les instances de petite taille et moyenne alors qu'une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d'autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge

De nombreux problèmes d'optimisation issus du monde réel, notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés. En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte. Les métaheuristiques sont des candidates naturelles pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques. Toutefois, le développement de métaheuristiques efficaces découle d'un processus de recherche complexe. Le cœur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif, ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO. Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées. Enfin, la question de la prise en compte l'incertitude est abordée dans le contexte de l'optimisation multiobjectif.

La question de l'accès au soin est cruciale dans notre société moderne. Un effet évident de la demande accrue de services de santé est l'augmentation du taux d'occupation dans les hôpitaux. La principale différence entre la dispensation de soins à l'hôpital et au domicile est la suivante: le patient doit se déplacer et toutes les ressources nécessaires à son traitement se trouvent dans le même endroit, tandis que dans les soins délivrés au domicile, les ressources doivent être déplacées au chevet du patient. Il existe plusieurs défis afin de pouvoir réaliser ce changement. Dans cette thèse nous traitons trois problèmes importants dans la conception des structures de soins à domicile. D'abord, la localisation des structures en minimisant les coûts logistiques, où nous développons trois modèles incluant différentes caractéristiques comme du système de santé comme les coûts liés aux déplacements des ressources, la variation de la demande dans le temps et l'existence et évolution des ressource libérales. Ces modèles nous permettent de proposer des localisations robustes dans le temps tout en assurant une couverture maximale et en minimisant les coûts. La deuxième problématique consiste au choix des activités et couverture épidémiologique et spatiale en tenant compte différentes activités et types de ressources, les autorisations pour réaliser les pathologies et la couverture. Deux modèles développés nous ont permis montrer les effets sur l'affectation de la demande et le dimensionnement de ressources induits par changements dans les coûts des libéraux, salaires et d'autorisation de servir la demande. Le troisième problème et celui du dimensionnement de ressources avec incertitudes de demande (volume, épidémiologique et géographique) et le modèle proposé tient compte du problème sous-jacent de déplacement des ressources à l'aide d'une estimation de la tournée réalisée.