Optimiseur de tournée

Placez 8 livraisons. L'algo vous corrige.

RouteE4Découverte 8 min

Drag & drop sur grille 2D. Comparaison ordre élève vs plus-proche-voisin vs optimal exhaustif (≤8 points).

Optimiser une distanceComparer des solutions

Composez votre tournée

Trait cyan : votre tournée · trait vert pointillé : optimal. Cliquez sur deux points pour les permuter dans l'ordre.

Méthode pro

## Méthode pro

1. Cadrer
Objectif: comparer une tournée « plus-proche-voisin » (PPV) à un ordre optimisé (distance minimale) en intégrant contraintes opérationnelles: SLA/fenêtres horaires, temps service, vitesse moyenne, et pondération pénalité de retard.

2. Les formules / règles clés
- Distance tournée: somme des arcs parcourus (km)
- Temps déplacement: Distance / Vitesse moyenne (h)
- Temps total: Déplacement + Σ Temps service (h)
- Lateness i: max(0; ETAi – Li) où Li = limite SLA (h)
- Score multi-critère: Distance + λ × Σ Lateness (km équivalents ou min pénalisées)

3. Étapes de résolution
1) Collecter la matrice de distances symétriques (ou temps) incluant retour dépôt et les SLA par client; fixer vitesse moyenne (ex: 40 km/h) et temps de service par stop.
2) Construire la solution PPV: départ dépôt → choisir itérativement le client le plus proche non servi; fermer la boucle au dépôt.
3) Générer une solution alternative: tri heuristique (ex: par azimut OU 2-opt local) ou séquence dictée par SLA; calculer distance/temps.
4) Calculer pour chaque route: ETA à chaque stop (cumuls déplacement + service), retards éventuels, score pénalisé avec λ (ex: 10 min = 1 km équivalent).
5) Comparer PPV vs optimal: distance, temps total, respect SLA; retenir la meilleure au score défini avec l’exploitation.
6) Tester la robustesse: variante vitesse (trafic), glisser 2-opt pour éliminer croisements, échanger deux arrêts si gros gain.
7) Restituer KPIs: km économisés, % SLA tenus, heures de conduite (lien 561/2006), coût variable évité (CRK×km).

4. Pour aller plus loin
- Méthodes: savings de Clarke & Wright, 2-opt/3-opt, VNS; prise en compte fenêtres horaires (VRPTW). KPI BTS GTLA: taux de service, km à vide, temps d’attente. Références: règlement 561/2006 (temps de conduite/pauses), ADR si matières dangereuses, GDP si pharma (respect température/temps). Intégrer Incoterms 2020 (point de transfert) et CO2e (ADEME) pour arbitrer vitesse vs émissions. Lier au ROI: chaque km évité = CRK × km; rapporter aussi pénalités SLA évitées.

Cas types corrigés

Cas 1

PPV vs ordre optimisé — 4 clients

Dépôt D et clients A, B, C, E. Distances symétriques (km): D-A 4, D-B 6, D-C 8, D-E 7; A-B 3, A-C 7, A-E 4; B-C 2, B-E 3; C-E 3. Vitesse 40 km/h, 6 min de service par stop.

Résolution

1.Plus-proche-voisin: D→A(4)→B(3)→C(2)→E(3)→D(7) = 19 km.
2.Permutation 2-opt testée D→A→B→E→C→D: 4+3+3+3+8 = 21 km → rejetée.
3.Temps total PPV = 19/40 h + 4×6 min = 28,5 + 24 = 52,5 min.
4.Comparaison: aucune permutation ne descend sous 19 km → PPV est ici l'optimum.

Tournée retenue 19 km / 52 min, optimum confirmé par 2-opt.

→ Le PPV peut être optimal sur de petits problèmes — toujours valider par un 2-opt avant de figer.

Cas 2

Distance vs respect SLA

Mêmes 4 clients. SLA: B doit être livré avant 08:30. Départ 08:00, vitesse 40 km/h, 6 min/stop. Pénalité λ = 2 km par 10 min de retard.

Résolution

1.Route distance-minimale D→A→B→C→E→D = 19 km. ETA B: 4 km (6 min) + 6 min service A + 3 km (4,5 min) = 16,5 min → 08:16:30, pas de retard.
2.Route alternative D→C→B→A→E→D = 8+2+3+4+7 = 24 km, ETA B = 8 km (12 min) + 6 min + 2 km (3 min) = 21 min → 08:21, ok mais +5 km inutiles.
3.Score pénalisé route 1 = 19 + 0 = 19.
4.Score pénalisé route 2 = 24 + 0 = 24.

La route 19 km respecte le SLA et minimise le score — gain net 5 km.

→ Un coefficient de pénalité explicite oriente l'algorithme vers le respect du SLA quand il le faut.