Les entreprises de transport et de distribution sont confrontées à des difficultés d’exploitation liées à la taille et à la complexité de leur processus de livraison. Dans cette problématique, nous proposons une approche globale du Problème Général de Livraison (PGL).Au niveau méthodologique, c’est une approche hiérarchique (stratégique, tactique, opérationnelle) et structurée. Il s’agit de concevoir et d’exploiter un PGL en le décomposant en problèmes de livraisons élémentaires identifiés et le plus possible indépendants les uns des autres (problèmes de transport, de hubs, d’agences, de tournées...).Au niveau algorithmique, des modèles et algorithmes de résolution ont été proposés pour résoudre ces problèmes élémentaires de livraison dans la phase opérationnelle en tenant compte, en particulier, du nombre et de la capacité limités des moyens de transport.Au niveau applicatif, deux exemples réels sont traités : le système de livraison d’une entreprise de Vente à Distance et le système de livraison des casernes de pompiers du Nord de la France à partir de la pharmacie centrale de Lille / Transport and delivery companies are confronted by difficulties in their transportation process due to the scale and the complexity of their distribution process. In this context, we propose a comprehensive approach to General Delivery Problem (GDP). In terms of methodology, it is a hierarchical (strategic, tactical and operational) and structured approach. It consists of designing and decomposing the GDP into well identified basic delivery problems as independent as possible. These basic transport problems involve the problems about transportation, intermediate facility, agencies, routings, etc. At the algorithm level, models and solution algorithms have been proposed to solve these basic delivery problems in the operational phase, taking account in particular transportation restriction about the number and capacity of vehicles.At the application level, two real examples are discussed: one is the delivery system of a delivery company; the other one is the delivery system of the Regional Fire and Emergency Center in the north of France

Le raisonnement spatial et temporel qualitatif est un domaine principal d’études de l’intelligence artificielle et, en particulier, du domaine de la représentation des connaissances, qui traite des concepts cognitifs fondamentaux de l’espace et du temps de manière abstraite. Dans notre thèse, nous nous focalisons sur les formalismes du domaine du raisonnement spatial et temporel qualitatif représentant les informations par des contraintes et apportons des contributions sur plusieurs aspects. En particulier, étant donnée des bases de connaissances d’informations qualitatives sur l’espace ou le temps, nous définissons des nouvelles conditions de consistance locale et des techniques associées afin de résoudre efficacement les problèmes fondamentaux se posant. Nous traitons notamment du problème de la satisfiabilité qui est le problème de décider s’il existe une interprétation quantitative de toutes les entités satisfaisant l’ensemble des contraintes qualitatives. Nous considérons également le problème de l’étiquetage minimal qui consiste à déterminer pour toutes les contraintes qualitatives les relations de base participant à au moins une solution ainsi que le problème de redondance consistant à déterminer les contraintes qualitatives non redondantes. En outre, nous enrichissons le domaine des formalismes spatio-temporels par des contributions concernant une logique spatio-temporelle combinant la logique temporelle propositionnelle (PTL) avec un langage de contraintes qualitatives spatiales et une étude de la problématique consistant à gérer une séquence temporelle de configurations spatiales qualitatives devant satisfaire des contraintes de transition. / Qualitative Spatial and Temporal Reasoning is a major field of study in Artificial Intelligence and, particularly, in Knowledge Representation, which deals with the fundamental cognitive concepts of space and time in an abstract manner. In our thesis, we focus on qualitative constraint-based spatial and temporal formalisms and make contributions to several aspects. In particular, given a knowledge base of qualitative spatial or temporal information, we define novel local consistency conditions and related techniques to efficiently solve the fundamental reasoning problems that are associated with such knowledge bases. These reasoning problems consist of the satisfiability problem, which is the problem of deciding whether there exists a quantitative interpretation of all the entities of a knowledge base such that all of its qualitative relations are satisfied by that interpretation, the minimal labeling problem, which is the problem of determining all the atoms for each of the qualitative relations of a knowledge base that participate in at least one of its solutions, and the redundancy problem, which is the problem of obtaining all the non-redundant qualitative relations of a knowledge base. Further, we enrich the field of spatio-temporal formalisms that combine space and time in an interrelated manner by making contributions with respect to a qualitative spatio-temporal logic that results by combining the propositional temporal logic (PTL) with a qualitative spatial constraint language, and by investigating the task of ordering a temporal sequence of qualitative spatial configurations to meet certain transition constraints.

