Remplacer tout ou partie du prototypage par la simulation numérique : hier un rêve, aujourd’hui une réalité à laquelle la branche de calcul scientifique d'Eurobios (ESCB) participe avec ses clients. Modélisation de matériaux nucléaires avec le CEA, simulation d’impacts de fluides sur les parois des cuves de méthaniers avec GazTransport & Technigaz (GTT) ou modélisation d'écoulements dans les pipe-lines avec l’Ente Nationale Idrocarburi (ENI Milan) voici quelques thématiques autour des écoulements multi-phasiques qui font l’objet de développements informatiques.
La planification de tournées de services d’envergure tels que la collecte des ordures ménagères est un problème complexe, jusqu’à récemment réalisé manuellement. Mais une nouvelle technologie commence à changer le processus de planification de ces tournées.
La disponibilité des réseaux de voirie sous forme numérique ainsi que de nouveaux algorithmes de traitement permettent maintenant de planifier ces tournées jusqu’au niveau des parcelles individuelles et de prévoir avec une grande précision les temps, distances et autres indicateurs de performance clés pour les tournées proposées. Les avantages essentiels d’une telle technologie concernent l’accroissement de l’efficacité des tournées – plus d’efficacité signifiant la réduction des temps et distances des trajets, ce qui réduit très directement les coûts environnementaux et d’exploitation des tournées. Les économies réalisées peuvent être importantes – 5 à 20% sont des chiffres réalistes. On constate également de nombreux autres avantages, tels que l’augmentation du service aux clients et collectivités, la création de conditions de travail équitables entre personnels, et la capacité à replanifier ou ajuster les tournées avec rapidité, etc..
Nous allons discuter ici des résultats de deux projets pilotes en Angleterre (Veolia et Biffa) qui ont mis en œuvre cette technologie pour planifier les tournées sur de vastes districts (120 tournées, 50 000 points de collecte). L’objectif de ces pilotes était d’évaluer l’adéquation de cette technologie innovante aux besoins de ces deux organisations. Nous évoquerons certains des challenges rencontrés au fil des étapes de ces projets (depuis la définition des besoins jusqu’à la mise en place des tournées) ainsi que la manière de les surmonter afin de bâtir des tournées entraînant à la fois des économies substantielles et satisfaisant les attentes subjectives des agents de planification. Ces expériences seront riches d’intérêt pour toute entreprise envisageant d’adopter cette puissante technologie d’avenir.
INTRODUCTION
Planifier une tournée implique de savoir déterminer qui, quoi, où, quand et comment. L’approche classique a toujours été de répondre au « qui, quoi et où » en traçant une carte et en assignant des secteurs aux équipes. Les « quand et comment »
étant souvent laissés à la responsabilité de l’équipe, et impliquant de devoir résoudre deux problèmes – dans quel ordre faut-il visiter les foyers et quelle route suivre entre deux lieux de collecte (autrement dit quel parcours effectuer).
Comment élaborer ces tournées ? Faut-il quadriller une carte entre secteurs uniformes (ou «blobs »). Si oui, comment alors faire en sorte que les durées travaillées soient égales, que les volumes déchargés soient optimaux, que les trajets soient efficaces, que la diversité des taux de participation soit bien prise en compte, que les tournées bi-hebdomadaires de recyclage ne soient pas perturbées et que les si nombreuses autres considérations soient toutes optimisées. Planifier des tournées est un exercice complexe. Le nombre de variables et de contraintes mises en jeu est étonnamment élevé. La complexité découle du grand nombre de tournées possibles, alors qu’il n’est pas envisageable de les faire valider toutes par les chauffeurs afin d’identifier la meilleure ! Ce caractère, combinatoire, du problème est dissuasif et de tout temps les agents de planification se sont fiés à leur expérience et leur intuition, en s’aidant d’expérimentations pratiques pour mettre au point des tournées qui marchent bien.
Une alternative est de ne pas construire vos tournées « à la main » mais d’exploiter un logiciel de type « planification de territoire » afin de découper automatiquement le district de collecte en tournées. Ces outils peuvent en effet vous aider à obtenir une tessellation de qualité, mais leur handicap fatal est qu’ils ont besoin de deux étapes pour réaliser une planification – en définissant tout d’abord le périmètre de la tournée sans se préoccuper des contraintes de sa réalisation.
Par conséquent ces outils butent sur les difficultés énumérées plus haut et ne peuvent garantir l’optimalité des tournées.
Ce livre blanc traite de cette nouvelle génération de systèmes de planification, basés sur les technologies de simulation et d’optimisation détaillées. De tels systèmes offrent une véritable optimisation holistique des tournées, avec le bénéfice d’économies substantielles. Nous présenterons tout d’abord cette technologie de nouvelle génération, puis nous discuterons des résultats obtenus en l’appliquant aux deux projets pilotes de Veolia et Biffa, en Angleterre.
Les illustrations ci-dessus présentent une zone typique sur laquelle on souhaite planifier une tournée, dans trois niveaux de détail successifs.
LA PLANIFICATION DE TOURNEES DE NOUVELLE GENERATION
Cette technologie de nouvelle génération pour la planification de tournée met en œuvre la simulation et l’optimisation par ordinateur. La simulation par ordinateur permet de simuler un véhicule sur son parcours de collecte, et calcule l’ensemble des indicateurs clés de performance (KPIs) tels que durée, distance, tonnage, nombre de voyages de déchargement, nombre de demi-tours et parcours inverses effectués, etc. Le tout avec une grande précision. Ceci est rendu possible à la fois par la disponibilité des réseaux routiers sous forme numérisée et par les dernières avancées en matière d’algorithmes numériques. Le modèle de simulation d’Eurobios prend en compte aussi bien les vitesses d’un véhicule sur différentes routes à différentes heures de la journée, que les interdictions de demi-tours, les rues barrées, les accélérations / décélérations, le temps de collecte, les virages serrés, le temps nécessaire aux demi-tours, les voyages de déchargement, etc, afin de calculer, avec un très haut niveau de précision, les indicateurs clés de performance.
Cette technologie a pour effet de permettre d’évaluer l’efficacité d’une tournée par pure simulation sur un ordinateur. On dispose ainsi d’un terrain d’expérimentation virtuel grâce auquel on peut multiplier les simulations !
Simuler est une chose, mais il faut maintenant à faire face à la difficulté réelle qu’est la détermination du meilleur ensemble de tournées. Et ceci est un problème impossible à traiter directement du point de vue mathématique. Même en ayant recours aux ordinateurs les plus puissants, le nombre de combinaisons de tournées possibles rend le calcul de l’optimum hors de portée. Par conséquent, nous mettons en œuvre des techniques propriétaires de pointe qui rendent l’ordinateur capable de rechercher intelligemment l’ensemble optimal de tournées.
Pendant la phase d’optimisation, nous simulons et calculons les KPIs pour des millions d’ensembles de tournées. Le moteur d’optimisation ne s’appuie que sur très peu d'hypothèses, mais recherche l’ensemble de tournées qui optimise les KPIs.
C’est ainsi que l’optimiseur trouvera souvent des tournées surprenantes ou peu intuitives qu’aucun planificateur humain n’aurait pu imaginer.
ANALYSE DES PROJETS PILOTES
Dans cette partie, nous exposons certains des enseignements tirés des pilotes réalisés en Angleterre. Les deux projets concernaient la planification complète des tournées de collecte et de recyclage de larges districts (environ 120 tournées, 50 000 points de collecte). Les tournées de collecte se déroulaient sur un cycle hebdomadaire tandis que celui des tournées de recyclage était de deux semaines.
A présent nous allons décrire brièvement chaque étape du processus de planification mis en œuvre.
Numérisation des tournées
Le point de départ pour cette planification de nouvelle génération consiste à représenter les tournées numériquement. Ceci implique de disposer d’une représentation digitale d’un sous-ensemble des tournées opérationnelles réelles, au niveau de détail décrivant la séquence des foyers collectés dans chaque rue.
Ceci est nécessaire afin de pouvoir fournir une référence de comparaison ainsi qu’une possibilité de calibrage de l’outil. Lorsque les tournées ne sont pas disponibles en format numérique (en Angleterre par exemple, les tournées sont fréquemment stockées dans des feuilles de calcul listant le nom des rues concernées par la collecte), il faut consacrer du temps à les importer dans le logiciel retenu à cet effet.
Etalonnage
L’étalonnage consiste à mettre en œuvre le modèle de simulation sur ordinateur afin de calculer les KPIs pour un sous-ensemble de tournées numérisées et à les comparer avec ceux observés dans la réalité (par exemple les données GPS). On en ajuste ensuite les différents paramètres pour optimiser la précision des prévisions issues des simulations.
Spécification des contraintes
Beaucoup de contraintes peuvent être intégrées dans les calculs que cette nouvelle technologie de planification peut effectuer. L’agent de planification peut désigner les routes où la collecte ne doit être effectuée d’un seul coté, celles dont l’accès est très étroit, ou encore celles avec des zones d’écoles à éviter à certaines heures de la journée.
Optimisation
Une fois atteinte l’étape d’optimisation, nous sommes prêts à laisser l’ordinateur rechercher l’ensemble optimal de tournées. Les contraintes ont été définies au préalable mais nous devons indiquer à la machine à quoi ressemble un jeu optimal de tournées ! Ceci peut s’avérer plus complexe qu’on ne pourrait le penser. En effet nous souhaitons obtenir des tournées pouvant être effectuées dans les temps et distances les plus courts mais d’autres considérations compliquent la situation, telles que des temps de travail équitables, les pénalités pour non-respect des contraintes fixées, la géométrie des tournées, etc. Avec pour conséquence que le processus d’optimisation nécessitera, afin de produire des résultats satisfaisant les agents de planification, de répéter l’optimisation et l’ajustement des divers paramètres qui gouvernent le compromis entre les différents objectifs recherchés.
Validation en situation réelle
Les tournées engendrées par notre optimiseur pourront souvent apparaître aux planificateurs humains peu intuitives, sinon irréalisables. Nous avons donc effectué des exercices de validation consistant à exécuter ces tournées en comparant les temps et distances prévues par le modèle avec la réalité. Alors que ces prévisions se révélaient être extrêmement précises, le chauffeur se gratta la tête avec perplexité, examina sa carte et déclara « ce système marche vraiment.. ».
Implémentation
Le premier stade de l’implémentation consiste à « vendre » le nouveau plan de tournées à la municipalité concernée. La pression politique peut s’avérer un vrai obstacle à la mise en place. Les changements de tournées, même parfaitement réalisées, ont le potentiel, au moins au début, de faire grimper le compteur des réclamations clients.
Une autre préoccupation se manifeste : comment les avantages du système sont-ils partagés ? La mise en place de tournées plus efficaces entraîne typiquement la réduction des coûts de personnel, de carburant et d’entretien. Au final, on peut constater une résistance des syndicats ouvriers, car des tournées plus efficaces signifient souvent qu’un camion peut être enlevé de la flotte, ou que le volume d’heures supplémentaires peut être réduit.
Mais la prise en compte automatisée des critères de sécurité (personnel n’ayant pas à faire la collecte sur les deux cotés d’une route à fort trafic, ou évitement des zones d’écoles aux heures où les enfants sont déposés ou repris) et l’équilibrage des tournées en heures travaillées ainsi que les résultats mêmes de l’optimisation peuvent permettre de surmonter certains de ces obstacles.
Une fois ces difficultés de mise en place surmontées, l’étape suivante est de prévenir les clients de la modification du calendrier de collecte. Puisque les tournées sont désormais complètement numérisées jusqu’au niveau du foyer, de nouveaux mécanismes de notification sont maintenant disponibles, depuis l’envoi à chaque foyer de courriers personnalisés, jusqu’à la publication d’information sur site web.
L’expérience de ces pilotes a montré que cette nouvelle technologie créait de nouvelles opportunités pour ces activités et stimulait leur management.
RESULTATS ET CONCLUSIONS
Ces pilotes ont eu pour résultat un accroissement d’efficacité compris entre 5 et 20%, en même temps qu’un meilleur équilibrage des heures travaillées et la prise en compte exhaustive des facteurs de sécurité souhaités.
En outre, les magnifiques cartes et rapports numérisés, incorporant les survols proposés par Google Earth, ont amené certains bénéfices très pratiques : la mise en place de ces nouvelles tournées a pu s’effectuer de manière beaucoup plus souple (en diminuant l’exigence de disposer de conducteurs expérimentés) que dans le passé.
Nous avons présenté ici un bref aperçu de cette nouvelle technologie de planification de tournées et l’expérimentation réalisée avec de grands acteurs dans ce domaine en Angleterre.
La production de la nouvelle génération du logiciel de planification « Eurobios Waste optimiser » est le fruit de cette expérimentation. Plusieurs grandes entreprises de collecte et municipalités en Angleterre et en France utilisent désormais ce logiciel ou ont mis en place des tournées élaborées par lui, et bénéficient activement des avantages qu’il leur procure.
