L’abeille et le voyageur de commerce

Le « problème du voyageur de commerce » est un classique des mathématiques depuis sa formulation initiale en 1859. L’énoncé, des plus simples qui soit, tiens en une phrase : il s’agit de trouver le plus court chemin pour relier des points disposés au hasard, par exemple des villes réparties sur un territoire, et revenir ensuite à son point de départ. D’ou son nom de « problème du voyageur de commerce », puisque l’intérêt de celui ci est de visiter le plus de clients possible en limitant au maximum les temps de trajet et les consommations d’énergie associées. C’est aussi un classique pour les logisticiens, qui doivent optimiser des tournées de livraison ou d’enlèvement, en limitant les frais induits par les distances parcourues, et pour améliorer les délais de livraison.

Mais si l’énoncé est simple, aucun algorithme n’a encore pu être trouvé pour permettre une résolution rapide, quelque soit la disposition et la répartition des points à visiter, la difficulté augmentant très vite lorsque le nombre de point à visiter s’accroît. Les logiciels d’optimisation de tournée se contentent aujourd’hui soit d’approximations, soit comparent les différentes combinaisons possibles, ce qui peut prendre des heures de calculs si le nombre de point devient important.

Le plus surprenant, c’est que, d’après des études conduites par l’équipe de Nigel Raine, de l’institut des sciences du vivant de Royal Holloway, à l’université de Londres, les abeilles et les bourdons s’en sortent très bien pour résoudre ce problème, alors que leur cerveau, dont le volume est inférieur à celui d’une tête d’épingle, contient moins de un millions de neurones (par comparaison, le cerveau humain est constitué de plus de 100 milliards de neurones). Et le tout en temps réel, ce qui constitue une prouesse, mais aussi un avantage évident quand on doit butiner un maximum de fleurs en un temps minimum, et économiser l’énergie pour garder les réserves nécessaires au retour à la ruche.

Décidemment, les prouesses de la nature, et l’économie de moyens avec laquelle elle les réalise, n’ont pas fini de nous étonner et de nous inspirer. Logisticiens et voyageurs de commerce, vous avez sans doute encore bien des choses à apprendre des abeilles et des bourdons.