Comment les algorithmes transforment-ils une carte de ville en un problème mathématique ?

Il est midi à Dakar. Dans un restaurant des Almadies, plusieurs commandes attendent d'être récupérées. Trois clients doivent être livrés : l'un à Ngor, un autre à Ouakam et le dernier à Mermoz.

Le livreur connaît la ville. Il sait qu'en empruntant certaines rues, il peut éviter un détour. Mais aujourd'hui, une difficulté supplémentaire se présente : les trois commandes doivent arriver rapidement, et les conditions de circulation peuvent changer d'un quartier à l'autre.

Faut-il commencer par le client le plus proche ? Livrer d'abord celui qui attend depuis le plus longtemps ? Choisir les grandes avenues, même si elles allongent le trajet ?

Ce problème, en apparence ordinaire, appartient à un domaine des mathématiques appelé recherche opérationnelle. Il mobilise notamment la théorie des graphes, l'algorithmique et l'optimisation combinatoire.

Ces outils permettent d'étudier une question simple à formuler, mais parfois redoutablement difficile à résoudre : comment organiser plusieurs déplacements pour obtenir le meilleur résultat possible ?

Une ville peut se représenter par des points et des lignes

Pour un mathématicien, une carte routière peut être transformée en un objet beaucoup plus abstrait : un graphe.

Un graphe est constitué de deux éléments :

• des sommets, qui représentent ici des intersections, des lieux de départ ou des destinations ;

• des arêtes, qui représentent les routes reliant ces différents points.

On note généralement un graphe :

où V désigne l'ensemble des sommets et E l'ensemble des arêtes.

Prenons un réseau routier fictif composé de cinq intersections. Chaque route possède une longueur exprimée en kilomètres.

Pour calculer la distance totale d'un itinéraire, il suffit d'additionner les longueurs des routes empruntées.

Si un livreur suit le parcours A \rightarrow B \rightarrow C \rightarrow D, sa distance totale est :

Mais les routes ne sont pas toutes équivalentes. Certaines sont à sens unique, d'autres sont difficiles d'accès. Une route peut également être courte tout en étant particulièrement lente à certaines heures.

On enrichit alors le graphe en attribuant une valeur à chaque arête. Cette valeur est appelée un poids.

Selon le problème étudié, le poids peut représenter une distance, une durée de trajet, une consommation de carburant ou un coût.

Cette distinction est essentielle : les mathématiques ne cherchent pas spontanément le « meilleur » chemin. Elles cherchent le meilleur chemin selon un critère que l'on doit définir.

Le plus court chemin n'est pas nécessairement le plus rapide

Imaginons deux itinéraires possibles entre un restaurant et un client.

Le premier mesure 4 kilomètres et traverse plusieurs rues encombrées. La vitesse moyenne y est de 12 km/h.

Le second mesure 6 kilomètres, mais emprunte une voie plus fluide sur laquelle la vitesse moyenne atteint 30 km/h.

Le temps de parcours peut être estimé à partir de la relation :

Pour le premier itinéraire :

Pour le second :

Le deuxième trajet est donc plus long de deux kilomètres, mais permet de gagner huit minutes.

Cet exemple est volontairement simplifié : les vitesses moyennes sont supposées constantes et les temps d'arrêt ne sont pas pris en compte.

Il révèle néanmoins une difficulté fondamentale. Un algorithme chargé de minimiser la distance ne produira pas nécessairement le même résultat qu'un algorithme chargé de minimiser la durée.

Dans une application de livraison, cette différence peut avoir des conséquences importantes. Le trajet choisi influence le temps d'attente du client, les déplacements du livreur et, parfois, le coût du service.

Dijkstra : trouver un chemin sans explorer toutes les possibilités

En 1959, le mathématicien et informaticien néerlandais Edsger W. Dijkstra publie un article consacré à deux problèmes sur les graphes, dont celui du plus court chemin.

L'algorithme qui porte aujourd'hui son nom est devenu l'une des méthodes classiques de recherche de chemins dans un réseau.

Son principe repose sur une idée élégante : plutôt que d'examiner toutes les routes possibles, on construit progressivement les meilleures distances connues depuis un point de départ.

Supposons qu'un livreur parte du point A et souhaite rejoindre D.

Au départ, la distance connue entre A et lui-même est nulle :

Les autres distances sont initialement considérées comme infinies, car aucun chemin n'a encore été identifié.

