Les problèmes d'optimisation en variables 0-1 mixtes permettent de modéliser de nombreux problèmes réels difficiles à résoudre. Cette thèse s'intéresse à la mise en oeuvre de méthodes de résolution hybrides pour obtenir des solutions de bonne qualité en des temps raisonnables pour ces problèmes. L'ensemble des algorithmes présentés dans cette thèse est testé sur le problème du sac-à-dos multidimensionnel. Il consiste à maximiser une fonction linéaire en respectant un ensemble de contraintes linéaires. Après une présentation de quelques concepts fondamentaux utilisés en recherche opérationnelle pour résoudre les problèmes d'optimisation, nous présentons dans le premier chapitre différents problèmes de la famille du sac-à-dos. Nous abordons dans le second chapitre un ensemble de méthodes efficaces existantes pour résoudre le problème du sac-à-dos multidimensionnel. Nous proposons dans le chapitre 3 une première méthode hybride qui combine la programmation dynamique et la recherche tabou au sein d'un processus dit d'intensification globale. Des concepts de réduction sont également intégrés dans la programmation dynamique de manière à essayer de réduire la taille du problème. La seconde approche décrite dans le chapitre 4 combine la recherche dispersée avec des éléments de la recherche tabou et des chemins reliants pour affiner la recherche. Une étude expérimentale est menée pour mesurer l'impact de différents composants de l'algorithme. Nous terminons dans le chapitre 5 par une méthode utilisant conjointement la relaxation en continu et la relaxation en nombres entiers mixtes pour résoudre efficacement les problèmes en variables 0-1. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes. La dernière approche permet d'améliorer quelques meilleures valeurs connues sur des instances existantes du problème du sac-à-dos multidimensionnel.

Notre travail porte sur l'étude du Problème de Routage et d'Allocation de Longueur d'Onde (Routing and Wavelength Allocation - RWA) dans des réseaux optiques WDM, indépendamment de la topologie physique sous-jacente. Le problème a été idntifié comme étant NP-difficile et plusieurs approches, tant exactes qu'approchées, existent. Nous fournissons d'abord une revue de littérature dans laquelle nous présentons quelques formulations mathématiques pour le problème ainsi que plusieurs manières d'obtenir des bornes inférieures et des heuristiques. Nous considérons le problème min-RWA dans lequel on doit satisfaire un certain nombre de requêtes avec le moins de longueurs d'onde possible. Nous présentons une méthodologie reposant sur une recherche locale de type Descente à Voisinage Variable (Variable Neighborhood Descent - VND) que l'on appelle VND-BFD. Son objectif principal est de supprimer des longueurs d'onde. Nous présentons également une méthode hybride VND-BT. Ensuite, nous proposons une nouvelle approche, elle-aussi reposant sur la VND. Elle consiste à ré-arranger les requêtes entre les longueurs d'onde disponibles. Lorsqu'elle atteint un optimum local, une procédure de perturbation est appliquée et le schéma est similaire à la Recherche Locale Itérée (Iterated Local Search - ILS). Quatre variantes sont définies selon les stratégies appliquées dans VND et ILS : VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p et VNDe-ILS5p. Les résultats expérimentaux montrent que cette nouvelle approche est plus performante, en particulier la version VNDe-ILS5p. La méthode est compétitive avec les meilleures méthodes de la littérature puisque VNDe-ILS5p a permis d'améliorer une grande partie des meilleures solutions connues sur les instances standard du min-RWA. Enfin, nous considérons aussi le problème max-RWA dans lequel on doit maximiser le nombre de requêtes traitées avec un nombre donné de longueurs d'onde. Nous proposons des modèles compacts ainsi que des améliorations destinées à accélérer la résolution par des solveurs en nombre entiers. Après avoir décrit des modèles existants utilisant la génération de colonnes, nous proposons un nouveau modèle, PG-MAX-IS-IRC, utilisant lui-aussi la génération de colonnes. Il permet d'obtenir des bornes supérieures de même qualité en un temps très fortement réduit.

La logistique est un enjeu majeur de la compétitivité des entreprises multinationales. La performance logistique est majoritairement définie lors de la structuration stratégique du réseau logistique. Appliqué au constructeur automobile PSA Peugeot Citroën, une approche d'aide à la décision est proposée pour optimiser la localisation des investissements capacitaires et la répartition des volumes de production. Ce problème de planification stratégique de réseau logistique international est décomposé en trois sous-problèmes de complexité croissante donnant chacun lieu à une revue de littérature et à des propositions de méthodes d'optimisation heuristiques ou métaheuristiques. Ces méthodes sont validées sur des jeux de données de test ainsi que sur un cas d'étude industriel. Un prototype d'application d'aide à la décision s'intégrant dans le système d'information de l'entreprise est présenté.

