Les objectifs en optimisation de tournées : bénéfices de l’approche lexicographique
- 16 décembre 2020
- 4 mins
L’optimisation de tournées consiste à trouver la meilleure solution pour visiter un ensemble de points en respectant un ensemble de contraintes. Reste à définir la notion de “meilleure” solution… En effet, qu’est-ce qui fait qu’une tournée est meilleure qu’une autre ? Selon les domaines, on pourra par exemple répondre “celle qui a le moins de kilomètres” ou bien “celle qui a le moins de retard”, voire “un peu des deux”. Et en pratique, la réponse est souvent complexe à obtenir car elle implique d’être au préalable très clair sur ses propres objectifs business, et de pouvoir les modéliser dans le formalisme de l’algorithme.
Petit tour d’horizon de ce sujet plus complexe qu’il n’y parait, et qui est au final déterminant dans l’adoption d’une solution d’optimisation sur le terrain.
Prérequis : le rôle des objectifs d'optimisation en optimisation de tournées
Un problème d’optimisation de tournées se compose d’un ensemble d’éléments primordiaux qui, attaqués par un algorithme de résolution, permettent d’obtenir une solution de tournées optimisées. Ces éléments sont :
- les objectifs d’optimisation (par exemple : “minimiser le nombre de kilomètres parcourus”),
- les données du problème (par exemple : la localisation des points à visiter, les données de trafic prédictifs, etc),
- les contraintes du problème (par exemple : les horaires de travail des chauffeurs)
Les méthodes classiques : paramétrer un objectif d’optimisation unique ou agrégé
Dans la plupart des méthodes et des outils, l’utilisateur définit un seul objectif à l’algorithme. Cette approche est, de loin, la plus facile à mettre en oeuvre d’un point de vue algorithmique. Dans ce mode, il faut donc choisir un indicateur qui doit refléter au mieux les priorités business de l’entreprise. Cette approche a le mérite d’être simple mais rencontre rapidement ses limites quand on l’applique à des problématiques réelles.
En effet, les problèmes d’optimisation de tournées sont toujours multicritères. Il n’est que très rarement possible de choisir un seul indicateur. Pour pallier à cette limite, les outils d’optimisation ont souvent recours à des objectifs “agrégés”, qui vont mutualiser plusieurs indicateurs en un seul grâce à une formule mathématique. Le plus utilisé (sinon le seul) est la moyenne pondérée : chaque indicateur va se voir attribuer un poids, et l’indicateur optimisé sera la somme pondérée de ces indicateurs.
Problème là encore : comment définir les pondérations pour qu’elles reflètent réellement les objectifs métier ? La tâche est complexe ! Pour simplifier le problème, la plupart des logiciels du marché ignorent purement et simplement la plupart des objectifs, pour n’en proposer que quelques-uns (les classiques). En tentant de simplifier leurs approches, ils les rendent finalement simplistes ou difficiles à exploiter.
Chez Kardinal, nous pensons que nos algorithmes doivent résoudre les problèmes du terrain, sinon rien. Ainsi, non seulement nous pouvons gérer simultanément l’ensemble des objectifs métier de nos clients, mais l’utilisateur peut aussi aisément paramétrer l’optimisation pour qu’elle reflète ses objectifs métier.
L’optimisation lexicographique : prioriser plutôt que pondérer pour mieux refléter les objectifs business de l’entreprise
L’optimisation Kardinal est basée sur un algorithme d’optimisation multicritère dit “lexicographique”. Cela signifie que les objectifs ne sont pas agrégés en un indicateur unique, mais priorisés, ordonnés, du plus important au moins important. Ainsi, une solution sera jugée meilleure qu’une autre si elle est meilleure sur l’objectif de priorité 1, peu importe les valeurs des autres objectifs moins prioritaires. Ce principe demeure pour l’ensemble des objectifs.
Prenons un exemple concret pour démontrer ce que cette approche permet, par rapport à la pondération :
Imaginons donc une problématique de livraison de colis du dernier kilomètre. Certains clients ont payé (cher) pour une livraison “Premium” en 24h dans un créneau précis, d’autres (moins cher) pour une livraison “Silver” en 24h, d’autres encore pour une livraison “Standard” en 48h qui est optionnelle. Une partie de la flotte est constituée de prestataires qui doivent essayer de générer un chiffre d’affaire de 250€ si on les utilise, mais on préfère s’appuyer préférentiellement sur les salariés. Bien sûr, on cherche à limiter au maximum les kilomètres parcourus, mais on cherche d’abord à utiliser le moins de véhicules possibles pour réaliser les livraisons prioritaires (dans la limite de la flotte disponible).
Les objectifs d’optimisation qu’on peut identifier ici sont les suivants :
- Maximiser les livraisons “Premium” planifiées
- Maximiser les livraisons “Silver” planifiées
- Maximiser les livraisons “Standard” optionnelles planifiées
- Minimiser le nombre de tournées de salariés
- Minimiser le nombre de tournées de prestataires
- Minimiser la “non-rentabilité” des prestataires
- Minimiser les kilomètres parcourus
- Minimiser les retards sur les livraisons “Premium”
Ainsi, on a 8 objectifs d’optimisation. Clairement, trouver des pondérations capables de refléter exactement les priorités du business (sans compter qu’il faut maximiser certains objectifs, et en minimiser d’autres) est particulièrement complexe. En revanche, prioriser est très simple, et les implications d’un choix sont immédiatement compréhensibles pour le décideur. Ainsi, imaginons la priorisation suivante :
- Maximiser les livraisons “Premium” planifiées
- Minimiser les retards sur les livraisons “Premium”
- Maximiser les livraisons “Silver” planifiées
- Minimiser le nombre de tournées de prestataires
- Minimiser le nombre de tournées de salariés
- Maximiser les livraisons “Standard” optionnelles planifiées
- Minimiser la “non rentabilité” des prestataires
- Minimiser les kilomètres parcourus
Dans ce paramétrage, le service aux clients “Premium” passe avant tout. On préfère même livrer à l’heure un client “Premium” plutôt que de livrer un client “Silver” tout court. Les livraisons “Standard” sont positionnées après la minimisation du nombre de tournées, ce qui modélise le fait que ce sont des livraisons optionnelles : on n’utilisera pas des véhicules en plus pour faire ces livraisons. Finalement, les objectifs 1 à 7 permettent d’optimiser la répartition du travail entre l’ensemble des tournées, et c’est seulement une fois que le dispatch est optimal que le 8ème objectif va chercher à optimiser les parcours eux-mêmes.
Cette approche a l’avantage de la lisibilité : on sait ce que l’algorithme va faire, et on sait quels impacts auront les ajustements. Ainsi, si on juge que livrer (à l’heure) un client “Premium” plutôt que livrer (tout court) un client “Silver” est trop radical, il suffit d’intervertir les objectifs 2 et 3. Si on juge le retard complètement secondaire par rapport à la performance économique, on peut passer l’objectif 2 après l’objectif 5. Et ainsi de suite.
Avec cette approche, la phase de paramétrage complexe de l’optimisation devient une formalité et l’utilisateur n’a pas affaire à une boîte noire. Techniquement, la difficulté d’un problème d’optimisation multicritère lexicographique est beaucoup plus élevée que les approches classiques d’optimisation, mais elles sont selon nous l’une des clés de la mise en application sur le terrain de solutions d’optimisation pertinentes.
L'Auteur
Cédric Hervet est docteur en Mathématiques Appliquées et co-fondateur de Kardinal. Depuis plus de 10 ans, il étudie et conçoit des systèmes d’Intelligence Artificielle pour des applications industrielles dans les secteurs des télécommunications, du marketing digital et du transport.
Sa double compétence en statistiques/Machine Learning ainsi qu’en algorithmie/Recherche Opérationnelle lui permet d’articuler ces deux grands ensembles de techniques pour concevoir les systèmes intelligents de demain.