L'algorithme examine d'abord les routes accessibles depuis A.

Il découvre qu'il est possible de rejoindre B en 3 kilomètres et C en 7 kilomètres.

Le sommet B, qui possède la plus petite distance provisoire, est traité en premier.

Depuis B, une autre route permet de rejoindre C en 2 kilomètres supplémentaires. Le parcours A \rightarrow B \rightarrow C mesure donc :

C'est mieux que les 7 kilomètres du trajet direct entre A et C.

La distance connue pour C est alors mise à jour.

En poursuivant le raisonnement, l'algorithme trouve :

avec une distance totale de :

Dans ce réseau, aucun autre chemin entre A et D n'est plus court.

L'algorithme de Dijkstra garantit ce résultat lorsque les poids des arêtes sont non négatifs, ce qui correspond notamment au cas des distances routières.

Son intérêt dépasse largement la livraison : la recherche de chemins intervient aussi dans les réseaux informatiques, les systèmes de navigation et de nombreux problèmes d'organisation.

Référence scientifique : Edsger W. Dijkstra, « A Note on Two Problems in Connexion with Graphs », Numerische Mathematik, 1959.

Une livraison, c'est simple. Plusieurs livraisons, beaucoup moins.

Trouver le meilleur chemin entre deux points est une chose. Déterminer dans quel ordre visiter plusieurs destinations en est une autre.

Revenons à notre livreur de Dakar.

Il doit livrer trois clients, puis revenir à son point de départ. Même s'il connaît les distances entre tous les quartiers, il doit encore décider dans quel ordre effectuer les livraisons.

Avec trois destinations, il existe :

ordres de visite possibles.

Le symbole « ! » désigne la factorielle.

Pour dix destinations, le nombre d'ordres possibles devient :

Avec quinze destinations :

Soit plus de 1 300 milliards de possibilités.

Ces calculs supposent que toutes les destinations peuvent être visitées dans n'importe quel ordre. Dans la réalité, certaines contraintes peuvent exclure des parcours.

Mais l'explosion du nombre de combinaisons demeure.

Ce phénomène est au cœur du célèbre problème du voyageur de commerce, connu sous son nom anglais Travelling Salesperson Problem (TSP).

Dans sa formulation classique, il s'agit de trouver le circuit le plus court permettant de visiter une série de villes une seule fois avant de revenir au point de départ.

Le problème paraît élémentaire. Pourtant, lorsque le nombre de destinations augmente, rechercher systématiquement toutes les solutions devient rapidement impraticable.

C'est pourquoi les informaticiens utilisent des méthodes capables de réduire l'espace de recherche, d'éliminer certaines possibilités ou de construire rapidement des solutions de bonne qualité.

Il faut ici distinguer deux objectifs : trouver une solution optimale, dont on peut démontrer qu'aucune autre n'est meilleure, et trouver une bonne solution rapidement, même si son optimalité n'est pas garantie.

Dans de nombreuses situations réelles, cette deuxième approche est particulièrement utile.

Quand plusieurs livreurs entrent dans l'équation

La difficulté augmente encore lorsqu'une entreprise doit organiser les tournées de plusieurs livreurs.

Supposons qu'un service dispose de quatre motos et de vingt commandes à distribuer dans différents quartiers.

Il ne suffit plus de déterminer l'ordre des livraisons. Il faut également décider quelles commandes seront attribuées à chaque livreur.

Cette famille de problèmes porte le nom de Vehicle Routing Problem, ou problème de tournées de véhicules.

On peut chercher à minimiser la distance totale parcourue :

où m représente le nombre de livreurs et D_k la distance parcourue par le livreur k.

Mais cette fonction ne traduit pas toutes les exigences d'un service de livraison.

Par exemple, minimiser la distance totale pourrait conduire à attribuer une tournée très longue à un livreur et des tournées beaucoup plus courtes aux autres.

Si l'objectif est de terminer l'ensemble des livraisons le plus tôt possible, on peut plutôt chercher à minimiser la durée de la tournée la plus longue :

où T_k représente la durée de la tournée du livreur k.

Le choix de la fonction à minimiser change donc profondément la manière d'organiser le travail.

À cela s'ajoutent des contraintes concrètes : capacité de transport, disponibilité des livreurs, horaires de livraison ou ordre de préparation des commandes.

Certains problèmes imposent même des fenêtres temporelles : un client doit être livré entre deux heures précises.

