Faculté des sciences de base SB, Département de mathématiques, Institut de mathématiques IMA (Chaire de recherche opérationnelle SE ROSE)

Problèmes de cheminements optimaux dans les réseaux avec contraintes associées aux arcs

Mittaz, Michel ; Hertz, Alain (Dir.)

Thèse sciences techniques Ecole polytechnique fédérale de Lausanne EPFL : 2000 ; no 2103.

Ajouter à la liste personnelle
    Summary
    In this thesis we consider two optimal routing problems in networks. Both are NP-hard and are often used to modelize real life problems of large size. We first present the capacitated arc routing problem (CARP). In this problem, we have to serve a set of customers represented by the arcs of a network with vehicles of restricted capacity. The aim is to design a set of vehicle routes of least total cost. We describe two heuristic methods for the CARP based on local search techniques. The first one is a Tabu Search heuristic using an original post-optimization procedure. Principles appearing in this procedure are used to define a class of neighborhoods we combine in a Variable Neighborhood Descent method. Our algorithms compare favorably with some of her methods. They were initially developed to deal with the undirected CARP. We describe how to transform them so that they can be applied to the directed CARP. We also propose an adaptation to the directed case of a lower bound originally developed for the undirected CARP. This lower bound is used to evaluate the quality of the solutions produced by our algorithms for the directed CARP. Our methods obtain solutions whose value is, on average, close to known lower bounds. We use the CARP to tackle a real life problem of boat routing and scheduling. This problem can be viewed as a directed CARP with time windows. We describe in detail its modeling process and we analyze our first results. We obtain solutions that require less boats than the present schedule. Nevertheless, these solutions are not completely feasible in practice. We suggest some ways to improve them. The second problem treated in this thesis is the shortest capacitated paths problem (SCPP). We present a Tabu Search heuristic and some post-optimization procedures for the SCPP. These procedures are called in our Tabu Search algorithm. Two versions of this algorithm are considered. In the first one, post-optimization procedures are intensively used. In the second one, they are less frequently applied. This second version is faster. Compared with a greedy approach, the two versions of our Tabu Search heuristic obtain solutions which are, on average, of better quality. The SCPP was proposed to us by EDF (Electricité de France) in order to minimize the total length of the paths followed by cables in a nuclear power-station. It can also be viewed as a subproblem of the bandwidth packing problem (BWP) appearing in telecommunications.
    Résumé
    Dans cette thèse, nous considérons deux problèmes de cheminements optimaux dans les réseaux. Ces deux problèmes sont NP-durs et sont fréquemment utilisés pour modéliser des problèmes pratiques de taille importante. Nous traitons tout d'abord le problème de tournées sur les arcs avec capacité (PTAC). Ce problème consiste à servir un ensemble de clients, représentés par les arcs d'un réseau, à l'aide de véhicules de capacité limitée. Le but est de minimiser la longueur totale des tournées accomplies par les véhicules. Nous présentons deux heuristiques basées sur des méthodes de recherche locale que nous avons développées pour résoudre le PTAC. La première est une méthode tabou. Elle fait appel à une procédure de post-optimisation originale. En se basant sur les principes utilisés dans cette procédure, nous avons défini une classe de voisinages que nous employons dans une méthode de descente à voisinage variable. Nos heuristiques se comparent favorablement à d'autres types de méthodes. Elles ont été initialement élaborées pour traiter le cas non orienté du PTAC. Nous décrivons comment les modifier pour les appliquer au PTAC orienté. Nous proposons également une adaptation au cas orienté d'une borne inférieure développée à l'origine pour le PTAC non orienté. Cette borne permet d'évaluer la qualité des solutions produites par nos algorithmes dans le cas orienté du PTAC. Ces derniers fournissent des solutions dont la valeur est, en moyenne, proche de celle de bornes inférieures. Un aspect, plus pratique du PTAC est abordé en étudiant un problème réel de confection d'horaires de bateaux. Nous décrivons ce problème en termes de PTAC avec fenêtres de temps. Le processus de modélisation est présenté en détail et les premiers résultats obtenus sont analysés. Nous avons trouvé des solutions nécessitant moins de bateaux que dans l'horaire actuel. Ces solutions ne sont cependant pas encore totalement utilisables en pratique. Quelques pistes sont suggérées pour les améliorer. Le deuxième problème abordé dans cette thèse est le problème de plus courts chemins avec capacité (PPCCC). Une méthode tabou pour la résolution du PPCCC est présentée ainsi que des procédures de post-optimisation. Ces procédures sont utilisées dans notre méthode tabou. Nous avons considéré deux variantes de cette dernière. La première utilise les procédures de post-optimisation de manière intensive. La seconde, plus rapide, les employe moins fréquemment. Comparées à une approche gloutonne, les deux variantes obtiennent des solutions qui, en moyenne, sont de meilleure qualité. Le PPCCC nous a été initialement proposé par EDF (Electricité de France) dans le but d'optimiser les itinéraires empruntés par des câbles dans une centrale nucléaire. Il peut aussi être vu comme un sous-problème du "Bandwidth Packing Problem" (BWP) apparaissant dans le domaine des télécommunications.