Une nouvelle solution à un problème d’optimisation combinatoire dans les systèmes de partage de vélos

Une nouvelle solution à un problème d'optimisation combinatoire dans les systèmes de partage de vélos

Figure 1 : Exemples de violations des contraintes d’approvisionnement et de chargement. En (a), le véhicule peut satisfaire la contrainte de chargement donnée car il peut prendre les trois vélos en excès dans le port i. Cependant, en (b), le véhicule viole la contrainte de chargement car il n’a de place que pour l’un des trois vélos excédentaires au port. De même, en (c), le véhicule viole la contrainte d’approvisionnement car il ne peut fournir qu’un vélo au port i, qui en a besoin de trois. Dans la stratégie proposée, ces contraintes sont traitées comme des contraintes souples dans la formulation du problème. Cette approche permet une recherche d’algorithme pour les espaces de solutions réalisables et infaisables et accélère la recherche de solutions quasi optimales ou optimales. Crédit : Tohru Ikeguchi de l’Université des sciences de Tokyo

Les systèmes de partage de vélos sont devenus une option attrayante pour alléger le trafic dans les villes encombrées. Cependant, rééquilibrer le nombre de vélos à chaque port au fil du temps est essentiel, et trouver les chemins de routage optimaux pour les véhicules en charge du rééquilibrage constitue un problème d’optimisation combinatoire. Désormais, les scientifiques proposent un algorithme innovant capable de trouver plus rapidement des solutions quasi optimales, même pour un grand nombre de ports, ouvrant la voie à des systèmes de partage de vélos plus efficaces.

Les embouteillages se sont aggravés depuis les années 1950 dans les grandes villes grâce au nombre exorbitant de voitures vendues chaque année. Malheureusement, le prix figuré attaché au trafic excessif comprend des émissions de dioxyde de carbone plus élevées, une perte de temps plus collective et des problèmes de santé exacerbés. De nombreuses municipalités se sont attaquées au problème de la circulation en mettant en place des systèmes de vélos en libre-service, dans lesquels les gens peuvent emprunter des vélos dans des ports stratégiquement placés et se déplacer où ils veulent, à condition qu’ils ramènent finalement les vélos dans un port, mais pas nécessairement celui d’où le vélo a été obtenu à l’origine.

Comme on peut le remarquer immédiatement ou non, cette dernière autorisation crée en elle-même un nouveau problème. Chaque fois que quelqu’un emprunte un vélo et ne fait pas l’aller-retour avec, un vélo supplémentaire survient au port de destination tout comme il y a une perte d’un vélo au port d’origine. Au fil du temps, la répartition des vélos entre les ports devient déséquilibrée, provoquant à la fois une accumulation excessive de vélos dans certains ports et une pénurie de vélos dans d’autres. Ce problème est généralement résolu par l’envoi périodique d’une flotte de véhicules capables de transporter plusieurs vélos afin de restaurer les ports à leur nombre « idéal » de vélos.

De nombreuses recherches ont été consacrées au problème de rééquilibrage des vélos à l’aide d’une flotte de véhicules. Trouver les chemins de routage optimaux pour les véhicules est en soi un problème mathématique très complexe dans le domaine de l’optimisation combinatoire. Il faut s’assurer que les algorithmes d’optimisation utilisés peuvent atteindre une solution suffisamment bonne dans un délai raisonnable pour un nombre réaliste de ports et de véhicules. Cependant, de nombreuses méthodes ne parviennent pas à trouver des solutions réalisables lorsque plusieurs contraintes sont prises en compte simultanément, telles que les contraintes de temps, de capacité et de chargement/déchargement pour les véhicules (Figure 1).

Mais et si nous laissions la stratégie d’optimisation changer un peu les stratégies pour tirer le meilleur parti des situations difficiles ? Dans une étude récente publiée dans le MDPI Sciences appliquées, une équipe de scientifiques a suggéré une tournure innovante au problème de routage des systèmes de partage de vélos utilisant ce concept. Dirigée par le professeur Tohru Ikeguchi de l’Université des sciences de Tokyo, l’équipe composée de Ph.D. L’étudiant Honami Tsushima de l’Université des sciences de Tokyo et le professeur agrégé Takafumi Matsuura du Nippon Institute of Technology, Japon, ont proposé une nouvelle formulation du problème de routage dans laquelle les contraintes imposées sur les routages peuvent être violées. Cela a permis d’utiliser l’algorithme d’optimisation pour explorer ce que l’on appelle l’espace des « solutions infaisables ». Le professeur Ikeguchi explique leur raisonnement : « Dans la vraie vie, si un travail peut être terminé en quelques minutes grâce aux heures supplémentaires, nous travaillerons au-delà de la limite de temps. De même, si nous ne transportons que quatre vélos et devons en fournir cinq, nous fournissent toujours les quatre que nous avons. »

Suivant cette ligne de pensée, les chercheurs ont formulé la variante « contraintes douces » du problème de routage dans le rééquilibrage des vélos. En utilisant cette approche, au lieu d’exclure purement et simplement les solutions qui violent les contraintes, celles-ci peuvent être considérées comme des chemins valides qui entraînent des pénalités ajustées dynamiquement et prises en compte lors de l’évaluation des routages possibles. Cette approche a permis à l’équipe de concevoir un algorithme qui peut utiliser l’espace des solutions infaisables pour accélérer la recherche de solutions optimales ou quasi optimales.

Les chercheurs ont évalué les performances de leur méthode grâce à des expériences numériques avec des problèmes de référence comprenant jusqu’à 50 ports et trois véhicules. Les résultats montrent que leur stratégie peut trouver des solutions optimales ou quasi optimales dans tous les cas, et que l’algorithme peut rechercher efficacement les espaces de solutions réalisables et infaisables. Cela préfigure un avenir meilleur pour les habitants des villes à trafic congestionné, dans lesquelles les systèmes de partage de vélos pourraient devenir une solution attrayante. Comme le remarque le professeur Ikeguchi, « Il est probable que les systèmes de partage de vélos se répandront dans le monde entier à l’avenir, et nous pensons que le problème de routage dans le rééquilibrage des vélos est un problème important à résoudre dans les sociétés modernes. »


Lyft suspend les vélos électriques après un incendie de batterie


Plus d’information:
Honami Tsushima et al, Stratégie d’exploration d’espaces de solutions faisables et infaisables pour résoudre un problème de routage du système de partage de vélos à plusieurs véhicules, Sciences appliquées (2021). DOI : 10.3390/app11167749

Fourni par l’Université des sciences de Tokyo

Citation: Une nouvelle solution à un problème d’optimisation combinatoire dans les systèmes de partage de vélos (2021, 28 octobre) récupéré le 28 octobre 2021 à partir de https://techxplore.com/news/2021-10-solution-combinatorial-optimization-problem-bicycle.html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.