La thèse porte sur la proposition de méthodes d'optimisation (modèles mathématiques et métaheuristique) et leur couplage avec un modèle de simulation pour la résolution de problèmes de livraison collecte incluant la planification des horaires des chauffeurs. L'originalité de ces travaux porte sur la diversité des ressources (véhicule, chauffeur, quai de chargement, de déchargement, contenant, ligne de production, aire de nettoyage) et des contraintes (incompatibilité véhicule/contenant, date de début au plus tôt, date de fin souhaitée, planning...) à prendre en compte. L'objectif est de proposer une organisation permettant de réaliser l'ensemble des transports tout en minimisant les retards et les heures supplémentaires. La première partie s'intéresse au transport d'un seul type de produit. Le problème est modélisé comme un RCPSP avec profil de demande en ressources variable. Les transports à vide sont modélisés comme des temps de montage dépendant de la séquence. Deux programmes linéaires en nombres entiers sont proposés. La seconde partie concerne le transport de plusieurs types de produit. Le problème présente une double complexité qui est résolue par le couplage d'une recherche locale itérée avec un modèle de simulation. Le modèle de simulation permet de répondre à la complexité structurelle et fonctionnelle, notamment en raison de la diversité des ressources. La troisième partie intègre la définition des horaires de travail des chauffeurs. Une approche itérative incluant un modèle de simulation, un programme linéaire en nombres entiers et le couplage précédemment présenté est proposée. Ce problème est traité dans un contexte hospitalier pour le transport de contenants propres ou sales (repas, linge, médicaments) entre sites de consommation et sites de production. Chaque partie fait l'objet d'une expérimentation avec des données réelles.

Avec plus de 345 millions de tonnes de déchets produits en France en 2012, la performance de la chaîne logistique de collecte, transport et traitement de ces produits et matériaux est devenue un enjeu économique et écologique majeur dans notre société. Dans cette thèse, nous nous intéressons à l’optimisation de la chaîne de collecte et transport des déchets sur le plan tactique et opérationnel. Nous modélisons dans un premier temps un nouveau problème tactique d’optimisation de flux de déchets avec sites de transfert et de traitement sur un horizon mono-périodique puis multi-périodique, afin d’exploiter un réseau logistique existant de manière optimale. Nous résolvons différentes variantes de ce problème linéaire mixte à l’aide d’un solveur. Nous étudions dans un second temps la planification opérationnelle de la collecte de conteneurs d’apport volontaire et des tournées de véhicules associées en résolvant un problème riche de tournées avec gestion de stocks et plateformes de vidage intermédiaires. Nous proposons un modèle d’optimisation de ce nouveau problème et le résolvons par un algorithme à voisinages larges (ALNS) dans un cadre déterministe puis stochastique, dans lequel le remplissage des conteneurs est aléatoire et plus conforme à la réalité. Nous obtenons des résultats compétitifs en évaluant notre approche sur des instances de la littérature proches de notre problème riche. En réalisant un logiciel d’optimisation à destination d’une entreprise de collecte et transport de déchets, nous améliorons également de manière significative les tournées de véhicules en application réelle. / With more than 345 million tons produced in France in2012, waste supply chain management is an important economical and ecological issue for our society. In this thesis, we focus on optimizing waste supply chain on both the tactical and operational decision levels. In order to optimize an existing waste logistic network in medium term, we first solve a multimodal flow problem where products are transferred and transformed in sites of various size, in a mono-periodic then multi-periodic horizon. At an operational level, we study the planning and routing of vehicles used for voluntary drop-off waste container collection by solving a complex inventory routing problem with intermediate facilities. We use a large neighborhoods search metaheuristic to solve both the deterministic and stochastic approaches, where waste supply quantity is also subject to uncertainty. We obtain competitive results on instances coming from the literature on classical routing problems close to our rich case. We also develop an optimization software used by a French waste management company and significantly improve routes in a real application.

