Optimiser des tournées

Qu’est-ce que l’optimisation de tournées ?

CarteMains (1)

voir une étude de cas ici

Une tournée est un ensemble d’interventions ou de passages à réaliser dans une journée, à des endroits et à des horaires différents, généralement prévu à l’avance. C’est la zone de chalandise ou la zone géographique d’influence (voir également ici)

De plus, plusieurs contraintes sont généralement à respecter : les contraintes des clients, des contraintes liées au transport, des aléas de la route, des horaires de travail des collaborateurs, compétences ou connaissances obligatoires pour assurer l’intervention, etc.

Une intervention peut-être une collecte, une livraison, une intervention ou une visite sur site (technique, commerciale, services à la personne, soins à domicile, portage de repas, services aux entreprises, collecte de déchets, …).

Entre chaque intervention il y a donc en toute logique, un déplacement.

L’optimisation de tournées consiste à créer un ordonnancement de l’enchaînement des rendez-vous ou des interventions qui, d’une part respectent les contraintes et d’autre part, assure un minimum de temps de conduite et réduit le nombre de kilomètres parcourus.

Pourquoi optimiser des tournées ?

Souvent les tournées ne sont pas planifiées. Généralement les rendez-vous sont pris, éventuellement un horaire ou créneau horaire défini avec le client, puis le rendez-vous est donné en fonction des intervenants présents.

Parfois, les rendez-vous sont planifiés dans un outil externe comme un agenda ou une feuille d’un classeur, mais les tournées sont généralement constituées par les personnes qui assurent les interventions.

Il en résulte une perte de temps, le temps de conduit entre les rendez-vous qui parfois dépasse les 30%.

Dans un contexte économique tendu où les marges sont faibles et la concurrence rude, disposer d’un outil qui permet de réduire ce temps improductif tout en réduisant le nombre de kilomètres parcourus, est devenu indispensable.

L’optimisation des tournées consiste donc à réduire au maximum les déplacements entre les interventions, aussi bien en temps qu’en distance, en proposant un ordonnancement des interventions différent, tout en respectant les contraintes associées (horaire, compétence, équipement spécifique pour assurer l’intervention, …).

Organiser les tournées à la main c’est courant mais particulièrement chronophage. Choisir les meilleures tournées, c’est à dire celles qui présentent le meilleur rapport temps/kilomètres, est impossible sans outil. D’après nos études, des tournées constituées manuellement induisent en moyenne environ 28% de temps de transport supplémentaire et près de 24% de kilomètres parcourus en plus. (étude menée auprès de nos clients « pilotes » d’après des tournées réellement réalisées, organisées manuellement – voir également le détail de l’étude ici)

L’optimisation de tournées : un « problème » mathématique

Le cas le plus simple est un ensemble d’interventions à réaliser par un seul intervenant, sans contrainte particulière. C’est à dire toutes les interventions peuvent être réalisées à n’importe quel moment de la journée.  Et ce par tous les intervenants et sans avoir besoin de compétences ou d’équipements particuliers.

Nombre de tournées avec 3 interventionsIl s’agit du problème du voyageur de commerce, très connu et étudié depuis fort longtemps par les mathématiciens.

Prenons un exemple très simple : Trois interventions doivent être faites par un seul intervenant, sans contrainte particulière. Combien de tournées différentes est-il possible de créer ?

Il est possible de démarrer la tournée avec n’importe des trois interventions, donc déjà trois choix. Une fois la première intervention réalisée, il en reste deux, avec deux choix. Et ceci est vrai pour les trois choix de départ.

Le nombre de tournées différentes qu’il est possible de créer est de 3 * 2 soit 6.

Mais en ajoutant une seule intervention, le nombre de tournées différentes est déjà de 4 * 3 * 2 soit 24.

Un problème exponentiel

Pour 5 intervention, c’est 5 x 4 x 3 x 2 = 120 tournées différentes théoriques possibles.

Pour 10 interventions le nombre est de 3.628.800. Et pour 11 interventions ? Près de 40.000.000 de tournées différentes !

