Les stratégies de recherche nouvellement proposées améliorent le coût de calcul du problème du partage de vélos

bicyclette

Crédit : domaine public CC0

Le partage de vélos est une option de transport zéro carbone attrayante pour un monde de plus en plus perturbé par le changement climatique. Mais les vélos doivent être restaurés de temps en temps dans les ports à vélos. Le calcul de la manière optimale de restaurer les vélos prend du temps et coûte cher en calculs. Récemment, des chercheurs de l’Université des sciences de Tokyo se sont appuyés sur leur précédent algorithme d’optimisation pour proposer deux stratégies visant à réduire les coûts de calcul tout en maintenant les performances de l’algorithme.

Les systèmes de partage de vélos (BSS) sont des solutions de transport dans lesquelles les utilisateurs peuvent louer un vélo à partir d’un dépôt ou d’un “port”, voyager, puis ramener le vélo au même port ou à un port différent. Les BSS gagnent en popularité dans le monde entier car ils sont respectueux de l’environnement, réduisent les embouteillages et offrent des avantages supplémentaires pour la santé des utilisateurs. Mais finalement, un port devient plein ou vide dans un BSS. Cela signifie que les utilisateurs ne peuvent plus louer un vélo (lorsqu’il est vide) ou en restituer un (lorsqu’il est plein). Pour résoudre ce problème, les vélos doivent être rééquilibrés entre les ports d’un BSS afin que les utilisateurs puissent toujours les utiliser. Ce rééquilibrage doit également être effectué d’une manière qui profite aux entreprises BSS afin qu’elles puissent réduire les coûts de main-d’œuvre, ainsi que les émissions de carbone des véhicules de rééquilibrage.

Il existe plusieurs approches existantes pour le rééquilibrage BSS, cependant, la plupart des algorithmes de solution sont coûteux en calcul et prennent beaucoup de temps pour trouver une solution “exacte” dans les cas où il y a un grand nombre de ports. Même trouver une solution approximative est coûteux en calcul. Auparavant, une équipe de recherche dirigée par le professeur Tohru Ikeguchi de l’Université des sciences de Tokyo a proposé un “problème de routage du système de partage de vélos à plusieurs véhicules avec des contraintes souples” (mBSSRP-S) qui peut trouver les temps de trajet les plus courts pour plusieurs véhicules de rééquilibrage de vélos avec le mise en garde que la solution optimale peut parfois violer les limites du monde réel du problème. Maintenant, dans une étude récente publiée dans le MDPI’s Sciences appliquées, l’équipe a proposé deux stratégies pour rechercher des solutions approximatives au mBSSRP-S qui peuvent réduire les coûts de calcul sans affecter les performances. L’équipe de recherche a également présenté un doctorat. l’étudiante Mme Honami Tsushima de l’Université des sciences de Tokyo et le professeur Takafumi Matsuura du Nippon Institute of Technology.

Décrivant leurs recherches, le professeur Ikeguchi déclare que “plus tôt, nous avions proposé le mBSSRP-S et qu’il offrait des performances améliorées par rapport à notre mBSSRP d’origine, qui ne permettait pas la violation des contraintes. Mais le mBSSRP-S augmentait également le calcul global. coût du problème car il devait calculer à la fois les solutions réalisables et irréalisables du mBSSRP. Par conséquent, nous avons maintenant proposé deux stratégies de recherche consécutives pour résoudre ce problème.

Les stratégies de recherche proposées recherchent des solutions réalisables dans une période de temps beaucoup plus courte par rapport à celle proposée à l’origine avec mBSSRP-S. La première stratégie se concentre sur la réduction du nombre de solutions “voisines” (solutions qui sont numériquement proches d’une solution au problème d’optimisation) avant de trouver une solution réalisable. La stratégie utilise deux algorithmes bien connus appelés “Or-opt” et “CROSS-exchange”, pour réduire le temps global nécessaire au calcul d’une solution. La solution faisable ici fait référence à des valeurs qui satisfont les contraintes de mBSSRP.

La deuxième stratégie modifie le problème à résoudre en fonction de la solution réalisable au problème mBSSRP ou au problème mBSSRP-S, puis recherche de bonnes solutions quasi optimales en peu de temps par Or-opt ou CROSS-exchange.

L’équipe de recherche a ensuite réalisé des expériences numériques pour évaluer le coût de calcul et les performances de leurs algorithmes. “Grâce à l’application de ces deux stratégies, nous avons réussi à réduire le temps de calcul tout en maintenant les performances”, révèle le professeur Ikeguchi. “Nous avons également constaté qu’une fois que nous avons calculé la solution réalisable, nous pouvions trouver rapidement des temps de trajet courts pour les véhicules de rééquilibrage en résolvant le problème de contrainte dure, mBSSRP, au lieu de mBSSRP-S.”

La popularité des BSS ne devrait que croître à l’avenir. Les nouvelles stratégies de recherche de solutions proposées ici contribueront grandement à la réalisation de BSS pratiques et confortables qui profitent aux utilisateurs, aux entreprises et à l’environnement.


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


Plus d’information:
Honami Tsushima et al, Recherche de stratégies à faibles coûts de calcul pour le problème de routage du système de partage de vélos à plusieurs véhicules, Sciences appliquées (2022). DOI : 10.3390/app12052675

Fourni par l’Université des sciences de Tokyo

Citation: Les stratégies de recherche nouvellement proposées améliorent le coût de calcul du problème du partage de vélos (2022, 5 mai) récupéré le 5 mai 2022 sur https://techxplore.com/news/2022-05-newly-strategies-bicycle-sharing-problem.html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation loyale à 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.