Placer des vélos ne suffit pas. Il faut pouvoir les atteindre depuis une porte via un couloir de 1,20 m. La capacité accessible est la seule métrique qui compte.
Un parking vélo rempli à 100 % mais inaccessible vaut zéro. M4 s'assure que chaque vélo posé peut être atteint par un humain.
Le constructeur M2/M3 maximise le nombre de vélos posés — la capacité brute. Mais si un rack est coincé derrière trois rangées sans couloir, il est inutile. La capacité accessible correspond au nombre de vélos qui peuvent être atteints depuis une porte via un couloir de circulation de 1,20 m de large (norme PMR).
Largeur couloir PMR
Résolution de la grille
Cellules pour 1,20 m
Un maillage à 0,15 m transforme la géométrie continue en un problème de grille.
Le polygone de la pièce est rasterisé sur une grille carrée de pas 0,15 m. Chaque cellule est soit libre (0) soit occupée par un vélo (1). Les poteaux et murs sont marqués comme obstacles.
Le couloir de circulation a une largeur exacte de 1,20 m, soit 8 cellules de la grille. Pour vérifier si un couloir passe, on teste si une fenêtre de 8 cellules de large est entièrement libre.
Pour tester rapidement si une fenêtre rectangulaire est libre, on pré-calcule les sommes préfixes 2D de la grille d'occupation. Le test d'une fenêtre se réduit alors à 4 additions au lieu de parcourir 8×N cellules.
Trouver le chemin de la porte aux racks qui retire le moins de vélos possible.
Le graphe de circulation est initialisé avec un nœud source placé au centre du nœud d'accès de la porte. C'est le point d'entrée unique pour les usagers.
Chaque cellule de la grille a un coût de traversée : 0 si elle est libre, sinon le nombre de vélos qu'il faudrait retirer pour la libérer. Le chemin optimal est celui qui minimise ce coût total.
À coût d'occupation égal, on préfère le chemin le plus court. Un petit epsilon (step_eps) est ajouté au coût par cellule traversée pour garantir ce départage sans perturber l'optimisation principale.
Dijkstra avec une file de priorité (min-heap) garantit de trouver le chemin qui retire le minimum absolu de vélos. Pas d'heuristique, pas d'approximation — c'est un optimum exact.
Deux approches opposées pour combiner pose de vélos et circulation. Les deux sont évaluées, la meilleure est retenue.
Poser d'abord, tailler ensuite. Le constructeur remplit la pièce au maximum, puis Dijkstra trace un couloir en retirant les vélos gênants.
Réserver d'abord, poser ensuite. Le couloir de 1,20 m est réservé avant la pose. Le constructeur ne remplit que l'espace restant.
Quand une pièce a plusieurs portes, les couloirs peuvent se partager des tronçons.
Les portes sont traitées séquentiellement. Après le premier Dijkstra, les cellules du couloir tracé sont marquées comme libres à coût 0. Le Dijkstra suivant (pour la deuxième porte) profite automatiquement de ce tronçon gratuit et ne « creuse » que les segments nécessaires pour atteindre les zones non encore desservies.
Couloir unique, linéaire. Dessert les racks le long du chemin.
Forme en Y ou L selon la géométrie. Tronc commun partagé.
Arbre de desserte. Chaque branche supplémentaire coûte de moins en moins.
Chaque rack est individuellement testé pour garantir qu'il est atteignable.
Un parcours en largeur (BFS) part de l'espace libre connecté aux portes. Toutes les cellules libres atteignables sont marquées. Ce BFS s'exécute sur la grille après traçage du couloir.
Pour chaque rack posé, on vérifie qu'au moins une cellule adjacente (devant, côtés) est dans l'ensemble des cellules libres atteignables. Si oui, le rack est accessible. Sinon, il est isolé.
Un rack inaccessible reçoit une pénalité fatale dans la fonction objectif : sa capacité est comptée comme 0. Cela force l'optimiseur NSGA-II (M5) à éviter les configurations qui créent des zones mortes.
capacité_brute − vélos_inaccessibles. L'objectif f₁ du NSGA-II est de maximiser cette valeur nette, ce qui élimine naturellement les layouts qui sacrifient l'accessibilité pour la densité.
Un couloir tout droit est plus confortable qu'un labyrinthe. M4 peut en tenir compte.
Un paramètre optionnel turn_penalty ajoute un coût supplémentaire à chaque changement de direction dans le chemin de Dijkstra. Un virage à 90° coûte turn_penalty ; un demi-tour (180°) coûte 2 × turn_penalty.
Effet : l'algorithme préfère les couloirs rectilignes, même s'ils sont légèrement plus longs. Cela améliore l'ergonomie pour les usagers et facilite le passage avec des vélos chargés.
| Paramètre | Valeur par défaut | Effet |
|---|---|---|
turn_penalty | 0.0 | Désactivé — chemin le plus court uniquement |
turn_penalty | 0.5 | Légère préférence pour les lignes droites |
turn_penalty | 2.0 | Forte pénalisation — couloirs quasi-rectilignes |
L'état dans la file de priorité est étendu de (coût, x, y) à (coût, x, y, direction). Quand la direction change entre deux cellules consécutives, le coût de virage est ajouté.