Les développements continus en micro-spectroscopie vibrationnelle IR et en analyse numérique de données multidimensionnelles ont permis récemment l'émergence de l'histologie spectrale. A l'échelle tissulaire et sur une base biomoléculaire, cette nouvelle approche représente un outil prometteur pour une meilleure analyse et caractérisation de différents états physiopathologiques, et potentiellement une aide au diagnostic clinique. Dans ce travail, en utilisant un modèle tissulaire de côlon normal chez la Souris et chez l’Homme, nous avons apporté des améliorations à la chaîne de traitements des données afin d'automatiser et d'optimiser cette histologie spectrale.En effet, dans un premier temps, le développement d’une double application hiérarchique d'indices de validité a permis de déterminer le nombre optimal de classes nécessaire à une caractérisation complète des structures histologiques. Dans un second temps, cette méthode a été généralisée à l'échelle interindividuelle par couplage d'un prétraitement par EMSC (Extended Multiplicative Signal Correction) et d'une classification non-supervisée k-Means; ce couplage étant appliqué conjointement à toutes les images spectrales IR. Enfin, compte tenu de l'essor des métaheuristiques et de leur capacité à résoudre des problèmes complexes d'optimisation numérique, nous avons transposé un algorithme mémétique aux données spectrales IR. Ce nouvel algorithme se compose d'un algorithme génétique et d'un raffinement par classification non-supervisée k-Means. Comparé aux méthodes classiques de clustering, cet algorithme mémétique appliqué aux images spectrales IR, a permis de réaliser une classification non-supervisée optimale et indépendante de l'initialisation. / Recent developments in IR vibrational microspectroscopy and numerical multidimensional analysis have led to the emergence of spectral histology. At the tissue level, this new approach represents an attractive tool for a better analysis and characterization of pathophysiological states and for diagnostic challenges. Here, using normal murine and human colon tissues, data processing steps have been improved for automating and optimizing this spectral histology. First, the development of a hierarchical double application of validity indices permitted to determine the optimal number of clusters that correctly identified the different colon histological components. Second, this method has been improved to perform spectral histology at the inter-individual level. For this, EMSC (Extended Multiplicative Signal Correction) preprocessing has been successfully combined to k-Means clustering. Finally, given the ability of metaheuristics to solve complex optimization problems, a memetic algorithm has been developed for IR spectral data clustering. This algorithm is composed of a genetic algorithm and a k-Means clustering refinement. Compared with conventional clustering methods, our memetic algorithm allowed to generate an optimal and initialization-independent clustering.

Notre travail porte sur l'étude du Problème de Routage et d'Allocation de Longueur d'Onde (Routing and Wavelength Allocation - RWA) dans des réseaux optiques WDM, indépendamment de la topologie physique sous-jacente. Le problème a été idntifié comme étant NP-difficile et plusieurs approches, tant exactes qu'approchées, existent. Nous fournissons d'abord une revue de littérature dans laquelle nous présentons quelques formulations mathématiques pour le problème ainsi que plusieurs manières d'obtenir des bornes inférieures et des heuristiques. Nous considérons le problème min-RWA dans lequel on doit satisfaire un certain nombre de requêtes avec le moins de longueurs d'onde possible. Nous présentons une méthodologie reposant sur une recherche locale de type Descente à Voisinage Variable (Variable Neighborhood Descent - VND) que l'on appelle VND-BFD. Son objectif principal est de supprimer des longueurs d'onde. Nous présentons également une méthode hybride VND-BT. Ensuite, nous proposons une nouvelle approche, elle-aussi reposant sur la VND. Elle consiste à ré-arranger les requêtes entre les longueurs d'onde disponibles. Lorsqu'elle atteint un optimum local, une procédure de perturbation est appliquée et le schéma est similaire à la Recherche Locale Itérée (Iterated Local Search - ILS). Quatre variantes sont définies selon les stratégies appliquées dans VND et ILS : VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p et VNDe-ILS5p. Les résultats expérimentaux montrent que cette nouvelle approche est plus performante, en particulier la version VNDe-ILS5p. La méthode est compétitive avec les meilleures méthodes de la littérature puisque VNDe-ILS5p a permis d'améliorer une grande partie des meilleures solutions connues sur les instances standard du min-RWA. Enfin, nous considérons aussi le problème max-RWA dans lequel on doit maximiser le nombre de requêtes traitées avec un nombre donné de longueurs d'onde. Nous proposons des modèles compacts ainsi que des améliorations destinées à accélérer la résolution par des solveurs en nombre entiers. Après avoir décrit des modèles existants utilisant la génération de colonnes, nous proposons un nouveau modèle, PG-MAX-IS-IRC, utilisant lui-aussi la génération de colonnes. Il permet d'obtenir des bornes supérieures de même qualité en un temps très fortement réduit. / This work deals with the routing and Wavelength assignment (RWA) in optical WDM networks independently on the underlying physical topology. We begin with a review of the literature presented some mathematical models formulated to solve theproblem, are also reviewed methods for setting lower bounds and heuristic methods. This problem has been shown to be NP-hard and several heuristic algorithms have been developed to solve it. We present in this work a methodology based on metaheuristic Variable Neighborhood Descent (VND), which we call VND-BFD, primarily with the focus on the elimination of wavelengths and a hybrid method VND-BT to solve the problem. Then we introduce a new approach also based on VND, but this time with the focus on the rearrangement of the requests, when this new version of the VND fails the procedure activates a disturbance, as the metaheuristic Iterated Local Search. We define four variants to this method, which we call VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p and VNDe-ILS5p. The computational experiments show that the approach with the focus on requestsproved more efficient, especially the version VNDe-ILS5p. The proposed method is competitive with respect to the best methods in the literature. Finally, we present compact models aimed at maximizing the number of requests accepted and some simplifications are proposed in order to speed up the resolution of problems. Although we present some models of literature based on column generation and a new methodology is proposed. The new methodology, which we call PG-MAX-IS-IRC, was able to solve all instances faster than the method of the literature and always found the same upper bound.

