Soutenance mémoire
Problèmes généralisés de tournées de véhicules
Les problèmes généralisés de tournées de véhicules appartiennent à la classe de problèmes d’optimisation combinatoire généralisés. Les problèmes classiques de tournées de véhicules peuvent être généralisés de façon naturelle en considérant un problème dérivé dans lequel une partition donnée de nœuds (ou arcs) du graphe est regroupée en un ensemble de nœuds (ou arcs), que l’on appellera grappe. Grâce aux nombreuses nouvelles applications récentes, les problèmes généralisés ont un rôle de plus en plus important dans le domaine de la distribution, de la collecte, de la logistique, etc.
Problème généralisé de tournées sur nœuds
Avant d’introduire le problème généralisé de tournée sur les nœuds (GVRP), nous abordons d’abord les deux sous-problèmes suivants : le problème généralisé du voyageur de commerce (GTSP) et le problème généralisé du voyageur de commerce avec multiples véhicules (mGTSP). Le problème généralisé du voyageur de commerce est une généralisation d’un des problèmes les plus connus d’optimisation combinatoire : le problème du voyageur de commerce (TSP). Le GTSP peut être décrit comme suit. Soit G = (V, E) un graphe complet non orienté, V = {v1, …, vn} un ensemble de nœuds, E un ensemble d’arêtes et C = {C1, …, CK} un ensemble de grappes, avec 0 < K ≤ n. Chaque vi ∈ V appartient à exactement une grappe (notons que de cette manière, les grappes sont mutuellement disjointes). Notons cij le coût (distance, temps) entre les nœuds vi et vj . Le but est de chercher un tour de coût minimal visitant chaque grappe exactement une fois.
Le GTSP a été introduit initialement par Srivastava et al. [58] et Henry-Labordere [31]. Dans ces travaux primitifs, le problème a été résolu par la programmation dynamique. Il a ensuite attiré beaucoup d’attention de la communauté de recherche. Plusieurs recherches ont porté sur la transformation du GTSP en TSP (voir par exemple Ben-Arieh et al. [10], Laporte et Semet [39], Noon et Bean [45]). Cette transformation possède deux propriétés importantes : 1) les instances de TSP créées ont presque la même taille que celles du GTSP et 2) une solution optimale du TSP créée peut être convertie en une solution optimale du GTSP. Mais malheureusement, une solution non optimale réalisable du TSP résultant peut être non réalisable pour le GTSP. Par conséquent, la résolution du GTSP demande des solutions optimales des instances du TSP obtenues. Comme les structures des instances du TSP généré et du TSP standard sont différentes, la résolution de manière exacte du GTSP par la transformation en TSP est difficile pour les solveurs actuels du TSP. Une méthode exacte plus efficace pour le GTSP est un algorithme de branchement et coupes développé par Fischetti et al. [21] qui peut résoudre quelques instances jusqu’à 89 grappes et 442 nœuds.
Deux algorithmes d’approximation ont été publiés dans la littérature pour le GTSP. Slavík [56] a proposé un algorithme avec le ratio d’approximation de 3ρ/2, où ρ est le nombre de nœuds dans la grappe la plus grande (ρ = maxi=1,…,K(|Ci |). Malheureusement, le ratio dans le pire cas peut être relativement mauvais car ρ peut être assez grand. Garg et Konjevod [22] ont proposé un algorithme d’approximation de O(log² (n) log(log(n)) log(m)). Dans les deux algorithmes, l’inégalité triangulaire doit être satisfaite.
La plupart des travaux dans la littérature traite le problème par une méthode heuristique. Noon et Bean [44] ont proposé quelques heuristiques, incluant une adaptation de l’heuristique du plus proche voisin développée pour le TSP. Des adaptations similaires ont été implémentées par Fischetti et al. [21]. En suite, Renaud et Boctor [51] ont proposé une heuristique appelée GI3 (Generalized Initialization, Insertion and Improvement en anglais) qui était une généralisation de l’heuristique I3 présentée dans Renaud et al. [52] pour le TSP. Cette heuristique consiste de trois phases : une phase d’initialisation dans laquelle une partie du tour est construite, une phase d’insertion qui complète le tour en insérant un nœud d’une des grappes non-visitées qui donne le plus d’économie et une phase d’amélioration basée sur les mouvements de 2- et 3-opt. Des heuristiques constructives et des recherches locales ont été aussi discutées dans Bontoux et al. [12], Gutin et Karapetyan [28], Hu et Raidl [33], Snyder et Daskin [57]. Récemment, Karapetyan et Gutin [37] ont donné une révision de voisinages du GTSP et discuté en détail de différentes recherches locales.
Plusieurs métaheuristiques ont aussi été proposées pour le GTSP. Un des algorithmes les plus compétitifs publiés à ce jour est de Silberholz et Golden [54]. Il s’agit d’un algorithme génétique avec quelques nouvelles caractéristiques, incluant des populations initiales isolées et un nouveau mécanisme de reproduction basé sur l’opérateur ordonné de croisement du TSP. Ce nouveau mécanisme a été appelé mrOX (modified rotational ordered crossover en anglais). Les procédures d’amélioration locale combinées avec ce mécanisme permettent d’obtenir de très bons résultats sur de nouvelles instances de grande taille. Plus récemment, Bontoux et al. [12] ont proposé un algorithme mémétique où la procédure de croisement utilise la recherche locale à grand voisinage. Les résultats obtenus sur l’ensemble des instances standards avec jusqu’à 217 grappes et 1084 nœuds ont démontré l’efficacité de l’algorithme en terme de la qualité des solutions et temps de calcul. D’autres métaheuristiques pour le GTSP ont également été développées par Gutin et Karapetyan [28], Gutin et al. [29], Huang et al. [34], Pintea et al. [46], Tasgetiren et al. [60], Snyder et Daskin [57].
Le problème généralisé du voyageur de commerce avec multiples véhicules est une généralisation du problème du voyageur de commerce avec multiples véhicules (mTSP ou multiple Traveling Salesman Problem). Nous n’avons trouvé, à ce jour, aucun article qui traite ce nouveau problème. Le GmTSP peut être défini comme suit : Soit G = (V, E) un graphe complet non orienté, où V est un ensemble de nœuds et E est un ensemble d’arêtes. V = {v0, …, vn−1} est l’ensemble de n nœuds qui peuvent être visités, le nœud v0 est le dépôt où m véhicules de capacité illimitée sont localisés. C = {C0, …, CK−1} est un ensemble de K grappes disjointes qui doivent être visitées. Chaque nœud vi ∈ V appartient à exactement une grappe. Un coût cij est associé à chaque arête de E = {vi , vj : vi , vj ∈ V, i < j}. L’objectif du GmTSP est de déterminer m tours de coût minimal pour m véhicules, qui commencent et se terminent au dépôt, tels que chaque nœud de V \ {v0} soit visité au plus une fois et chaque grappe de C soit visitée exactement une fois.
Le problème généralisé de tournées sur nœuds (GVRP ou Generalized Vehicule Routing Problem) est une généralisation du problème classique CVRP, qui est aussi une extension du GTSP et également du GmTSP. Etant donné un graphe complet non orienté G = (V, E) et un ensemble de grappes C = {C0, …, CK−1} définis comme dans le cas du problème GmTSP, les différences par rapport au GmTSP sont les suivantes :
1. au nœud de dépôt v0, m véhicules identiques sont localisés, d’une capacité commune Q limitée
2. chaque grappe Ci , sauf C0 (qui se compose uniquement du dépôt), a une demande Di.
Le GVRP consiste à déterminer m routes telles que :
1. chaque route commence et se termine au dépôt ;
2. exactement un nœud de chaque grappe doit être visité une et une seule fois ;
3. la demande totale de chaque route ne dépasse pas la capacité du véhicule ;
4. le coût total est minimisé.
Le GVRP est clairement NP-difficile car il se réduit à un CVRP si chaque grappe comprend un seul nœud ou à un GmTSP si la capacité des véhicules est illimitée. Le nombre de papiers sur le GVRP est assez limité. Le problème a été introduit initialement par Ghiani et Laporte [24]. En 2003, Kara et Bekta¸s [36] ont proposé la première formulation de taille polynomiale. Un algorithme de colonies de fourmis et un algorithme génétique ont été proposés par Pop et al. [47] et Matei et al. [42] respectivement. Récemment, Bekta¸s et al. [9] ont proposé 4 formulations suivies par 4 algorithmes de branchement et coupes. Ils ont conclu que la meilleure formulation est une formulation non orientée à deux indices avec un nombre exponentiel de contraintes. Une heuristique de type recherche locale à grand voisinage (LNS ou Large Neighbourhood Search) a été aussi proposée dans ce papier pour fournir des bornes supérieures pour les algorithmes de branchement et coupes. Dans la même période que Bekta¸s et al. [9], Pop et al. [48] ont introduit deux nouvelles formulations. La première est une formulation basée sur les nœuds et similaire à la formulation de Kara et Bekta¸s [36] mais produit une borne inférieure plus forte tandis que la seconde est une formulation basée sur les flots. Dans ce travail, une seule instance de Ghiani et Laporte [24] a été résolue directement par CPLEX. Aucune autre expérience de calcul avec les formulations proposées n’a été publiée et aucun algorithme de branchement et coupes n’a été développé.
Le GVRP a des applications principalement dans la planification des réseaux de distribution et dans la conception de réseaux de télécommunications. Quelques domaines d’applications immédiates sont énumérées ci-dessous (voir Baldacci et al. [6], Bekta¸s et al. [9] et Pop et al. [48]) :
– Routage des navires dans le transport maritime : étant donné un certain nombre de régions dans lesquelles sont localisés des ports, l’organisation de la distribution via ces ports peut être telle que les navires livrent les marchandises à un seul port dans chaque région (port principal), et les marchandises sont ensuite distribuées dans toute la région. Ce problème de routage peut être modélisé comme un GVRP où les régions (avec leurs ports respectifs) correspondent aux grappes et la flotte de navires correspond à l’ensemble de véhicules.
– Distribution de produits médicaux : une application spécifique du GVRP se pose quand un certain nombre de districts, qui englobent chacun un certain nombre de municipalités, ont besoin d’être approvisionnées en produits pharmaceutiques et qu’il suffit de fournir tout un lot de produits à une municipalité dans chaque district. Dans ce cas, le problème de la distribution correspond à un GVRP dans lequel les districts représentent les grappes et l’équipe de distribution médicale correspond à l’ensemble des véhicules.
– Problème de collecte des déchets urbains : ce problème consiste à concevoir des routes pour un certain nombre de véhicules qui sont utilisés pour ramasser les déchets urbains et les livrer à un centre d’enfouissement, un incinérateur ou une usine de recyclage à un coût de transport minimum.
– Conception de réseau de télécommunication sécurisé : étant donné une infrastructure de télécommunication centralisée avec un serveur central et des grappes d’ordinateurs. La conception doit être faite de telle sorte qu’exactement un ordinateur dans chaque grappe soit connecté avec le serveur central, et qu’il existe exactement deux chemins qui n’ont aucune arête commune entre le nœud central et chaque grappe. La sécurité du réseau est assurée par ces deux chemins où l’un doit être activé si l’autre est en panne. De toute évidence, toutes les solutions réalisables du GVRP peuvent être utilisées pour mettre en œuvre une telle conception, où le serveur central est le dépôt.
Problème de la tournée couvrante
Le problème de la tournée couvrante (CTP ou Covering Tour Problem) est équivalent au GTSP si les grappes dans le GTSP sont jointes et est défini comme suit : Soit G = (V ∪ W, E1 ∪ E2) un graphe non orienté, où V ∪ W est un ensemble de nœuds et E1 ∪ E2 est un ensemble d’arêtes. V = {v0, …, vn−1} est l’ensemble des n nœuds qui peuvent être visités, et W = {w1, w2, …, wl} est l’ensemble des l nœuds qui doivent être couverts. Dénotons T = {v0, …, vt−1}, un sous-ensemble de V , correspondant à l’ensemble des nœuds qui doivent être visités. v0 est le dépôt. Un coût cij est associé à chaque arête de E1 = {vi , vj : vi , vj ∈ V, i < j} et une distance dij est associée à chaque arête de E2 = {vi , vj : vi ∈ V \ T, vj ∈ W}. La mission du CTP est de déterminer une route fermée commençant et terminant au dépôt telle que :
1. chaque nœud de T soit visité exactement une fois et chaque nœud de V \ T soit visité au plus une fois ;
2. chaque nœud de W soit couvert par la route, c’est-à-dire, se situe à une distance maximum r d’au moins un nœud de V \ T qui est visité, où r est le rayon de couverture.
|
Table des matières
1 Introduction générale
2 Problèmes généralisés de tournées de véhicules
2.1 Problème généralisé de tournées sur nœuds
2.2 Problème de la tournée couvrante
2.3 Problème généralisé de tournées sur arcs
2.4 Problème de la tournée sur arcs suffisamment proche
2.5 Conclusion
3 Problème de la tournée sur arcs suffisamment proche
3.1 Des formulations mathématiques pour le CEARP
3.2 Méthodes de résolution proposées
3.3 Evaluation numérique
3.3.1 Implémentation et jeux de donnés
3.3.2 Pourquoi nos instances sont-elles difficiles ?
3.3.3 Résultats des évaluations numériques
3.4 Conclusion
4 Problème de tournées couvrantes multi-véhicules
4.1 Nouvelle formulation pour le mCTP
4.2 Méthodes de résolution proposées
4.2.1 Algorithme de branchement et coupes
4.2.2 Une métaheuristique pour le mCTP
4.3 Evaluation numérique
4.3.1 Implémentation et jeux de donnés
4.3.2 Résultats de l’évaluation numérique
4.4 Conclusion
5 Problème généralisé de tournées sur nœuds
5.1 Nouvelle formulation pour le GVRP
5.2 Méthodes de résolution proposées
5.2.1 Algorithme de branchement et coupes
5.2.2 Une métaheuristique pour le GVRP
5.3 Evaluation numérique
5.4 Conclusion
6 Conclusion générale
