Algorithme d'enumeration par programmation dynamique pour la gestion d'une flotte de vehicules automatiques oeuvrant dans une mine souterraine (French text)

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.