Ce manuscrit aborde des problèmes d’ordonnancement et de transport avec une modélisation explicite du transport. De tels problèmes se modélisent communément sous forme de graphes qui sont évalués afin d’obtenir les dates de début des opérations.Les évaluations classiques des graphes sont effectuées au moyen d’algorithmes de plus long chemin permettant d’obtenir une solution semi-active, où toutes les dates des opérations sont au plus tôt. Néanmoins, ces évaluations permettent généralement de ne prendre en compte que des critères de temps ou de distance à minimiser. Les travaux présentés dans ce manuscrit proposent de tenir compte de critères de qualité de service dans la fonction objectif. Cette prise en considération nécessite de nouvelles fonctions d’évaluation du graphe afin d’obtenir des solutions non nécessairement semi-actives permettant de maximiser la qualité de service. En effet, une solution semi-active propose rarement une qualité de service optimale. Les critères de qualité de service adoptés portent sur les ordonnancements et sur le transport.Trois problèmes intégrés sont successivement traités. Le premier problème est un problème de Job-shop avec transport et qualité de service, appelé Job-shop Scheduling Problem with Routing (JSPR). Des pièces, définies par une succession d’opérations, sont à fabriquer sur différentes machines, et entre deux opérations, la pièce doit être transportée de machine en machine. Le critère de qualité de service dans ce problème est dépendant des délais entre, d’une part les différentes opérations sur les machines, et d’autre part entre les différentes opérations de transport. Les gammes opératoires et les opérations de transport sont dépendantes les unes des autres.Le second problème est un problème de Workforce Scheduling and Routing Problem (WSRP), assimilable à un problème de planification de visites à domicile par un ensemble d’employés, et où le transport est pris en compte. Pour ce problème, le critère de qualité de service dépend des dates de début des visites. Les tournées sont indépendantes les unes des autres.Le troisième problème est le Generalised Workforce Scheduling and Routing Problem (GWSRP), qui prend en compte des contraintes de coordination entre les employés. Les tournées de ces derniers sont dépendantes les unes des autres. Elles nécessitent d’être toutes considérées simultanément pour évaluer les dates des visites respectant les contraintes de coordination et maximisant la qualité de service.Pour chaque problème, une nouvelle fonction d’évaluation est proposée. Pour le JSPR, cette fonction est basée sur l’algorithme de (Cordeau and Laporte, 2003) qui est initialement prévu pour le Dial-A-Ride Problem, ainsi que sur l’insertion de time-lags dans le graphe disjonctif du JSPR. Cette évaluation est incluse dans une métaheuristique. Pour le WSRP, la fonction d’évaluation est basée sur un algorithme de calcul du plus court chemin avec un algorithme de type programmation dynamique à labels. Elle est généralisée pour être utilisée dans une génération de colonnes. Et enfin, pour le GWSRP, l’évaluation est effectuée par un modèle PPC qui combiné à une génération de colonnes définissent tous deux un schéma d’optimisation global. / This manuscript addresses scheduling and transport problems where the transport is explicitly taken into account. Such problems are commonly modelled by graphs that are evaluated to obtain the starting times of operations.Classic graph evaluations are performed using longer path algorithms to obtain a semi-active solution, where all operations are left shifted. Nevertheless, these evaluations generally allow only time or distance criteria to be taken into account. The work presented in this thesis propose to take the quality of service criteria into account in the objective function. These considerations require new graph evaluation functions in order to obtain non-semi-active solutions that maximise the quality of service. Indeed, a semi-active solution rarely offers maximum quality of service. Three integrated problems are successively addressed. The first problem is a Job-shop Scheduling Problem with transport and quality of service, referred to as Job-shop Scheduling Problem with Routing (JSPR). Jobs, defined by a succession of operations, are to be performed on different machines, and between two operations, the job must be transported from a machine to another machine. The quality of service criterion in this problem depends on the delay between, on the one hand, the different operations belonging to the same job, and on the other hand, between the different transport operations. Machine-operations and transport-operations are dependent.The second problem is a Workforce Scheduling and Routing Problem (WSRP), which is similar to a problem of planning home services by a set of employees, and where transport is taken into account. For this problem, the quality of service criterion depends on the starting times of the visits. The trips of employees are independent.The third problem is the Generalised Workforce Scheduling and Routing Problem (GWSRP), which takes coordination constraints between employees into account. The trips are dependent on each other. The evaluation function of the starting times must consider simultaneously all trips in order to respect all coordination constraints and to maximise the service quality.For each problem, a new evaluation function is proposed. For the JSPR, this function is based on the algorithm of (Cordeau and Laporte, 2003) which is introduced first for the Dial-A-Ride Problem. The evaluation function, for the JSPR, is based on the insertion of time-lags in the disjunctive graph. This evaluation is included in a metaheuristic. For the WSRP, the evaluation function is based on the dynamic labelling algorithm used for an Elementary Shortest Path Problem With Resource Constraints. This function is generalised in order to be included in a column generation scheme. Finally, for the GWSRP, the evaluation is performed by a PPC model combined with a generation of columns and both define an overall optimisation scheme.

