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é.

Abstract

This dissertation introduces the periodic capacitated arc routing problem with inventory constraints. The edges of a network act as customers that require a certain quantity of material. It is then held as inventory and consumed over time. The need for replenishment of the consumed material explains the periodic nature of the problem. Some examples of applications of this problem are the road watering in open-pit mine roads to suppress dust, road watering in forest roads and plant watering on street medians and sidewalks. This work focuses on the application of road watering in open-pit mines. A water truck travels along the roads of a mine spraying water to suppress dust. Because of its limited capacity, the truck needs to replenish at a water depot before starting a new route. Due to water evaporation, the humidity on the roads decreases over time. Roads require a certain amount of humidity to effectively retain dust particles. A shortage happens when the humidity level drops below the required level. The objective of this thesis is to find a set of routes that start and end at the depot so that the penalty costs associated with shortage, as well as the routing costs are minimized. Because the order in which roads are traversed and watered affects their humidity level, routing and inventory decisions are made simultaneously. This problem has been treated for node routing, i.e., the customers are located at the nodes of the network, and it is called the Inventory Routing Problem. However, it has not being addressed in the arc routing domain. This problem is modeled as a periodic capacitated arc routing problem due to capacity constraints and the frequency of service. The first case studied is where there is only one water depot and one vehicle to travel along the network. A mathematical model is developed using a mixed network. For each edge, there are two arcs that correspond to the direction in which the edge can be traversed. There is an artificial loop at the depot that represents the refill of the truck. The time horizon is divided in time periods of equal duration. Costs and inventory levels are calculated for each time period. The model is tested for known instances of the capacitated arc routing problem (CARP). It is able to solve to optimality networks of 40 to 55 edges for a time horizon of 20 to 30 periods. Two situations are considered where the quantity of water delivered to the edges is variable and constant. Results are reported to validate both situations. The contribution of this first approach is the mathematical model to solve the road watering problem. The mathematical model is then modified to include more than one vehicle. As the number of variables increases, it is capable of solving to optimality a network of 11 edges for a time horizon of less than 30 time periods. An adaptive large neighborhood search (ALNS) heuristic is developed to solve larger networks for a longer time horizon. It is able to provide a feasible solution for networks up to 55 edges and a time horizon of 300 time periods. The ALNS consists of an initial solution obtained using a construction algorithm and eight destroy-repair operators that are randomly selected to modify the initial solution at each iteration of the algorithm. The performance of these operators determines the probability of being selected for the next iteration. A better performance of the operator, in terms of improving the existing solution, corresponds to a higher probability of being selected. The operators are tested individually and in different combinations. The best combination is selected for each set of instances. Apart from the CARP instances, ten instances are created to test the algorithm. These new instances correspond to road networks of real open-pit mines. The contributions of this approach are the modification of the mathematical model to include more than one vehicle and the application of the ALNS to obtain a solution for this new problem. Finally, a new problem is addressed. It consists in the location of one or more water depots along the nodes of the network to reduce the shortage and routing costs. Because the solution is obtained by servicing the edges of a network, this problem corresponds to a location arc routing problem (LARP) with a periodic component. This problem has only been treated in the node routing domain. No other application has been studied for location in the arc routing domain. Long term decisions, such as depot location, are combined with short term decisions, such as routing and inventory replenishment. Several scenarios are tested and their average cost is added to the depot placement costs in order to obtain a total cost. These scenarios are the result of changes in the parameters of the problem that can occur over a long planning horizon. Three location algorithms are used to obtain an initial solution to the location of one and several depots. The algorithms follow a location, allocation and routing (L-A-R) approach in which, first the depots are placed, then the edges are assigned to the service trucks and finally, a route is formed. The ALNS developed for the previous approach is adapted and used to improve the solution. The contribution is an algorithm applied to the location of depots for a periodic capacitated arc routing problem.