Cette thèse s'intéresse à la conception et à l'analyse de méthodes de discrétisation hybrides pour les inégalités variationnelles non linéaires apparaissant en mécanique des fluides et des solides. Les principaux avantages de ces méthodes sont la conservation locale au niveau des mailles, la robustesse par rapport à différents régimes de paramètres et la possibilité d’utiliser des maillages polygonaux / polyédriques avec des nœuds non coïncidants, ce qui est très intéressant dans le contexte de l’adaptation de maillage. Les méthodes de discrétisation hybrides sont basées sur des inconnues discrètes attachées aux faces du maillage. Des inconnues discrètes attachées aux mailles sont également utilisées, mais elles peuvent être éliminées localement par condensation statique. Deux applications principales des discrétisations hybrides sont abordées dans cette thèse. La première est le traitement par la méthode de Nitsche du problème de contact de Signorini (dans le cas scalaire) avec une non-linéarité dans les conditions aux limites. Nous prouvons des estimations d'erreur optimales conduisant à des taux de convergence d'erreur d'énergie d'ordre (k + 1), si des polynômes de face de degré k >= 0 sont utilisés. La deuxième application principale concerne les fluides à seuil viscoplastiques. Nous concevons une méthode de Lagrangien augmenté discrète appliquée à la discrétisation hybride. Nous exploitons la capacité des méthodes hybrides d’utiliser des maillages polygonaux avec des nœuds non coïncidants afin d'effectuer l’adaptation de maillage local et mieux capturer la surface limite. La précision et la performance des schémas sont évaluées sur des cas tests bidimensionnels, y compris par des comparaisons avec la littérature / This thesis is concerned with the devising and the analysis of hybrid discretization methods for nonlinear variational inequalities arising in computational mechanics. Salient advantages of such methods are local conservation at the cell level, robustness in different regimes and the possibility to use polygonal/polyhedral meshes with hanging nodes, which is very attractive in the context of mesh adaptation. Hybrid discretizations methods are based on discrete unknowns attached to the mesh faces. Discrete unknowns attached to the mesh cells are also used, but they can be eliminated locally by static condensation. Two main applications of hybrid discretizations methods are addressed in this thesis. The first one is the treatment using Nitsche's method of Signorini's contact problem (in the scalar-valued case) with a nonlinearity in the boundary conditions. We prove optimal error estimates leading to energy-error convergence rates of order (k+1) if face polynomials of degree k >= 0 are used. The second main application is on viscoplastic yield flows. We devise a discrete augmented Lagrangian method applied to the present hybrid discretization. We exploit the capability of hybrid methods to use polygonal meshes with hanging nodes to perform local mesh adaptation and better capture the yield surface. The accuracy and performance of the present schemes is assessed on bi-dimensional test cases including comparisons with the literature

Cette thèse s’intéresse à trouver des solutions informatiques à certains problèmes de l’optimisation combinatoire, à savoir les problèmes de tournées de véhicules. Elle aborde les problèmes de Transport A la Demande (TAD). L’objectif principal visé dans cette thèse fait appel à certaines approches exactes et certaines approches méta-heuristiques pour résoudre des problèmes d’optimisation multi-objective de Transport A la Demande avec plusieurs véhicules. En effet, nos principaux objectifs de recherche consistent à : -I) Résoudre un problème multi-objectif de Transport A La Demande multi-véhicules basé sur la qualité de service ; - II) Résoudre un autre problème de Transport A la Demande multi-objectifs multi-véhicules. Ce problème traite un cas spécifique et qui consiste à l’application de ce problème aux domaines de l’Hospitalisation A Domicile (HAD). Nous avons appliqué des algorithmes exacts de "Branch and Bound" et des méthodes méta-heuristiques telles que l’algorithme évolutionnaire "Algorithme Génétique" et l’algorithme de "Colonie de Fourmis" pour apporter des solutions efficaces à ces différents problèmes. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes pour montrer leurs capacités de produire des solutions de haute qualité en temps de calcul raisonnables. / This thesis focuses on finding computer science solutions for some combinatorial optimization problems, namely Vehicle Routing Problems (VRP). The thesis addresses the Dial A Ride Problems (DARP). Its main objective is to use some exact and meta-heuristics approaches to solve multi-objective optimization of Dial A Ride Problem with multi-vehicles. Hence, our main research aims are : - I)Solve a multi-objective Dial A Ride Problem with multi-vehicles based on quality of service, this problem treats a general case ; - II) Solve another multi-objective Dial A Ride Problem with multi-vehicles, this problem deals with a specific case which is an application of the Dial A Ride Problem in Home Health Care (HHC). We have also applied exact algorithms "Branch and Bound" and meta-heuristic algorithms such as evolutionary algorithms "Genetic Algorithm" and "Ant Colony" algorithm to provide effective solutions to these different problems. A set of numerical results are presented for each of these methods. Our results show that they produce high quality solutions in a reasonable execution time for all the treated problems.

Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

