Depuis quelques années, la méthode de séparation et évaluation par intervalles (Interval Branch and Bound) est de plus en plus utilisée pour résoudre les problèmes d’optimisation globale sous contraintes (Constrained Global Optimisation), notamment ceux qui sont non convexes. Contrairement à un grand nombre de ses concurrents, cette méthode permet de prouver l’optimalité d’une solution avec un niveau de précision donné. En revanche, son processus d’exploration arborescent implique une complexité exponentielle en temps et en mémoire dans le pire cas. De ce fait, le développement de techniques permettant d’accélérer la convergence de cette méthode définit un pan de recherche important.Une première contribution concerne les méthodes de contraction destinées à réduire l’espace de recherche. Nous proposons une nouvelle méthode de contraction, nommée TEC, qui généralise à plusieurs dimensions le principe de la disjonction constructive utilisée par la méthode de contraction CID. TEC construit un sous- arbre d’exploration par un processus de bissection et de contraction avant d’effectuer l’union des espaces de recherche associés aux feuilles de ce sous-arbre. Nous proposons deux variantes de TEC exploitant sa structure arborescente. La première, nommée Graham-TEC, permet d’apprendre des contraintes linéaires implicites utilisées pour améliorer la contraction. La seconde, nommée TEC-UB, permet d’apporter une amélioration à la recherche de solutions en faisant appel à une heuristique de recherche de solutions sur les feuilles du sous-arbre.Une deuxième contribution concerne les stratégies de parcours de l’arbre d’exploration. Nous étudions une stratégie récente qui fait un compromis entre un parcours en meilleur d’abord et un parcours en profondeur d’abord. Nous proposons des variantes de cet algorithme qui privilégient l’exploration des régions faisables.Les algorithmes proposés, testés sur un banc d’essai reconnu par la communauté, obtiennent des temps comparables à l’état de l’art. / In recent years, the Interval Branch and Bound method has been used more and more to solve constraint global optimization problems, especially those which are non-convex. Unlike many of its competitors, this method makes it possible to prove the optimality of a solution with a given level of accuracy. On the other hand, its tree exploration process implies an exponential complexity in time and memory in the worst case. That is why, the development of acceleration techniques defines an important piece of research.A first contribution concerns the interval filtering operators designed to reduce the search space. We propose a new interval filtering operator, named TEC, that generalizes to several dimensions the constructive disjunction principle used by the existing CID operator. TEC constructs a bounded subtree using a branch and contract process and returns the parallel-to-axes hull of the leaf domains/boxes. We propose two variants of TEC exploiting its tree structure. The first variant, named Graham-TEC, learns implicit linear constraints, used for improving the contraction. The second one, named TEC-UB, searches for a good feasible point inside a leaf box of the TEC subtree.A second contribution concerns the node selection strategies. We have studied a recent strategy that makes a compromise between a best-first search and a depth-first search and have proposed variants of this algorithm that favor the exploration of feasible regions.

Les enjeux du développement durable, le réchauffement climatique, la pollution dans les grandes villes, la congestion et les nuisances sonores, l'augmentation des prix de carburants, sont parmi des nombreux facteurs qui incitent les pays développés à l'innovation dans les transports publics. Dans ce contexte, l'introduction des systèmes de vélos en libre-service, au cours de ces dernières années, est une des solutions adoptées par de nombreuses grandes villes. Malgré leur succès fulgurant dans le monde entier, il existe peu d'études fondamentales sur ce type transport urbain. Pourtant, leur exploitation et leur management par des opérateurs soulèvent de nombreuses questions notamment d'ordre opérationnel. Dans ce contexte, cette thèse s'adresse aux problèmes d'ordonnancement et de rééquilibrage des stations de vélos en libre-service. Ce sont des problèmes cruciaux pour la qualité de service et la viabilité économique de tels systèmes. Le rééquilibrage consiste à redistribuer le nombre de vélos entre les différentes stations afin de satisfaire au mieux les demandes des usagers. Cette régulation se fait souvent par le biais de véhicules spécifiques qui font des tournées autour des différentes stations. Ainsi, deux problèmes d'optimisation difficiles se posent : la recherche de la meilleure tournée du véhicule de régulation (ordonnancement de la tournée) et la détermination des nombres de véhicules à utiliser (rééquilibrage des stations). Dans cette optique, les travaux de cette thèse constituent une contribution à la modélisation et à l'optimisation de performances des systèmes de vélos en libre-service en vue de leur rééquilibrage et leur ordonnancement. Plusieurs méthodes d'optimisation et ont été développées et testées. De telles méthodes incorporent différentes approches de simulation ou d'optimisation comme les réseaux de Petri, les algorithmes génétiques, les algorithmes gloutons, les algorithmes de recherche par voisinage, la méthode arborescente de branch-and-bound, l'élaboration des bornes supérieures et inférieures, etc. Différentes facettes du problème ont été étudiées : le cas statique, le cas dynamique, l'ordonnancement et le rééquilibrage avec un seul (ou multiple) véhicule(s). Afin de montrer la pertinence de nos approches, la thèse comporte également plusieurs applications réelles et expérimentations / In our days, developed countries have to face many public transport problems, including traffic congestion, air pollution, global oil prices and global warming. In this context, Public Bike sharing systems are one of the solutions that have been recently implemented in many big cities around the world. Despite their apparent success, the exploitation and management of such transportation systems imply crucial operational challenges that confronting the operators while few scientific works are available to support such complex dynamical systems. In this context, this thesis addresses the scheduling and balancing in public bicycle-sharing systems. These problems are the most crucial questions for their operational efficiency and economic viability. Bike sharing systems are balanced by distributing bicycles from one station to another. This procedure is generally ensured by using specific redistribution vehicles. Therefore, two hard optimization problems can be considered: finding a best tour for the redistribution vehicles (scheduling) and the determination of the numbers of bicycles to be assigned and of the vehicles to be used (balancing of the stations). In this context, this thesis constitutes a contribution to modelling and optimizing the bicycle sharing systems' performances in order to ensure a coherent scheduling and balancing strategies. Several optimization methods have been proposed and tested. Such methods incorporate different approaches of simulation or optimization like the Petri nets, the genetic algorithms, the greedy search algorithms, the local search algorithms, the arborescent branch-and-bound algorithms, the elaboration of upper and lower bounds, ... Different variants of the problem have been studied: the static mode, the dynamic mode, the scheduling and the balancing by using a single or multiple vehicle(s). In order to demonstrate the coherence and the suitability of our approaches, the thesis contains several real applications and experimentations