+33 1 85 76 20 29
contact@citodi.fr

La Recherche Opérationnelle au service de la logistique

La Recherche Opérationnelle : la Science du mieux avec moins

L’essor de l’informatique et des mathématiques appliquées ont permis la modélisation et la résolution de problèmes d’optimisation complexes. Cette discipline, la Recherche Opérationnelle, a rencontré de nombreux succès dans l’industrie et le transport en exploitant intelligemment les capacités de calculs d’ordinateurs sans cesse plus puissants pour résoudre des problèmes combinatoires inaccessibles à l’esprit humain

Ainsi, l’ordonnancement des tâches dans une usine, la gestion d’actifs financiers, la construction de plannings de personnels devenaient des problèmes qu’une approche rationnelle, scientifique, permettrait de résoudre. Et parmi l’ensemble des problèmes d’optimisation combinatoire qui ont suscité des efforts de recherche on trouve l’optimisation de tournées de livraisons.

L’optimisation de tournées : un vieux problème, toujours difficile à résoudre

L’un des problèmes fondamentaux lié à l’optimisation de tournées est le fameux « Problème du Voyageur de Commerce », dont on trouve la première description en 1832, qui consiste à trouver la façon de visiter N points (par exemple : les clients qu’un commercial souhaite rencontrer) qui minimise la distance parcourue par ledit commercial.

Formellement cela revient à identifier un cycle hamiltonien de moindre coût dans un graphe complet muni de pondération sur les arcs. Pour se rendre compte de l’aspect fortement combinatoire de ce problème, on peut calculer le nombre de tournées possibles en fonction du nombre de points à visiter.

Pour 3 points, il y a 6 tournées possibles.
Pour 6 points, il y en a 720.
Pour 10, il y en a déjà 3 628 800.
Pour 43 points, il y en a autant que d’atomes qui constituent la Terre (1050 environ),
Et pour 60 points, il y en a autant que d’atomes dans l’Univers (1080 environ).

Cette explosion combinatoire rend très rapidement impossible toute exploration exhaustive des solutions : c’est là qu’interviennent les mathématiques pour imaginer des algorithmes capables de résoudre en quelques minutes ce qui prendrait des siècles à un ordinateur, même très puissant, qui essaierait toutes les solutions afin de trouver la meilleure.

Les tournées de véhicules : des Mathématiques au Terrain

Pendant des décennies, les chercheurs ont travaillé à résoudre des versions plus complexes et plus proches de la réalité que la version assez théorique du Voyageur de Commerce : tournées de plusieurs véhicules, avec des capacités d’emport limitées, avec des créneaux de temps à respecter, avec des départs de plusieurs dépôts, etc.

Pour chacune de ces variantes, des algorithmes exacts (lents mais capables de fournir la meilleure solution au problème) ainsi que des algorithmes approchés (rapides pour fournir de bonnes solutions, sans garantie d’optimalité) ont été conçus.

Ces progrès théoriques et techniques ont pu être transférés vers les professionnels du transport et de nombreuses solutions logicielles intégrant de l’optimisation de tournées ont été conçues pour les y aider, contribuant à l’amélioration de la performance de la Supply Chain.

Le dernier kilomètre et la barrière du temps réel

Pour autant, il est resté jusqu’à peu un domaine pour lequel les algorithmes et les solutions existantes atteignaient leurs limites : le dernier kilomètre et les problématiques temps réel qui y sont reliées.

En effet, les professionnels du dernier kilomètre savent que les imprévus rendent très difficiles l’utilisation d’optimisation de tournées de livraisons.

Ainsi, il faut pouvoir adapter les tournées au contexte, et cela suppose qu’on remplisse les deux conditions suivantes :

1 ) La capacité à collecter l’information depuis le terrain pour adapter la tournée, et la capacité à informer le terrain des changements éventuels apportés à leurs itinéraires.
2 ) La capacité à recalculer de façon quasi instantanée les tournées pour tenir compte des nouvelles données reçues.

L’émergence depuis plusieurs années des smartphones, des applications et de la géolocalisation a permis de résoudre le premier point. Chez Citodi, nous résolvons le second.

> Voir l’approche CITODI