Ce travail porte sur les aspects numériques de la résolution de problèmes inverses non linéaires gouvernés par des équations aux dérivées partielles, à l'aide des techniques du contrôle optimal. Nous nous sommes limités dans cette thèse à l'étude de deux problèmes: identification du coefficient de diffusion de la chaleur, identification de sources non linéaires dans des e.d.p. elliptiques. Ces deux problèmes sont résolus numériquement à l'aide d'une approche lagrangienne, les fonctions sont identifiées par leurs coefficients dans une base de B-splines cubiques. Ces problèmes étant mal posés, on étudie des techniques de choix du paramètre de régularisation de Tikhonov, comme les méthodes de validation croisée. On résout ensuite ces deux problèmes dans une base d'ondelettes, ce qui nous permet, par le biais d'un changement de base approprié, de réduire le caractère mal posé de ces problèmes, et de mener à bien l'identification sans terme de régularisation. Dans les problèmes réels, la solution exacte étant généralement inconnue, lorsqu'on dispose d'un estimateur, il n'est a priori pas possible de savoir s'il s'agit d'un «bon» estimateur. On peut remédier à ce problème à l'aide des courbures de la surface des réponses, qui nous permettent de quantifier le degré de non linéarité de la surface au voisinage de l'estimateur obtenu et de justifier l'usage des méthodes séquentielles quadratiques utilisées pour l'identification

L'objet de cette thèse est l'étude de quelques aspects de <br />la notion d'hyperbolicité, plus particulièrement de la <br />relation qui existe entre celle-ci et la nature bien posée <br />d'un problème de Cauchy obtenu à partir d'un système<br />d'équations aux dérivées partielles issu de la mécanique <br />des fluides ou la réalisation de la simulation numérique <br />d'un tel problème.<br /><br />Dans un premier temps, nous rappelons en quoi la notion de<br />linéarisation d'un système d'équations aux dérivées <br />partielles semble naturelle à l'étude de ce système et <br />comment, de l'étude de ces problèmes linéarisés, plus <br />précisément de leur nature bien posée c'est-à-dire de leur <br />stabilité, découle la notion d'hyperbolicité.<br /><br />Nous étudions ensuite le cas particulier d'un modèle à <br />quatre équations pour un écoulement bifluide comportant des <br />termes de diffusion pour les équations de quantité de <br />mouvement. Nous montrons alors que, bien que, pour ce <br />système, l'ajout des termes de diffusion n'entraîne pas <br />l'hyperbolicité du modèle obtenu, les problèmes de Cauchy <br />construits à partir de la linéarisation de ce système, <br />autour d'un état constant, sont désormais bien posés.<br /><br />Enfin, nous considérons le cas d'un modèle à cinq équations <br />pour un écoulement bifluide. Ce modèle ne nécessite pas de <br />loi de fermeture algébrique (équations d'état ou lois <br />tabulées) mais comporte une équation aux dérivées <br />partielles portant sur la pression. Le système ainsi <br />obtenu n'est pas hyperbolique mais les valeurs propres de <br />l'opérateur d'advection sont toutes réelles. La simulation<br />numérique d'un écoulement régi par ce modèle, pour le cas <br />test du robinet de Ransom, ne fait néanmoins pas apparaître <br />les instabilités numériques que la nature mal posée du<br />linéarisé nous faisait craindre et qui sont présentes dans <br />les simulations réalisées à partir du modèle isentropique <br />classique à quatre équations.

