Le transport optimal : le chemin le plus court

OUSSAMA SAIDI (TIPE 2019)

[pic 1]

Le titre :    

Le transport optimal : le chemin le plus court

• Positionnement thématique

MATHEMATIQUES (la recherche opérationnelle), INFORMATIQUE (Informatique appliquée).

• Mots-clés (en français)

Complexité temporelle

Heuristiques

Algorithmes gloutons

Application de permutation

Problème NP-complet

• Mots-Clés (en anglais)

Time complexity

Heuristic

Greedy algorithms

permutation application

NP-complete problem

• Bibliographie commentée

La recherche du chemin le plus court consiste à minimiser la distance de parcours d’un certain nombre de points. Ce problème est apparu au premier lieu sous la forme d’une optimisation d’un trajet au début du XIXe siècle, formulé par le mathématicien irlandais William Rowan Hamilton [1]. En 1954, la solution a été trouvée pour 42 villes américaines, puis en 2004, le problème est résolu pour près de 25 000 villes suédoises. La recherche du chemin le plus court est récurrente dans le domaine du transport (dessin des lignes de métro), des réseaux électriques, et aussi dans le domaine militaire. Mathématiquement, il s’agit de trouver la permutation des points telle que la somme des distances entre deux points consécutifs est minimale.

Atteindre ce chemin optimal n’est pas aisé car il s’agit d’un problème NP-Complet : c'est-à-dire on n’ignore toujours une solution ayant une complexité polynomiale pour résoudre ce problème [2]. Un algorithme naïf, qui vérifie toutes les solutions afin de choisir la plus adéquate, exige une complexité de l’ordre de (n!), ce qui est loin d’être acceptable pour plus d’une dizaine de points. Les algorithmes les plus performants permettant de trouver la solution parfaite ont quant à eux une complexité de l’ordre de (2^n . n²) [3]. Cette dernière complexité est plus favorable que l’autre et plus raisonnable pour un petit nombre de points, mais aussi inabordable pour un nombre de points important.

Obtenir la solution parfaite n’est donc pas envisageable lorsque le nombre de points est trop élevé.

Il faut s’intéresser donc plutôt à la recherche de différentes méthodes permettant d’arriver à une solution approximative du problème, avec une complexité polynomiale et à trouver une solution pour un nombre de points de l’ordre de plusieurs milliers, c'est-à-dire là où les algorithmes cités précédemment sont incapable.

Afin de réduire la complexité temporelle tout en minimisant autant que possible la distance parcourue, en exploitant des méthodes de résolution approximative du problème, approchant autant que possible la solution optimale, mais en un temps au pire polynomial : c'est le principe des méthodes heuristiques. Ces méthodes consistent à utilisant notamment des algorithmes gloutons [4][5]. Ceux-ci choisissent à chaque fois la solution qui leur paraît être la meilleure à court terme : ils progressent ainsi dans le problème et permettent d’obtenir une solution proche de la solution optimale. Il s’agit ainsi d’un gain en complexité énorme pour une faible perte dans la solution finale.

...