Algorithme d'énumération par programmation dynamique pour la gestion d'une flotte de véhicules automatiques oeuvrant dans une mine souterraine

Les systèmes de gestion d'une flotte de véhicules automatiques visent une réduction des coûts d'opérations, ainsi qu'une amélioration de la productivité. Ce mémoire présente une étude du problème de choix des routes pour l'automatisation des véhicules de manutention opérant en souterraine. Le problème consiste à assigner de meilleures routes pour un ensemble de véhicules évoluant dans un réseau minier souterrain. Le réseau comporte des segments bidirectionnels à une seule voie. Le problème présente aussi des contraintes de conflit entre les véhicules, ainsi qu'une contrainte par rapport à l'orientation des véhicules. Deux approches permettent de résoudre le problème. Une méthode véhicule par véhicule permet de déterminer la route d'un véhicule selon les déplacements préétablis des autres véhicules du système. Une méthode globale quant à elle, réassigne les routes pour l'ensemble des véhicules à chacune des requêtes nécessaires au plan de production. Ce mémoire présente un algorithme d'énumération par programmation dynamique développé pour résoudre le problème d'une manière globale. Le projet permet d'élaborer deux modèles. Le premier modèle représente la position des véhicules sur les segments de route ou aux intersections, alors que le deuxième modèle crée des états selon la position des véhicules uniquement sur ces segments. Pour chaque modèle, des propositions et des procédures sont proposées pour assurer un enchaînement admissible, c'est-à-dire sans conflits, entre deux états. L'algorithme global permet d'analyser l'écart des solutions entre les deux approches de résolution. De plus, l'étude de différents critères de recherche permet d'améliorer le temps de résolution en vue d'une application en temps réel. Les résultats montrent l'efficacité de résolution des méthodes véhicules par véhicules dans un environnement minier.

Abstract

The objectives of automated guided vehicles systems are to reduce operation cost and to improve productivity. This master thesis is a study of a route selecting problem regarding hauling vehicles in underground mine. The problem consists in assigning the best routes to a set of vehicles in an underground mine road network. The network segments are bidirectional on a single path. The problem includes vehicles conflict constraints, as well as vehicles orientation constraints. The problem can be resolved by two approaches. A vehicle route can be assessed from a vehicle by vehicle approach taking into account the existing routes of the other vehicles in the system. A global approach re-assigns the routes to all the vehicles upon every request needed by the schedule production. In this thesis, a dynamic programming enumeration algorithm is presented which can resolve the problem by a global approach. Two models are developed. For the first model, states are represented by vehicles position on arcs and nodes of the network. The second model only use arcs to represent vehicles position. Procedures and propositions are presented to allow states progression. The algorithm allows us to study the variation that occurs between the solutions coming from global and vehicle by vehicle approaches. Moreover, the algorithm resolving time can be reduced by different research criteria through the enumeration tree. The results show the effectiveness of the vehicle by vehicle methods for mining operation.----------CONTENU Description des opérations minières souterraines -- Le réseau minier -- La manutention du minerai -- Systèmes de gestions d'une flotte de véhicules automatiques -- Les contraintes liées au réseau -- Mines à ciel ouvert -- Mines souterraines et milieu manufacturier -- Formulation du modèle mathématique -- Principes généraux de programmation dynamique -- Représentation du graphe physique -- Caractéristique du modèle -- Les états -- Les étapes -- Les coûts -- Les actions -- La valeur des états -- La relation de récurrence -- Règles de propagation des états -- Gestion des conflits -- Conflits aux intersections -- Conflits sur les arcs -- Schéma de résolution -- Règle de dominance -- Recherche de solutions -- Critère de sélection des états -- Évaluation des bornes -- Résultats sommaires -- Méthodologie -- Présentation des scénarios et résultats -- Adaptation pour l'orientation des véhicules -- Modélisation de l'orientation -- Problématique d'orientation sur un nœud -- Modification à la modélisation des états -- Modification aux contraintes -- Analyse des résultats -- Comparaison avec la modélisation incluant les nœuds -- Évaluation de l'algorithme sur des problèmes orientés -- Amélioration de l'algorithme -- Simulations.