J'adore Panoramax, mais en me baladant, je ne sais jamais si je dois tourner à droite ou à gauche pour ne pas repasser trop aux mêmes endroits. Heureusement, j'ai quelques outils.

Alors oui, le titre est peut être bizarre, je vais vous expliquer quand même un peu. 

Posons le problème

Comme je le disais plus haut, lors de mes campagnes panoramax, j'ai toujours ce dilemme de vouloir passer partout, mais sans repasser plusieurs fois aux mêmes endroits et ainsi éviter aussi de marcher ou pédaler des kilomètres inutiles qui pourraient photographier d'autres endroits (et puis cela me fatigue). Cela m'a surtout interrogé quand j'ai traversé le cimetière de Kerfautras. Pour ceux qui ne connaissent pas, c'est là

Afficher une carte plus grande

Vous l'avez ? chaque fois que je vois le plan, j'y pense, maintenant vous aussi (gnarf, gnarf, gnarf...)

Donc comment passer dans toutes les allées, sans tourner en rond ? Et bien, c'est simple, faisons appel à la géomatique et à un postier chinois.

CPP ou Chinese Postman Problem

Sans doute moins connu que le voyageur de commerce, mais tout aussi important, sinon plus. Je ne refais pas ce que l'on trouve sur wikipedia (lien) ou bien ici (chinese postman), mais donc il s'agit de trouver le chemin qui permet de passer partout. Très utile pour les tournées de déneigement, de recherche systématique...

Pour cela, il nous faut un graphe avec des noeuds, autrement dit, dans notre cas : des routes et des croisements, des impasses, des boucles, etc. En gros pour résoudre ce problème complexe, il faut faire intervenir plusieurs étapes.

1. Avoir un graphe
2. avoir un graphe topologique
3. avoir un graphe topologique dont on extrait des noeuds
4. regarder de près les noeuds, compter leur degré
5. relier les noeuds
6. les parcourir pour trouver le plus court

Avoir un graphe

Le plus facile, on peut soit partir de la BDTOPO, soit d'OSM, ou si avez votre propre réseau cela fonctionne aussi, je vous laisse tranposer dans la suite. Dans mon cas, j'ai regardé les 2 (BDTOPO et OSM) et ici, on voit nettement que OSM est plus riche sur les sentiers du cimetière.

Je vais donc charger les tracés via le plugin QUICKOSM, en prenant toutes les routes. Rien de notable ici à vous partager.

Avoir un graphe topologique

J'ai mon graphe, je vais maintenant le nettoyer pour pouvoir calculer mon postier chinois (ou rural). Je retire toutes les routes qui ne m'intéresse pas (selection, supp, rapide), ce n'est pas obligatoire mais on y voit plus clair.

Je vérifie la topologie, à savoir est-ce-que les routes qui se suivent sont bien raccordées entre elles ? Pour cela, vu le peu de chemin, une verif via les outils verif topologique de QGIS suffit, doublé d'un oeil de lynx. Pour des graphes plus compliqués, on peut faire intervenir des outils plus puissants.

Ici tout va bien, reste à vérifier comment sont tracés les chemins :

 c'est bien ce que je craignais, il y a de grands tracés qui ne sont pas interrompus à chaque intersection, et bien faisons le : l'outil utiliser pour cela est  : couper avec des lignes. Normalement, il s'utilise pour coupe une couche de ligne avec une autre couche de ligne, mais si vous coupez votre couche avec elle même, vous obtenez des tronçons coupés à chaque intersection.

lignes bien coupées !

Pour quoi faire ça : pour voir tous les noeuds possibles ou orientés le graphe, chaque noeud est un croisement où vous pouvez tourner à droite ou à gauche, si j’ai une grande ligne, je suis dans le cas d’une route sous un pont ou en tunnel, donc sans choix de tourner. Penser à rassembler ces lignes (pont ou tunnel) si c’est le cas.

Regarder les noeuds de près, les relier, parcourir le graphe

