Le problème périodique de tournées sur les arcs avec contraintes de capacité et de gestion de stocks

Dans cette thèse, on introduit le problème périodique de tournées sur les arcs avec contraintes de capacité et de gestion de stocks. Les arêtes d'un réseau représentent les clients qui nécessitent une certaine quantité de matériel. Ce matériel est mis en inventaire et consommé au cours du temps. Les besoins de réapprovisionnement indiquent la nature périodique du problème. Les exemples d'applications de ce problème sont l'arrosage des chemins de terre dans les mines à ciel ouvert pour supprimer la poussière, l'arrosage des routes dans les réseaux forestiers et l'arrosage des plantes sur les trottoirs des rues. On prend l'application de l'arrosage des routes dans les mines à ciel ouvert. Un camion-citerne se déplace le long des routes en arrosant de l'eau pour supprimer la poussière. À cause de sa capacité limitée, le camion doit retourner au dépôt avant de commencer une nouvelle tournée. À cause de l'évaporation de l'eau, l'humidité sur les routes diminue en fonction du temps. Les routes ont besoin d'un certain niveau d'humidité pour retenir efficacement les particules de poussière. Une pénurie arrive lorsque le niveau d'humidité se trouve en dessous du niveau requis. L'objectif de cette étude est de trouver un ensemble de tournées qui débutent et finissent au dépôt de telle façon que les coûts de pénalité liés à la pénurie, ainsi que les coûts de routage soient minimisés. Parce que l'ordre dans lequel les arêtes sont traversées et arrosées affecte le moment où l'humidité est restaurée, des décisions sur le routage et la gestion de l'inventaire sont prises simultanément. Ce problème a été traité pour les tournées sur les nœuds, i.e., les clients sont situés aux nœuds du réseau, et il est appelé Inventory Routing Problem. Cependant, il n'a pas été traité dans le domaine de tournées sur les arcs. Étant donné la capacité limitée du camion et la nature périodique du remplissage, on considère cette application comme un problème périodique de tournées sur les arcs avec contraintes de capacité (PCARP). Au début, on considère le cas du problème d'arrosage où il n'existe qu'un seul dépôt (réservoir d'eau) dans le réseau et un seul camion-citerne. On travaille sur un réseau mixte dans lequel, pour chaque arête, il y a deux arcs, un dans chaque direction de traverse. Il y a aussi une boucle artificielle au dépôt qui représente le remplissage du camion. L'horizon de temps est divisé en périodes de temps de même durée. Les coûts et les quantités en inventaire sont calculés pour chaque période de temps. On élabore un modèle de programmation linéaire en nombres entiers qui est testé pour des exemplaires connus du problème de tournées sur les arcs avec contraintes de capacité (CARP). La solution indique la séquence optimale de traverse et d'arrosage des arêtes, le remplissage du camion au dépôt, s'il a lieu, et les coûts totaux de routage et de pénalité pour la pénurie sur le niveau d'humidité. Les limites de ce modèle sont établies en fonction de la taille des réseaux et de la longueur de l'horizon de temps qu'on est capable de résoudre. On est capable de trouver la solution optimale pour des réseaux avec 40 à 55 arêtes pour 20 à 30 périodes de temps. Ce qui correspond à un horizon de temps de 30 minutes en réalité. Deux situations sont testées, lorsque la quantité d'eau arrosée aux arêtes est variable ou constante. Les résultats sont présentés pour valider les deux situations. La contribution de cette première approche est le modèle mathématique pour résoudre le problème d'arrosage des routes dans les mines à ciel ouvert. La deuxième approche a pour objectif de résoudre des exemplaires de plus grande taille et pour un horizon de temps plus long. On modifie le modèle mathématique pour inclure plus d'un véhicule et un seul dépôt. Avec ces modifications on est capable de trouver la solution optimale pour un exemplaire de petite taille, 11 arêtes, pour un horizon de temps de 20 minutes. Pour résoudre des exemplaires de plus grande taille et incrémenter l'horizon de temps, on utilise un algorithme heuristique appelé adaptive large neighborhood search (ALNS). L'ALNS se compose de huit opérateurs de destruction et de réparation choisis au hasard pour modifier la solution existante à chaque itération. La performance des opérateurs détermine la probabilité d'être choisi aux itérations suivantes. Une meilleure performance de l'opérateur, en termes d'amélioration de la solution existante, correspond à une plus grande probabilité d'être choisi. On utilise un ensemble d'exemplaires du CARP et un ensemble d'exemplaires créé à partir des réseaux de mines à ciel ouvert réels. Cette heuristique est capable de trouver une solution réalisable pour un horizon de temps de 300 minutes. Les opérateurs sont testés individuellement et en les combinant entre eux en utilisant un critère d'arrêt de 25000 itérations. On trouve la combinaison qui obtient la meilleure amélioration du coût total pour chaque ensemble d'exemplaires. Les contributions de cette approche sont la modification du modèle mathématique afin d'inclure plus d'un véhicule et l'application de l'heuristique ALNS pour obtenir une solution à ce nouveau problème. Finalement, un dernier problème est abordé. Il consiste à localiser un ou plusieurs dépôts (réservoirs d'eau) le long des nœuds du réseau pour réduire les coûts de pénurie et de routage du problème d'arrosage des routes dans les mines à ciel ouvert. Comme l'activité principale se trouve sur les arêtes du réseau, ce problème correspond à un problème de localisation et de tournées sur les arcs (LARP) avec une composante périodique. Ce problème a été traité pour les tournées sur les nœuds. Cependant, il n'y a pas une autre application dans laquelle la localisation des dépôts est faite dans le domaine des problèmes périodiques de tournées sur les arcs. On prend des décisions à long terme telles que la localisation des dépôts et des décisions à court terme telles que le routage et la gestion des stocks. Pour cette raison, plusieurs scénarios sont testés et leur coût moyen est ajouté aux coûts de localisation des dépôts afin d'obtenir un coût total pour le problème. Les scénarios sont le résultat de changements dans les paramètres du problème qui peuvent se produire sur un horizon de planification à long terme. Trois algorithmes de localisation sont utilisés pour obtenir une solution initiale à la localisation d'un et de plusieurs dépôts. Ces algorithmes suivent le processus Location, allocation and Routing (L-A-R), une méthode divisée en trois parties : premièrement, on place les dépôts sur les nœuds du réseau, puis on affecte les arêtes aux camions et finalement on trouve une tournée. L'heuristique ALNS développée pour l'approche précédente est adaptée et utilisée pour améliorer la solution. On compare la localisation d'un dépôt \`a différents endroits. On compare aussi les trois algorithmes de localisation. La contribution de cette partie est le développement d'un algorithme appliqué à la localisation de dépôts pour un problème périodique de tournées sur les arcs avec contraintes de capacité.