Boston a économisé 5 millions de dollars en aiguillant les autobus scolaires à l’aide d’un algorithme

Avec 25 000 élèves et les coûts de transport les plus élevés du pays, le Boston Public School District avait besoin d’un meilleur moyen pour amener les enfants en classe.

L’autobus scolaire jaune est demeuré en grande partie inchangé depuis ses débuts en 1939. Mais si les autobus se ressemblent, leurs trajets sont devenus infiniment plus complexes au cours des 80 dernières années, à mesure que le nombre d’élèves, d’écoles et de réseaux routiers augmentait et changeait.

Dessiner des itinéraires d’autobus pour les écoles publiques de Boston comporte des défis propres à la ville. Le BPS permet aux parents de choisir l’école de leur enfant sur une liste d’une dizaine d’options, afin de réduire les inégalités qui pourraient résulter de l’isolement des élèves dans leur quartier. Bien que cela représente un plus grand choix que la plupart des villes, les itinéraires d’autobus qui en résultent peuvent être sinueux et compliqués.

Le fait que BPS offre plus de services d’autobus que la plupart des autres districts ne fait qu’aggraver ce problème. Tous les élèves du primaire qui fréquentent des écoles situées à plus d’un mille (1km6) de chez eux se voient offrir un service d’autobus jaune vers l’une des 220 écoles, et bon nombre d’entre eux vivent beaucoup plus loin que cela. Certaines écoles attirent des élèves de plus de 20 codes postaux différents. Chacune de ces écoles avait également des heures de début des cours différentes, entre 7 h 15 et 9 h 30, de sorte que les autobus devaient se rendre dans plusieurs écoles pour aller les chercher et les déposer.

En 2017, le district fait face à de sérieux défis. Par élève, le BPS avait les coûts de transport les plus élevés du pays, soit environ 2 000 dollars par élève et par an, ce qui représente 10 % du budget du district. Les écoles ont dû faire face à la hausse des coûts chaque année, malgré la baisse de fréquentation. Le taux de ponctualité de leurs autobus était également bien inférieur à celui des autres grands districts.

En l’absence d’un fournisseur clair vers qui se tourner pour résoudre ce problème, BPS a plutôt fait appel à des experts, organisant un concours dans le cadre duquel les chercheurs ont pu expérimenter des ensembles de données anonymes du BPS pour créer des itinéraires efficaces et des heures de début optimales pour chaque école.

« Pour dire les choses simplement, nous voulions une solution qui fonctionne « , a déclaré Will Eger, le directeur principal des projets stratégiques de BPS. « Il y a beaucoup de bizarreries dans cette situation de transport, et nous voulions quelque chose qui pourrait régler la grande majorité de ces problèmes tout en étant très efficace, quelque chose qui pourrait fonctionner du jour au lendemain au moins. »

Ces bizarreries représentent des millions de variables de décision qui influent sur toute solution, y compris les différentes largeurs de route, les différentes infrastructures d’autobus (par exemple, la présence d’élévateurs pour fauteuils roulants ou de sièges de sécurité pour enfants), les élèves qui ont besoin du même conducteur d’autobus chaque année, les élèves qui ont un moniteur et ceux qui se sont disputés et qui doivent donc être dans différents autobus. Il comprend également les quelque 5 000 élèves qui ont des besoins spéciaux et qui doivent aller et venir de porte en porte (parfois dans des écoles non-BPS, car la ville offre un service d’autobus jaune aux élèves qui fréquentent des écoles privées et à charte à Boston, ainsi que des établissements d’enseignement spécialisé à l’extérieur de la ville).

« Quand vos enfants sont affectés négativement, il est difficile d’avoir une vue d’ensemble. »

Considérer toutes ces possibilités crée un  » nombre de solutions si grand qu’on ne peut même pas l’énumérer « , a déclaré Arthur Delarue, un candidat au doctorat qui a travaillé avec l’équipe du MIT Operations Research Center dont l’algorithme a remporté le concours. L’équipe a passé des centaines d’heures à trouver une solution à ce que Delarue a appelé un défi « audacieux et inhabituel ».