Et c'est là que mes ennuis ont commencé. Je pensais naïvement pouvoir tout faire dans postgis, couplé à un peu de pgrouting et de qgis. Malheureusement, je me suis vite rendu compte à ma grande surprise que PGROUTING n'a pas de fonction pour résoudre ce problème. Il y a bien une fonction expérimentale (https://docs.pgrouting.org/latest/en/pgr_chinesePostman.html) mais rien d’établi de façon sûr et facile.

Je ne suis donc lancé dans l'expérience. NE FAITES PAS CELA (sauf si vous avez une bonne raison), j'ai galéré une bonne semaine. Je vous explique les étapes suivies et que je pensais décrire dans cet article, mais vous verrez que j'ai fini par choisir la facilité...

Donc j'ai pris mon graphe, j'ai importé tout ça en base :

Créer la table depuis chemin pour pgrouting - check - important ici : votre couche doit être en polyligne simple pas de multistring, sinon marche pas, appris à mes dépens
SELECT * INTO vertices2
FROM pgr_extractVertices('SELECT id, geom FROM public.chemin ORDER BY id');

Ajouter un champs "source" pour indiquer quel est le noeud de départ - check
ALTER TABLE public.chemin ADD "source" int4 NULL;
UPDATE public.chemin AS e
SET source = v.id
FROM vertices2 AS v
WHERE ST_StartPoint(e.geom) = v.geom;

Ajouter un champs "target" pour indiquer quel est le noeud d'arrivée - check aussi
ALTER TABLE public.chemin ADD "target" int4 NULL;
UPDATE public.chemin AS e
SET target = v.id
FROM vertices2 AS v
WHERE ST_EndPoint(e.geom) = v.geom;

Ajouter un champs "cost" pour quantifier/ponderer mes tronçons, je prends ici que la longueur, pas besoin de pondérer des difficultés - check
ALTER TABLE public.chemin ADD "cost" numeric NULL;
update public.chemin set cost = ST_Length(geom);

Et un coût de chemin de retour, optionnel, mais comme ça il est là si besoin
ALTER TABLE public.chemin ADD "reverse_cost" numeric NULL;

En passant, vous noterez l'obligation de compiler un pgrouting récent pour bénéficier de la fonction expérimentale.

Tiens, j'en profite pour regarder les noeuds de près, c'est vrai je n'ai pas expliqué les degrés des noeuds, notion importante, qui, ici, nous servira à rien. Le degré d'un noeud est le nombre de route qui arrivent ou qui partent, tout simplement, si je suis au croisement de 4 routes, mon noeud est degré 4.

 Il faut connaitre cette notion pour évaluer si le noeud est pair ou impair, car c'est là qu'intervient Euler : un cycle eulérien ne peut être composé que de noeuds pairs, par contre un parcours eulérien peut commencer et finir sur des noeuds impairs (il est semi-eulérien), et si y'a plein de noeud impairs, il n'est pas eulérien du tout. Résoudre le problème du postier chinois revient donc à trouver un cycle eulérien là où il n'y en a pas.

Étapes pour résoudre le CPP

1. Identifier les nœuds impairs dans le graphe.
2. Trouver les paires de nœuds impairs à connecter avec le chemin le plus court (problème de couplage minimum).
3. Ajouter ces chemins au graphe (dupliquer les arêtes correspondantes).
4. Trouver un cycle eulérien sur le graphe modifié (algorithme de Hierholzer).
5. Retirer les arêtes dupliquées dans le parcours final (elles correspondent aux rues parcourues deux fois).

J'ai donc essayé dans ma base de trouver les noeuds pairs et impairs, pas trop compliqué, j'utilise la table vertice créée avec pgrouting

ALTER TABLE vertices2
ADD COLUMN degres INTEGER
GENERATED ALWAYS AS (
coalesce(cardinality(in_edges),0)+coalesce(cardinality(out_edges),0)
) STORED;

ALTER TABLE public.vertices2
ADD COLUMN est_pair bool
GENERATED ALWAYS AS (
(coalesce(cardinality(in_edges),0)+coalesce(cardinality(out_edges),0))%2=0
) STORED;

(le résultat est dans l'image). 

Et là, c'est la galère totale : des jours à chercher des chemins entre impairs à coup de pgr_dijkstraCostMatrix , de table temporaire, de bidouilles, de test de pgr_chinesePostman​ (qui fonctionne bien, dès que vous avez un graphe eulérien)​​​​​​. bref, il manque vraiment un calcul du couplage minimal, et j'ai eu beau chercher, si personne ne la fait, ce n'est pas sans raison. Toutes les solutions en base m'envoient vers un code python qui exporte, fais tourner networkx, et réimporte pour utiliser pgr_chinesepostman...

Échec… Oui, car j’échoue souvent, mais cette fois, j’ai persévéré.

L'échec n'est pas une option

Bon, Il y a sûrement quelqu'un qui a fait un plugin QGIS, ou qui a un modèle quelquepart...Et oui, il y a le plugin de Ralf Kistner https://github.com/rkistner/chinese-postman auquel je tire mon chapeau (you're awesome, man, that’s a massive job) qui malheureusement ne fonctionne pas sur ma config... même avec une modif récente, le code a ±10 ans.

Une fois remis au goût du jour, il ne répond que partiellement à mon problème, puisqu’il ne gère que les graphes fermés, et ne permet pas de choisir un point de départ.

Et puis il y a Qgis 4 qui débarque, et franchement, il est temps que je me serve d’une IA de codage, non ?

Vague-coding

Ok, donc j’ai donc forké le code, et branché Mistral Code (codestral-latest) là-dessus. Ce que j’ai appris, ce qui va amuser les pros du prompt et du vibe-coding qui maitrisent le sujet :

1. ça va vite, là où j’aurais posé la question sur StackOverflow, attendu 3 jours une ou deux réponses, tester, reposer une question…tout se fait en 5 minutes,
2. Il faut être précis, c’est effectivement en posant une question précise, sur un problème à la fois que les réponses sont les plus pertinentes et ne cassent pas tout,
3. faut vérifier, cela ne dispense de lire la doc, car entre les instructions qui n’existent pas ou plus, la syntaxe douteuse, il faut justement mettre le nez de l’IA dedans et lui dire non, l’instruction c’est ça, vérifies le reste du code…
4. y’a des fois, elle a des super idées !

Et finalement, j’ai donc participer à la naissance d’un nouveau plugin, pas en codant, en chef de projet assisté, indiquant quelle fonction, envoyant les logs, donnant des instructions. J’ai "assisté" plus que "été assisté", à mon sens, mais j’ai appris à utiliser Code et difficile de faire sans de nos jours...

Alors pour des raisons techniques, j’ai fini certaines parties à l’ancienne dans mon vscodium avec mes petits doigts boudinés, avant de mettre le code sur codeberg (qui n’est pas reconnu par Mistral, un comble d’être obligé de tout mettre sur github!!!) et tenter de voir si des parties du code sont à nettoyer du coté verbeux des IA.

CPP-Solver

Donc voici le repo du plugin, mais que fait-il et comment cela fonctionne ?

https://codeberg.org/pasq_fr/cpp_solver

zip à installer

Avoir un graphe…

Comme dans la première partie, il faut un graphe topologique bien découpé à chaque noeud. 

• Sélectionnez tous les segments qui vous intéresse, puis cliquer sur le joli logo fait par moi.
• Cela va tracer d’abord tous les noeuds indiquant s'ils sont pairs ou impairs (alors oui, tout est en anglais pour viser l’international…)
• Vous pouvez choisir le noeud de départ (un noeud impair/odd si possible) et un noeud d’arrivé (impair/odd aussi), et là, normalement, le tracé passe par tous les tronçons.

Si c’est moche, vous pouvez modifier le .qml du répertoire du plugin pour changer le style par défaut.

Limitations

Bon, je suis content, cela fonctionne, tester sur QGIS4.2 (sous linux) et QGIS3.40 (sous window$),  mais il y a certaines limites :

• Le graphe n’est pas orienté ou ne prend pas en compte des restrictions éventuelles : sens uniques, gabarit… je suis parti dans l’idée d’être à pied ou à vélo,
• Je n’ai pas testé sur des grands ensembles et ne le faîtes pas ! Normal, on atteint vite une complexité d’adjacence (cf. Pour un graphe de 100 000 nœuds, la matrice nécessite 10 milliards d'entrées.)
• Le tracé se fait entre noeud, ce qui peut rendre la lecture compliquée, je m’explique : dans le cas d’une courbe, vous aurez un résultat tout droit (cf. illustrations) ce qui est logique puisque l’on va de noeud en noeud et on ne suit pas le "trait". J’ai essayé une solution qui suit le tracé, mais cela génére un noeud à chaque sommet de courbe, et donc beaucoup de tracés possibles…Pour améliorer cela, on peut :
  • soit ajouter manuellement des points en coupant les courbes ou les grands changements de direction à des endroits stratégiques
  • soit modifier la couche chinese-postman générée pour y voir plus clair (en s’aidant du noeud de départ et noeud d’arrivée)

autre test avec des rues plus complexes, où j'ai bouclé à la main quelques rues et  supprimer certaines :

Où l'on voit qu'une bonne préparation de ces chemins est indispensable. Exemple sur ces boucles "oubliées" ou le départ qu'il refuse de prendre sur un noeud pair!! et donc ne peut pas boucler (d'ailleurs je ne sais pas pourquoi ce noeud est impair et l'autre pair sur cette boucle, bug ???).

Je dis préparation car en découpant les premières boucles et en ajoutant un petit bout au départ ou à l'arrivée, cela améliore le tracé.

Ce n’est pas parfait mais le code n’attend plus que vous pour s’améliorer.

Vivement le prochain défi ! et si c'était encore l'IA : https://medium.com/@iamavneetkaur16/ai-on-the-streets-reinforcement-learnings-journey-to-solve-the-chinese-postman-problem-70c994136eaa

BONUS

Juste pour le plaisir (mais pas que, car cela m'a bien servi sur le terrain, je vous laisse aller voir sur panoramax si j'ai réussi, tout ce que je peux vous dire, c'est que j'ai besoin d'une meilleure solution de guidage, dîtes moi si vous en voyez une en commentaire), j'ai ajouté une colonne temps (datetime) à mon parcours chinese-postman, juste pour vous faire une petite animation.

Dans la calculatrice de champs, j'ai ajouté une colonne temps qui converti l'ordre en temps sur 1 journée : 

 make_datetime( 2026,01,01,floor("order"*23 / maximum("order")),floor(( "order"*23 / maximum("order")  % 1) * 60), round((( "order"*23 / maximum("order")  % 1) * 60 - floor(( "order"*23 / maximum("order")  % 1) * 60)) * 60))

ensuite le contrôleur temporel fait le reste :

P.S. : cet article et son illustration, contrairement au plugin, sont fait à la main, parce-que faut pas déconner quand même, on va pas tout filer à l’IA, non mais oh…