Les méthodes de recherche opérationnelle permettent de représenter mathématiquement ces contraintes et de chercher des tournées compatibles avec elles.

Les limites d'un itinéraire calculé à l'avance

Jusqu'ici, nous avons raisonné comme si les distances et les durées étaient connues.

Or, dans une ville, le réseau routier n'est pas figé.

Un embouteillage peut apparaître. Une rue peut être temporairement inaccessible. Un client peut demander un changement de lieu de livraison. Une nouvelle commande peut arriver alors qu'un livreur est déjà en déplacement.

Le problème devient alors dynamique.

Pour le modéliser, le temps de parcours d'une route peut dépendre de l'heure à laquelle on l'emprunte.

On peut écrire :

où t_{ij} désigne le temps nécessaire pour aller du point i au point j, et \tau l'heure de départ sur cette route.

Un trajet qui nécessite dix minutes à 10 heures peut en demander vingt à 18 heures.

L'itinéraire calculé le matin n'est donc pas nécessairement pertinent en fin de journée.

Dans les systèmes disposant de données de circulation actualisées, il devient possible de réévaluer les temps de parcours et, si nécessaire, de recalculer certaines décisions.

Toutefois, la qualité du résultat dépend directement de la qualité des données disponibles.

Un algorithme peut être mathématiquement irréprochable et produire une estimation médiocre si les informations sur lesquelles il s'appuie sont incomplètes ou dépassées.

C'est l'une des grandes leçons de l'informatique appliquée : la performance d'un système dépend autant de la pertinence de son modèle que de la qualité des données qui l'alimentent.

L'intelligence artificielle est-elle indispensable ?

On associe souvent les applications modernes à l'intelligence artificielle. Pourtant, toutes les décisions automatisées ne nécessitent pas un modèle d'apprentissage automatique.

Un algorithme comme celui de Dijkstra ne repose pas sur un entraînement à partir de données. Il applique une méthode mathématique déterminée à un graphe.

Les techniques d'apprentissage automatique peuvent intervenir à un autre niveau, par exemple pour estimer le temps de parcours d'une route à partir d'observations historiques.

On peut ainsi distinguer deux tâches :

Prédire : combien de temps faudra-t-il probablement pour traverser une portion de route ?

Optimiser : compte tenu de ces estimations, quel itinéraire faut-il choisir ?

Ces deux tâches peuvent être associées, mais elles ne sont pas identiques.

La première relève notamment des statistiques et de l'apprentissage automatique. La seconde relève de l'algorithmique et de la recherche opérationnelle.

Un système de livraison peut donc combiner plusieurs disciplines sans qu'il soit nécessaire de qualifier l'ensemble de ses calculs d'« intelligence artificielle ».

Derrière chaque itinéraire, un choix humain

Les mathématiques peuvent calculer le chemin le plus court, la tournée la plus rapide ou la répartition qui minimise certains coûts.

Elles ne décident pas, à elles seules, de ce qu'une entreprise devrait considérer comme prioritaire.

Faut-il réduire le temps d'attente des clients ? Limiter les kilomètres parcourus ? Répartir équitablement les commandes entre les livreurs ? Préserver une marge pour absorber les imprévus ?

Ces objectifs peuvent entrer en concurrence.

Une tournée qui minimise la distance totale n'est pas forcément celle qui répartit le mieux la charge de travail. Un itinéraire qui semble optimal sur une carte peut également être peu adapté aux conditions réelles du terrain.

Construire un bon système ne consiste donc pas uniquement à choisir un algorithme performant. Il faut aussi définir les objectifs, comprendre les contraintes et accepter qu'aucun modèle ne représente parfaitement la réalité.

C'est précisément ce qui rend la recherche opérationnelle si intéressante : elle établit un dialogue permanent entre les mathématiques et le monde concret.

La prochaine fois qu'un livreur traversera Dakar pour remettre une commande, il ne suivra peut-être pas un itinéraire calculé par un programme sophistiqué. Son expérience et sa connaissance des quartiers peuvent aussi guider ses décisions.

Mais le problème qu'il résout, parfois intuitivement, est bien un problème mathématique.

Et derrière ce trajet apparemment banal se cachent certaines des questions les plus profondes de l'informatique : comment représenter le réel, comparer des millions de possibilités et prendre une bonne décision lorsque le temps manque ?