Leur solution a remplacé ce qui était auparavant un processus incroyablement laborieux, qui prenait des milliers d’heures à dix routeurs du système scolaire pour créer des itinéraires personnalisés pour chaque enfant et chaque école. Ces employés travaillent toujours avec BPS, en suivant les itinéraires qui ont du mal à respecter les délais et en gérant le guidage des conducteurs (Google Maps ne suffit pas puisqu’il est conçu pour les voitures et que les bus de 70 passagers ne peuvent pas, par exemple, faire facilement des demi-tours). Mais maintenant, l’algorithme MIT achemine l’ensemble du système en une seule fois, fournissant une base pour les routeurs humains à modifier.

« Le travail des gestionnaires de routes dans la communication avec les parties prenantes telles que les conducteurs, les directeurs d’école, les parents et les élèves est inestimable et ne peut être remplacé « , a dit Mme Delarue. « Mais l’ordre dans lequel les arrêts doivent être visités et la façon dont cet itinéraire est conçu ne peuvent être résolus efficacement par les humains. C’est là que nous ajoutons de la valeur. »

Sébastien Martin, un autre candidat au doctorat au MIT qui a travaillé sur la solution, a déclaré que les dilemmes liés au tracé des lignes d’autobus scolaires ont été étudiés depuis les années 1960, et de nombreuses solutions ont été proposées. « Chaque district scolaire a des besoins si différents qu’il est difficile de trouver une solution qui fonctionne parfaitement partout, dit-il. « Le problème est si difficile à résoudre que même les ordinateurs les plus puissants ne peuvent trouver une solution parfaite pour un district de la taille de Boston. Il y aura toujours des compromis. »

Mais même avec des compromis, l’utilisation d’un algorithme, que la ville a testé pour la première fois dans l’année scolaire 2017-2018, a créé des résultats spectaculaires. En 30 minutes, l’algorithme a créé une carte routière au niveau du système qui était 20 % plus efficace que celles faites à la main. Plus l’algorithme fonctionne longtemps, meilleure est la solution qu’il produit, jusqu’à ce qu’il ne puisse être amélioré. L’exécution de l’algorithme à l’été 2017 a permis au système d’éliminer 50 autobus, soit une baisse de 8 p. 100 du parc qui était le plus important que Boston ait connu en une seule année. Les autobus ont parcouru 1 million de kilomètres de moins cette année-là et ont réduit les émissions de dioxyde de carbone de 20 000 livres par jour. Le district a réinvesti les 5 millions de dollars économisés dans des initiatives scolaires.

« Incroyablement, cela s’est fait sans faire de trajets en bus ou sans marcher jusqu’aux arrêts plus longtemps, » dit Eger. « Nous avons maintenant des temps de marche plus courts pour les jeunes étudiants et ceux des quartiers dangereux, et nous avons encore réduit le nombre total d’arrêts. »

Une grande partie du succès de l’algorithme vient du fait qu’il adopte une approche au niveau du système, qu’il achemine plutôt indépendamment les écoles individuelles et qu’il relie ensuite ces routes entre elles. Au lieu de cela, l’algorithme assigne les élèves aux arrêts, met les arrêts afin qu’aucun élève ne roule plus d’une heure, puis adopte une approche de routage multi-écoles. La meilleure solution n’est donc pas celle qui utilise le moins d’autobus pour chaque école, mais celle qui recycle le plus efficacement les autobus sur les trajets menant à plusieurs écoles – et la solution utilise une programmation en nombres entiers souple qui permet au district de s’adapter aux politiques changeantes.