Dans ce mémoire, nous étudions un problème de tournées de véhicules dans lequel une flotte privée de véhicules n’a pas la capacité suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel à un transporteur externe. Ce dernier n’a aucune contrainte de capacité, mais un coût est encouru lorsqu’un client lui est affecté. Il n’est pas nécessaire de mettre tous les véhicules de la flotte privée en service si cette approche se révèle plus économique. L’objectif consiste à minimiser le coût fixe des véhicules, puis le coût variable de transport et le coût chargé par le transporteur externe. Notre travail consiste à appliquer la métaheuristique de recherche adaptative à grand voisinage sur ce problème. Nous comparons nos résultats avec ceux obtenus précédemment avec différentes techniques connues sur les instances de Christofides et celles de Golden. / In this master thesis, we study a vehicle routing problem in which a private fleet does not have sufficient capacity to serve all customers. Therefore, an external common carrier is required. The external common carrier has no constraint of capacity, but there is a cost when a customer it assigned to it. It is not necessary for all the vehicles of the private fleet to be used. The objective is to minimize the sum of the fixed cost of the private fleet, the variable routing cost and the external carrier cost. Our work applies the adaptative large neighborhood search metaheuristic on this problem. We compare our results with those obtained previously with different well-known techniques on the benchmark instances of Christofides and Golden.

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development. / Ce mémoire présente un nouvel algorithme métaheuristique de recherche taboue pour trouver des solutions optimales ou sous-optimales au problème de minimisation de la longueur des dépendances d’une matrice de conception (FLMP). Ce problème comporte une fonction économique non-linéaire et il appartient à la classe NP-ardu. Il s’ensuit qu’il est très difficile à trouver une solution optimale exacte en temps réel pour les problèmes de taille moyenne ou grande. D’abord, on présente le problème et une revue de la littérature associée. Ensuite, on analyse le problème, et on présente les détails du nouvel algorithme de recherche taboue produisant des solutions au problème de réduction de l’effet de retour en utilisant deux voisinages différents, le premier basé sur l’échange des positions de deux activités ("swap"), et le second sur le déplacement d’une activité à une position différente ("shift"). Des résultats numériques permettent d’analyser le comportement de l’algorithme et de comparer les deux voisinages. La première étape consiste à déterminer de bonnes valeurs pour les paramètres en utilisant des problèmes générés aléatoirement. Ensuite nos résultats sont comparés avec ceux obtenus dans la littérature. On conclut que l’algorithme de recherche taboue proposé est très prometteur, car nos résultats sont meilleurs que ceux publiés dans la litérature. D’autant plus que la recherche taboue semble avoir été utilisée pour la première fois sur ce problème.