Analyse comparative des croisements dans les algorithmes génétiques pour l’optimisation d’itinéraires : études de cas d’Astana et de Chimkent, Kazakhstan

Pourquoi des lignes de bus plus intelligentes comptent

Quiconque a attendu trop longtemps un bus ou enchaîné plusieurs correspondances sait que traverser une ville ne se résume pas à la distance. Deux lieux peuvent sembler proches sur une carte, mais être difficiles d’accès si les bonnes lignes de bus ne les relient pas. Cet article explore comment une classe de méthodes de recherche inspirées de l’évolution — les algorithmes génétiques — peut être ajustée pour concevoir de meilleures lignes de bus qui respectent les réseaux de transport réels dans des villes comme Astana et Chimkent au Kazakhstan. Le travail se concentre sur un ingrédient crucial de ces algorithmes, appelé l’étape de croisement, et montre comment bien le choisir peut faire la différence entre des trajets maladroits et détournés et des itinéraires rapides et réalistes.

Des cartes urbaines désordonnées à une recherche intelligente

Les planificateurs d’itinéraires traditionnels traitent souvent les villes comme si les voyageurs pouvaient se déplacer librement entre deux points, ne regardant que la distance physique. Les systèmes de bus réels ne fonctionnent pas ainsi : on ne peut aller que là où les lignes existent réellement, et chaque lien manquant ou détour imposé coûte du temps et de l’argent. Les auteurs modélisent cette réalité en représentant les lieux importants de la ville comme des points, les routes et les liaisons de bus comme des connexions, et un trajet complet comme un chemin qui visite chaque point exactement une fois. Ils posent alors un objectif en deux volets : d’abord, éviter les étapes « illégales » où il n’existe pas de bus direct ; ensuite, parmi les trajets légaux, choisir celui de distance totale la plus courte. Cela crée un casse-tête difficile avec de nombreux chemins possibles, où vérifier chaque option devient vite impossible à mesure que la ville grandit.

Comment l’évolution aide à trouver de meilleurs itinéraires

Les algorithmes génétiques attaquent ce type de problème en imitant la sélection naturelle. Plutôt que d’essayer un trajet à la fois, ils conservent toute une population de trajets candidats. À chaque génération, les meilleurs trajets sont favorisés, et de nouveaux sont créés en mélangeant et en modifiant légèrement les existants. L’étape clé du mélange — le croisement — décide comment des morceaux de deux trajets parents sont combinés pour former un trajet enfant. Pour la planification des bus, cette étape est critique : bien faite, elle transmet des schémas utiles d’arrêts connectés ; mal faite, elle peut briser des liens et produire des itinéraires qui ignorent le réseau de bus. Les auteurs testent neuf styles de croisement différents qui varient selon la façon dont ils préservent l’ordre des arrêts, les positions exactes des arrêts ou les liaisons réelles entre arrêts.

Tester de nombreuses façons de mélanger les trajets

Pour déterminer quels styles de croisement fonctionnent le mieux, l’équipe mène une large batterie d’expériences sur des données de transport réelles de Konya (ville de référence d’un travail antérieur) et d’Astana et Chimkent. Pour chaque ville, ils sélectionnent 14 destinations importantes, les relient aux arrêts proches, et construisent trois tableaux de données clés : les distances entre lieux, les paires qui disposent d’un bus direct, et les pénalités pour tenter de voyager là où aucun bus ne circule. Ils explorent ensuite des centaines de réglages, faisant varier la taille de la population, la fréquence d’utilisation du croisement, et la fréquence des petites modifications aléatoires (mutations). Pour chaque réglage, ils répètent l’algorithme de nombreuses fois pour tenir compte du hasard, et mesurent non seulement la brièveté des trajets finaux, mais aussi la fréquence à laquelle la méthode trouve un trajet légal et la rapidité avec laquelle elle y parvient.

La stratégie gagnante pour des trajets réalistes

Dans les trois villes, un style de croisement se distingue : la recombinaison d’arêtes. Contrairement aux méthodes qui se préoccupent principalement de l’ordre des arrêts, la recombinaison d’arêtes prête attention à quels arrêts sont directement liés et cherche à préserver ces liaisons lorsqu’elle construit de nouveaux trajets. L’étude montre que cette approche centrée sur les arêtes est bien plus susceptible de produire des trajets de bus réalisables, redécouvre plus souvent les meilleurs itinéraires connus, et le fait généralement en seulement quelques générations. Un second style, appelé croisement basé sur l’ordre, obtient également de bonnes performances et est plus rapide à calculer, offrant un bon compromis lorsque de très nombreux runs sont nécessaires. D’autres croisements courants qui réarrangent les arrêts de façon plus agressive ont tendance à peiner, nécessitant plus de temps et produisant moins d’itinéraires de haute qualité.

Ce que cela signifie pour les déplacements quotidiens

Pour un non-spécialiste, la conclusion est que la « recette » utilisée à l’intérieur d’un algorithme génétique peut avoir un fort impact sur la qualité des trajets qu’il conçoit. En privilégiant des règles de croisement qui conservent les liaisons réalistes tout en explorant de nouvelles combinaisons, les planificateurs peuvent générer des itinéraires qui respectent le réseau de bus existant tout en minimisant la distance totale de déplacement. Dans des tests sur des instantanés urbains petits mais réalistes, l’algorithme génétique le mieux réglé non seulement a égalé des itinéraires trouvés par des méthodes mathématiques exactes, mais l’a fait rapidement et de façon fiable. Cela suggère que, à mesure que les villes deviennent plus complexes et riches en données, une recherche évolutionnaire bien conçue peut aider les agences de transport à planifier des lignes qui paraissent plus directes, nécessitent moins de correspondances pénibles, et optimisent l’utilisation des véhicules et du carburant.

Citation: Kazbek, R., Sergaziyev, M., Kenzhe, D. et al. A comparative analysis of crossovers in genetic algorithms for route optimization: case studies from Astana and Shymkent, Kazakhstan. Sci Rep 16, 13816 (2026). https://doi.org/10.1038/s41598-026-43898-7

Mots-clés: itinéraires de transports en commun, algorithmes génétiques, mobilité urbaine, optimisation d’itinéraires, planification de villes intelligentes