Maintenant dans sa troisième année de fonctionnement, Eger dit que BPS exécute l’algorithme pendant l’été pour créer un horaire principal, puis fait des modifications à la main tout au long de l’année, bien qu’ils essaient d’intégrer les deux systèmes afin que des changements puissent être faits par l’algorithme pendant toute l’année. Mais, selon lui, le potentiel le plus puissant de ce défi était un autre algorithme, celui qui permet d’avoir un  » aperçu sans précédent  » des implications des changements de politiques, comme l’heure de la rentrée scolaire.

« C’était vraiment une révélation pour nous », a dit Eger. « Nous pouvons maintenant comprendre les effets sur les coûts et l’équité, ainsi que le nombre d’étudiants qui pourraient être touchés par un changement de politique. »

Mais ce n’est pas parce que le district a été en mesure d’énumérer clairement les effets des changements de politique qu’ils ont été populaires. En décembre 2017, sur la base des recommandations de l’algorithme, le Boston School Committee a approuvé, pour la première fois en 30 ans, des changements dans les heures de rentrée scolaire. Ces changements auraient touché 85% des écoles.

Cette décision s’appuyait sur plusieurs considérations, y compris des recherches qui ont démontré que le fait de commencer l’école secondaire avant 8 heures du matin a des effets néfastes sur la capacité d’apprentissage des adolescents. La recherche du MIT a également montré que Boston était inéquitable – alors que la plupart des parents préfèrent des heures de début entre 8h00 et 8h30 du matin, seulement 10% des élèves blancs de Boston commencent avant 8h00 du matin, contre 30% des élèves noirs. Les étudiants à revenu élevé commencent généralement plus tard, aux moments les plus souhaitables.

L’équipe s’est donc efforcée d’échanger les heures de début des écoles secondaires avec les écoles primaires du district et d’optimiser les heures de début en fonction de la faisabilité du parcours, de la santé des adolescents, des préférences des parents et de l’équité. Leur algorithme d’heure de début d’école a exploré les compromis entre les différentes heures de début et a trouvé un point d’équilibre entre toutes les considérations. S’il avait été déployé, il aurait fait passer de 74 % à seulement 6 % le nombre d’adolescents qui commencent tôt leurs études secondaires.

Mais il n’a pas été déployé. Après son dévoilement, les parents se sont vivement opposés à la proposition. Moins d’un mois plus tard, le district a abrogé les heures proposées pour la rentrée scolaire. Comme l’a souligné Dimitris Bertsimas, professeur à la tête de l’équipe du MIT, dans une présentation sur la solution, ceux qui étaient en faveur du statu quo avaient le plus à perdre. « Quand vos enfants sont affectés négativement, il est difficile d’avoir une vue d’ensemble « , dit-il.

Le MIT s’est finalement associé au Boston Globe en 2018 pour montrer comment l’algorithme de l’heure pourrait modifier les heures de début dans chaque école, mais aucun changement radical n’a encore été apporté. Malgré cela, Eger a déclaré que le projet a été une source d’inspiration pour le quartier et la ville dans son ensemble.

« C’est un exemple positif pour montrer comment nous pouvons utiliser une partie de l’incroyable potentiel de recherche que Boston a l’offre « , a-t-il déclaré. « De nombreux districts scolaires ont des problèmes opérationnels de ce genre, et relever ces défis complexes n’est pas notre domaine d’expertise. Nous devrions compter sur des experts pour cela, et nous concentrer sur le travail que nous faisons le mieux. »

Via Route 50,

Je trouve toujours amusant de voir à quel point on parle de toutes parts des dernières start-up B2C (orientées consommateurs) souvent centrées sur le divertissement ou le dernier moyen de remplir le temps, mais trop peu du travail utile et innovant, qui pourtant bénéficie au même public.
Dans ce cas-ci, évidemment les sujets liés aux collectivités et à l’organisation des villes suscite forcément des réactions, un brin réfractaires au changement, mais pourtant, nous voyons bien que ces mesures nouvelles peuvent être un bien dans une mesure bien plus importante…

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.