Un plus court chemin stochastique est un problème de plus court chemin dans un graphe dans lequel dans un sommet donné l’arc qui sera effectivement parcouru est choisi aléatoirement. C’est un cas particulier de processus de décision Markovien. Un Processus de Décisions Markovien (PDM) [1,2] est un modèle théorique qui se situe à la frontière de l’optimisation avec incertitude et de la théorie de la décision. Ces processus sont utilisés depuis de nombreuses années dans de nombreux cadres pratiques tels que la gestion de stock, la planification, l’optimisation de portefeuille, le contrôle des réseaux et plus généralement tout système qui évolue aléatoirement au cours du temps et que l’on cherche à contrôler et à optimiser. Trouver la meilleure politique peut se faire suivant trois grandes méthodes de calcul : la programmation linéaire, la programmation dynamique ou l’apprentissage par renforcement.
Dans, un plus court chemin stochastique on considère un graphe orienté. A chaque sommet l’arc qui va être parcourus va être tiré selon une probabilité qui dépend de la décision de celui qui parcourt le graphe. Le but est d’aller d’un sommet à un noeud terminal du graphe et le choix du critère sera de minimiser l’espérance du temps de parcours. On recherche la politique qui permet d’atteindre le minimum. Ce type de problème a un grand nombre d’utilisations tant dans la vie courante que comme modèle de base de nombreux problèmes scientifiques (routage dans les réseaux, optimisation de maintenance, plan de déplacements, stratégie en sport…).
Le but de ce projet est de comparer l’efficacité en pratique des différences méthodes de résolution et des logiciels qui les implémentent sur des instances issues de problèmes de plus court chemin stochastique. On utilisera pour chacune un solveur récent et qui s’interface facilement avec le langage python. On prendra Gurobi pour les solveurs linéaires, le suite tensor flow (tensor force) développée par google pour l’apprentissage par renforcement [3] et la suite logicielle Marmote pour la programmation dynamique.
Pour cela, on considérera un ou deux problèmes réels de plus court chemin pour lesquels une adaptation du modèle sera construite et codée (si besoin avec un travail sur l’interfaçage du logiciel) pour chaque méthode de résolution. Les comparaisons effectives seront alors lancées sur différentes instances de ces problèmes. La programmation sera principalement faite en python.
[1] Cours Décision et Jeux M1 Master Android.
[2] Description des MDP sur wikipedia :
https://fr.wikipedia.org/wiki/Processus_de_d%C3%A9cision_markovien
[3] Aurélien Géron, « Hands-On Machine Learning with Scikit-Learn & TensorFlow » O Reilly, 2017.