La première moitié de ce mémoire est consacrée à la théorie KAM et au théorème d'Arnold sur la stabilité des systèmes planétaires. Ce travail a fait l'objet d'un article en préparation et d'une publication~:\footnote{ \url{http://people.math.jussieu.fr/~fejoz/articles.html}} -- ''Twisted conjugacies and invariant tori theorems''~\cite{Fejoz:2010a}. Je redémontre une forme normale de champs de vecteurs due à Moser~\cite{Moser:1967}, pour les perturbations de champs de vecteurs admettant un tore invariant quasi-périodique diophantien. Cette forme normale, que j'appelle une \emph{conjugaison tordue} est une porte d'entrée pour démontrer des théorèmes de tores invariants dus à Kolmogorov, Arnold, Rüssmann et Herman, ainsi que d'autres théorèmes, par exemple pour des champs de vecteurs dissipatifs. J'introduis une notion de \emph{conjugaison hypothétique}, comme un intermédiaire commun aux théorèmes de tores invariants avec une condition de non-dégénérescence faible, améliore certaines estimations sur la dépendance fonctionnelle de la forme normale, et donne quelques applications nouvelles à la mécanique céleste. -- ''Démonstration du théorème d'Arnold sur la stabilité du système planétaire (d'après Herman)''~\cite{Fejoz:2004}. Cet article donne une démonstration du théorème d'Arnold pour $N$ planètes dans l'espace $\R^3$. La démonstration de~\cite{Fejoz:2010a} est une clarification et une amélioration de la partie abstraite de ~\cite{Fejoz:2004}. Arnold avait publié le résultat remarquable suivant~: dans le problème planétaire newtonien à $N$ planètes, si les masses des planètes sont assez petites, il existe dans l'espace des phases un sous-ensemble invariant de mesure de Lebesgue strictement positive, formé de tores invariants quasipériodiques de dimension $3N-1$~\cite{Arnold:1963}. La suggestion d'Arnold pour le démontrer en toute généralité était de fixer la direction du moment cinétique, pour se débarrasser de la dégénérescence due à l'invariance par rotation, puis d'appliquer sa version dégénérée du théorème de Kolmogorov pour trouver des tores lagrangiens invariants au voisinage de la singularité séculaire elliptique (mouvements képlériens elliptiques circulaires horizontaux). Cette stratégie de réduction partielle ne marche pas à cause d'une résonance mystérieuse, découverte par Herman, qui généralise à $N$ planètes une résonance déjà connue de Clairaut dans le problème de la lune. Cette résonance n'avait pas été remarquée dans le cas de $2$ planètes, où la réduction des noeuds de Jacobi permet de réduire complètement le problème par la symétrie de rotation, en coordonnées de Delaunay (je rappelle en appendice la définition de ces coordonnées, et propose une nouvelle démonstration de leur caractère symplectique). Ici, je démontre par récurrence sur le nombre de planètes, en suivant les idées d'Herman, que l'image locale de l'application fréquence (vue comme fonction des demi grands axes des planètes) est contenue dans un plan vectoriel de codimension deux, mais dans aucun plan vectoriel de codimension supérieure. Un argument de la théorie des intersections lagrangiennes permet alors d'appliquer un théorème de tores invariants qui ne requiert qu'une faible condition de non-dégénérescence. La seconde moitié de ce mémoire traite d'orbites périodiques et relativement périodiques (i.e. périodiques en repère tournant), dans le problème global des $N$ corps. Elle aussi est basée sur deux articles. -- ''The flow of the equal-mass spatial 3-body problem in the neighborhood of the equilateral relative equilibrium'' (avec A. Chenciner)~\cite{Chenciner:2008}. Nous démontrons qu'exactement deux familles de solutions relativement périodiques bifurquent de la solution d'équilibre relatif de Lagrange~: la famille homographique et la famille $\mathcal{P}_{12}$. De plus, en restriction à la variété centrale de dimension $4$ de l'équilibre relatif de Lagrange, la dynamique locale est une application twist d'un anneau de section, bordé par les deux familles. Un autre article montre que la famille $\mathcal{P}_{12}$ se termine, de l'autre côté, à la solution en Huit de Chenciner-Montgomery~\cite{Chenciner:2005a}. Entre ces deux extrémités, on sait que la famille $\mathcal{P}_{12}$ existe comme famille des minima de l'action lagrangienne parmi les lacets possédant sa classe de symétrie. Une telle famille pourrait a priori être non unique, ou discontinue, mais les expériences numériques ne laissent guère de doute (voir la figure dans la préface). -- ''Unchained polygons and the {$N$}-body problem'' (avec A. Chenciner)~\cite{Chenciner:2009}. L'équilibre relatif de Lagrange apparaît dans ce qui précède comme le centre organisateur du Huit. Nous montrons que le même phénomène se produit avec l'équilibre relatif du carré à quatre masses égales, qui apparaît comme centre organisateur de la famille du Hip-Hop. Plus généralement, beaucoup de classes de solutions récemment découvertes appartiennent aux familles de Lyapunov issues d'équilibres relatifs symétriques. Dans un repère tournant où elles deviennent périodiques, ces familles acquièrent des symétries remarquables. Nous étudions la possibilité de les prolonger globalement comme minima de l'action lagrangienne en un repère tournant, au sein de leur classe de symétrie. Une étape préliminaire est de déterminer les intervalles de la fréquence de rotation du repère sur lesquels un équilibre relatif est l'unique minimum absolu de l'action. Nous nous focalisons ensuite sur notre exemple principal, l'équilibre relatif du polygone régulier à $N$ sommets. L'existence locale de familles de Lyapunov verticales repose sur le fait que la restriction de la partie quadratique de l'énergie aux directions centrales est définie positive. Nous calculons les groupes de symétrie $G_{\frac rs}(N,k,\eta)$ des familles de Lyapunov verticales, et les utilisons pour prolonger les familles globalement. Les exemples paradigmatiques sont les familles de Huits pour un nombre impair de corps et les familles de Hip-Hops pour un nombre pair. Ce sont précisément les éléments de ces deux types de familles qui peuvent être des minima globaux. Dans les autres cas, des obstructions apparaissent, qui sont dues à des isomorphismes entre les groupes de symétrie de différentes famille~; c'est le cas des \emph{chaînes chorégraphiques}, dont les éléments sont seulement des minima locaux (sauf pour $N=3$). Une autre particularité intéressante de ces chaînes est le rôle décisif joué par la parité, en particulier à travers la valeur prise par le moment cinétique. Pour les familles de Lyapunov bifurquant d'un polygone à au plus $6$ sommets, nous vérifions en outre que la torsion locale est non dégénérée, ce qui justifie de prendre la rotation du repère comme paramètre. Cet article montre la fécondité des considérations de symétrie, comme technique de démonstration mais aussi comme guide heuristique dans la recherche de solutions remarquables. Le problème des $n$ corps, depuis longtemps à l'origine de nombreuses théories mathématiques, garde entier, de part la variété des techniques nécessaires à son étude, son pouvoir de fascination.

Nous considérons la simulation numérique des écoulements de fluides viscoélatiques. Développant une approximation en temps par la méthode des directions alternées, nous proposons un algorithme entièrement nouveau permettant de découpler le calcul des contraintes de celui des vitesses. D'ordre deux en temps, cette méthode permet de plus le calcul rapide des solutions stationnaires. L'éléments à divergence nulle de Thomas-Raviart est utilisé pour les vitesses, et celui de Lesaint-Raviart pour les contraintes. La méthode est appliquée au problème de l'écoulement de fluides du type Oldroyd dans une contraction brusque (problème de la marche).

Les processus ponctuels spatiaux forment une branche de la statistique spatiale utilisée dans des domaines d'application variés (foresterie, géo-marketing, sismologie, épidémiologie...) et développée par de récents travaux théoriques. Nous nous intéressons principalement dans cette thèse à l'apport de la théorie des processus ponctuels spatiaux pour des problèmes de positionnement optimal, ainsi que pour la définition de nouveaux indices de concentration basés sur les distances en économétrie. Le problème de positionnement optimal s'écrit souvent comme un problème d'optimisation prenant en compte des données geo-référencées auxquelles peuvent être associées des caractéristiques. Pour prendre en compte l'aléa, nous considérons ces données issues d'un processus ponctuel spatial pour résoudre un problème de positionnement stochastique plus réaliste qu'un modèle déterministe. A travers l'étude du positionnement optimal d'une nouvelle caserne de pompiers dans la région toulousaine, nous développons une méthode de résolution stochastique permettant de juger de la variabilité de la solution optimale et de traiter des bases de données volumineuses. L'approche implémentée est validée par des premiers résultats théoriques sur le comportement asymptotique des solutions optimales empiriques. La convergence presque sure des solutions optimales empiriques de l'étude de cas précédente est obtenue dans un cadre i.i.d. en utilisant la théorie de Vapnik-Cervonenkis. Nous obtenons aussi la convergence presque sure des solutions optimales empiriques, dans un cadre plus général, pour un problème de positionnement dérivé du problème de transport de Monge-Kantorovich. Nous nous intéressons ensuite à des indices de concentration basés sur des distances en économétrie. Ces indices de concentration peuvent s'écrire comme des estimateurs de caractéristiques du second ordre de processus ponctuels marqués. Nous définissons ensuite un estimateur non-paramétrique d'une nouvelle caractéristique d'un processus ponctuel spatial marqué définissant ainsi un nouvel indice de concentration améliorant ceux déjà existants. Dans un cadre asymptotique avec fenêtre d'observation bornée, notre estimateur est asymptotiquement sans biais.