Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UNIVERSITÉ DE PICARDIE JULES VERNE D’AMIENS ÉCOLE DOCTORALE : Sciences, Technol

UNIVERSITÉ DE PICARDIE JULES VERNE D’AMIENS ÉCOLE DOCTORALE : Sciences, Technologie et Santé (ED 547) Spécialité : Informatique THÈSE DE DOCTORAT soutenue le 15 Juin 2015 par Ibrahim MOUSSA Modèles de résolution approchée et efficace pour les problèmes des réseaux de transport et de télécommunication Membres du jury : M. KACEM Imed Professeur Rapporteur M. SAUBION Fréderic Professeur Rapporteur M. GIANNAKOS Aristotelis Maître de Conférences Examinateur M. HAO Jin-Kao Professeur Examinateur M. HIFI Mhand Professeur Directeur M. SAADI Touﬁk Maître de Conférences Co-Encadreur R`e›m`eˇr`cˇi`e›m`e›n˚t˙s Ce travail s’est déroulé au sein de l’équipe ROAD de l’unité de recherche (EPROAD), dans une bonne ambiance. Au moment où j’achève ce travail, je pense avant tout à ceux qui m’ont soutenu et accompagné et je tiens à adresser mes re- merciements les plus sincères au professeur Mhand HIFI, directeur de cette thèse et directeur du EPROAD, pour m’avoir accueilli au sein de son équipe. J’ai particu- lièrement apprécié sa conﬁance, ses conseils et son suivi, mais je ne le remercierai jamais assez pour les remarques éclairées qu’il m’a prodiguées tout au long de cette thèse. Je remercie également M. SAADI Touﬁk, co-encadrant de cette thèse pour ses encouragements, ses conseils, ses connaissances dans le domaine et surtout, son soutient dans les moments de doute, ont été un réel apport. Je remercie les professeurs Frédéric SAUBION et Imed KACEM d’avoir accepté de rapporter ma thèse. Je remercie également le professeur Jin-Kao HAO et M. Aristotelis GIANNAKOS d’avoir accepté de faire partie du jury. Je proﬁte de cette occasion pour remercier chaleureusement tous les membres de l’unité de recherche EPROAD et quelques membres de l’unité de recherche LT I, pour avoir su créer une ambiance agréable et multi-culturelle. Je remercie particulièrement Sagvan SALEH pour son aide dans la programmation C++ et pour sa grande disponibilité durant mes problèmes de débogage. Finalement, tout mon respect va à mes parents pour leurs encouragements et ce malgré l’éloignement, à mon frère Oumar, sa femme Awa et ma petite nièce Kamila pour leur presence chaleureuse. Je ne peux m’empêcher en ce moment de remercier la république du Niger pour le soutien ﬁnancier qu’elle m’a accordé tout au long de cette thèse. iii Résumé Titre : Modèles de résolution approchée et eﬃcace pour les problèmes des réseaux de transport et de télécommunication. Le transport des personnes et des marchandises soulève un grand nombre de problèmes diﬃciles à résoudre. En général, l’objectif des compagnies de transport est souvent de visiter un ensemble de points (représentant des clients) à un moindre coût. Ces clients peuvent être considérés ponctuels comme un site bien précis, une station ou même un numéro de rue. Les délocalisations des sites de production, de distribution, de commercialisation et l’ouverture des marchés augmentent de plus en plus, l’intérêt des entreprises de transport à minimiser les coûts. En eﬀet, pour rester compétitif, les professionnels du transport doivent réduire des coûts d’exploitation (carburant, péage, location, etc) et contrôler l’empreinte écologique engendrée par leurs activités. Ceci revient alors, à optimiser le nombre de véhicules opérationnels et le nombre de trajets pour chaque véhicule, tout en respectant les contraintes liées à l’activité de l’entreprise (délais des livraisons, horaires des livraisons, temps de travail réglementaire des chauﬀeurs, type de marchandises transportées, nature et handicape éventuel des personnes à transporter, etc). Aujourd’hui, la recherche opérationnelle sur ce type de problèmes s’avère très importante car elle permet de concevoir des systèmes d’informations essentiels dans la prise de décision. En eﬀet, ces systèmes permettent de modéliser et de traiter les ﬂux d’informations de l’entreprise dans le but d’aider à la prise de décision. Notons ainsi que le but ﬁnal est de satisfaire les clients tout en respectant les contraintes à un moindre coût. Cette thèse porte sur la résolution approchée de deux problèmes de l’optimisa- tion combinatoire bien connus en recherche opérationnelle. C’est problèmes trouvent de larges champs d’application dans le domaine de transport des personnes ou de marchandises et dans le domaine de la télécommunication. La première partie de la thèse est consacrée au problème d’orientation d’équipe qui est une variante du célèbre problème de tournées de véhicules. La deuxième partie de la thèse s’attaque au problème de K-clusters dans un graphe biparti. Ce dernier est utile pour décom- poser et faciliter la résolution d’un problème combinatoire. Mots clés : Biclique, Cluster, Greedy, Heuristique, K-CmBCP, Logistique, Op- timisation combinatoire, Recherche opérationnelle, TOP, Transport, VRP. v vi Abstract Title : Approached and eﬀective resolution models for problems of trans- port and telecommunication networks. The transport of people and goods raises a large number of problems that are diﬃcult to solve. In general, the purpose of the transport companies is to visit at low cost, a set of points representing clients. These customers can be considered as a one-oﬀspeciﬁc site, a station or even a house number. Relocation of production sites, distribution, marketing and market openness increase more and more the interest of transport companies to minimize costs. In order to stay competitive, transport professionals need to reduce operating costs (fuel, tolls, location, etc) and check the ecological footprint generated by their activities to avoid any surcharges. This amounts to optimize the number of operational vehicles and the number of trips per vehicle, while respecting the constraints associated with the company’s business (delays in deliveries, schedules of deliveries, regular working hours of drivers, such freight traﬃc, nature and possible handicaps of transported people, etc). Nowadays, operational research on such problems is very important because it allows the design of critical information systems in decision-making. Indeed, these systems are used to model and treat the company’s information ﬂow in order to help decision making knowing that the ultimate goal is to satisfy customers, within the constraints and, at lower cost. This thesis focuses on the approximate resolution of two well known combinato- rial problems in operations research, and, that ﬁnd several applications in the ﬁeld of transportation of people or goods and in ﬁled of telecommunication : the ﬁrst part of the thesis is devoted to the team orienteering problem that is a variante of the famous vehicle routing problem and the second part of the thesis addresses the K-clusters minimum biclique completion problem in a bipartite graph. This problem is useful to decompose and help for solving a combinatorial problem. Keywords : Biclique, Cluster, Combinatorial Optimization, Greedy, Heuristics, K-CmBCP, Logistics, Operations Research, TOP, Transportation, VRP. Table des matières Introduction générale 3 I Le problème d’orientation d’équipe 7 1 Etat de l’art 9 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Etat de l’art sur le problème de tournées de véhicules . . . . . . . . . 10 1.3 Etat de l’art sur le problème d’orientation d’équipe . . . . . . . . . 14 1.4 Classiﬁcation des variantes du problème de tournées de véhicules . . 16 1.5 Classiﬁcation des variantes du problème d’orientation d’équipe . . . 19 1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Méthodes de résolution 25 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1 Notions sur les graphes . . . . . . . . . . . . . . . . . . . . . . 26 2.1.2 Notions sur la programmation linéaire . . . . . . . . . . . . . 27 2.2 Les Méthodes de résolution classiques . . . . . . . . . . . . . . . . . 28 2.2.1 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . 29 2.2.2 Les méthodes approchées . . . . . . . . . . . . . . . . . . . . 31 2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3 Une heuristique en deux phases pour le problème d’orientation d’équipe 39 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Le problème d’orientation d’équipe . . . . . . . . . . . . . . . . . . . 40 3.3 Formulation . . . . . . . . . . . . . . . . . uploads/Management/ these-moussa.pdf