C’est pour ces raisons qu’il est nécessaire d’avoir recours à un « solveur de tournées » doté d’un algorithme mathématique puissant si on souhaite analyser les choix possibles pour en distiller le meilleur. C’est l’algorithme mathématique utilisé par BioSolver qui est chargé d’analyser les possibilités en fonction de l’ensemble des contraintes. Cet algorithme a été spécifiquement développé en collaboration avec deux laboratoires de recherches qui dépendent du CNRS.

BIOSOLVER est labellisé par le Pôle de Compétitivité « Véhicule du Futur ». BIOSOLVER a été cofinancé par BPI France et les collectivités territoriales du département du Doubs et de la Région Bourgogne-Franche-Comté.

L’optimisation de tournées : un exemple concret

10 interventions sans contraintes

Voici un exemple concret. Le gros point bleu est le point de départ et d’arrivé. Les petits points bleus sont les interventions à réaliser. Il n’y a aucune contrainte horaire pour réaliser les interventions.

Une tournée simple, sans contraintes

En tout il y a dix interventions à réaliser. Le nombre théorique de tournées différentes est supérieur à 3.5 millions.

En observant l’image à droite, on est en mesure d’imaginer immédiatement la tournée qui semble « logique ».

On va bien évidemment démarrer la tournée avec l’un des petits points bleus les plus proches du point de départ. Une fois ce point réalisé, on va vers le suivant le plus proche.

L’ensemble ressemble à un cercle fermé, comme indiqué dans l’image suivante.

Tournée sans contrainteCette tournée vous semble évidente ?

Logique non ? Et pourtant vous venez de choisir parmi plus de 3.500.000 tournées différentes possible…

Mais les choses se compliquent dès lors qu’il y ait des contraintes horaires à respecter.

10pointsAvecContraintesXS

Une tournée simple avec des contraintes d’intervention

Prenons le même cas avec les mêmes interventions pour un seul intervenant.

Les points rouges sont à réaliser entre 7h00 et 9h00 en sachant qu’une des deux interventions représentées par les points rouges les plus proches du gros point bleu ne pourra pas être réalisée dans les temps impartis.

Quelle tournée construire dans ce cas ?

4-CarteJC-remplie-0pointsTournéeAvecContraintesRemplieAlaMain (XS)Lorsque l’on constitue les tournées manuellement et vue le nombre de tournées différentes qu’il est possible de créer, la solution la plus simple est de démarrer avec les interventions à réaliser entre 7h00 et 9h00. Ainsi on est sur que ces interventions seront faites dans les temps impartis.

Mais est-il possible de faire mieux ?

Le rôle de Biosolver est justement d’analyser les millions de possibilités différentes offertes afin de proposer la tournée la plus courte.

5-CarteJC-remplie-10pointsTournéeAvecContraintesParBiosolver (XS)Voici ce que Biosolver proposera en terme de solution, en respectant bien évidemment les contraintes, c’est à dire réaliser les interventions représentées par les points rouges entre 7h00 et 9h00.

Bien sur l’exemple est très simple et le résultat proposé par forcément spectaculaire. Mais cela permet de comprendre le concept de l’optimisation.

Prenons un cas un peu plus complexe.

CarteJC-Vide-51intervnetionsAvecContraintesXS

Une tournée complexe avec contraintes

Dans l’exemple suivant, il y a 51 interventions.

Avec cet exemple on considère que le nombre de tournées différentes possibles, dépasse le nombre d’atomes dans l’univers.

Quelles tournées feriez-vous ? Vous savez qu’il est impossible de réfléchir globalement en prenant en compte les 51 interventions. Aussi, la seule solution est de découper le territoire en quartiers ou secteurs.

Combien de tournées différentes créeriez-vous ? Quatre ? Cinq ? Peut-être six ?

CarteJC-vide-51interventionsDécoupéXSPeut-être vous vous sentez obligé à découper le territoire en quartiers ?

La plupart des organisations manuelles passent par le découpage territoriale car il est plus facile à gérer

Quelles seraient les tournées créées par Biosolver ?

Pour le savoir cliquez ici.

Convaincu que la création de tournées optimisées est complexe ? Si vous souhaitez une présentation et une démonstration contactez-nous.