# Debug TSP - Pourquoi l'optimisation ne fonctionne pas

**Date:** 2025-11-23  
**Issue:** L'utilisateur dit que l'optimisation ne marche pas malgré beaucoup de détours  
**Solution:** Ajout de logs détaillés pour diagnostiquer

---

## Hypothèses à vérifier

### 1. Stages sans coordonnées GPS
**Symptôme:** Optimisation retourne ordre identique, 0% d'économie

**Cause possible:**
- Stages créés sans sélectionner de lieu sur la carte
- Location existe mais `coordinates.lat/lng` sont `null` ou `undefined`
- Adresse textuelle seulement, pas de géocodage

**Test:**
```
Ouvrir console backend → POST /api/route-optimization/plans/:planId/optimize
Vérifier logs "STAGES RECEIVED FOR OPTIMIZATION"
```

**Logs attendus:**
```
📍 STAGES RECEIVED FOR OPTIMIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
1. Paris
   Location: 48 Rue de Rivoli, 75001 Paris
   Coordinates: 48.8566, 2.3522
2. Lyon
   Location: Place Bellecour, 69002 Lyon
   Coordinates: 45.7578, 4.8320
3. Marseille
   Location: Vieux-Port, 13001 Marseille
   Coordinates: 43.2965, 5.3698
```

**Si problème:**
```
1. Paris
   Location: NO ADDRESS
   Coordinates: ❌ MISSING
   ⚠️  WARNING: Missing or invalid coordinates!
```

**Solution:**
- Backend retourne maintenant erreur 400 avec message clair
- Frontend doit forcer l'utilisateur à sélectionner un lieu sur la carte
- Ne pas accepter de stages sans coordonnées

---

### 2. Tous les stages au même endroit
**Symptôme:** 0% économie, ordre identique

**Cause possible:**
- Utilisateur a créé plusieurs stages mais tous avec la même adresse
- Bug frontend qui duplique les coordonnées

**Test:**
```
Vérifier logs TSP dans console backend
```

**Logs attendus (si problème):**
```
🔄 TSP Optimization:
   Current: Paris (48.86, 2.35)
   Evaluating 3 candidates:
     - Lyon: 0.0 km  ❌ PROBLÈME!
     - Marseille: 0.0 km  ❌ PROBLÈME!
     - Bordeaux: 0.0 km  ❌ PROBLÈME!
```

**Si normal:**
```
   Current: Paris (48.86, 2.35)
   Evaluating 3 candidates:
     - Lyon: 392.4 km
     - Marseille: 660.3 km
     - Bordeaux: 498.7 km
   ✓ Selected: Lyon (392.4 km away)
```

---

### 3. Ordre déjà optimal
**Symptôme:** 0-2% économie

**Cause:** Le trajet est déjà dans l'ordre le plus efficace

**Exemple:**
```
Paris → Lyon → Marseille → Nice
```
C'est déjà optimal (ligne droite vers le sud), TSP ne peut rien améliorer.

**VS:**
```
Paris → Nice → Lyon → Marseille
```
Très inefficace, TSP va réordonner en `Paris → Lyon → Marseille → Nice`

**Test:** Créer volontairement un trajet illogique
```
1. Paris (48.86, 2.35)
2. Marseille (43.30, 5.37) - Sud
3. Lille (50.63, 3.06) - Nord
4. Lyon (45.76, 4.83) - Sud-Est
5. Bordeaux (44.84, -0.58) - Sud-Ouest
```

TSP devrait réordonner :
```
1. Paris (FIXE - départ)
2. Lille (50km Nord) - plus proche de Paris
3. Lyon (400km Sud-Est)
4. Marseille (300km Sud)
5. Bordeaux (FIXE - arrivée)
```

---

### 4. Seulement 2-3 stages
**Symptôme:** Message "No optimization possible"

**Cause:** Pas assez de stages intermédiaires à optimiser

**Explication:**
- 2 stages total → Rien à optimiser (A → B)
- 3 stages total → Rien à optimiser (Start → Waypoint → End)
- 4+ stages → Optimisation possible

**Fix:** Ajouter plus d'étapes au voyage

---

## Logs de debug ajoutés

### Backend Controller (routeOptimization.controller.ts)
```typescript
console.log('━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━')
console.log('📍 STAGES RECEIVED FOR OPTIMIZATION')
console.log('━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━')
for (const [index, stage] of stages.entries()) {
  const coords = stage.location?.coordinates
  const coordsStr = coords ? 
    `${coords.lat.toFixed(4)}, ${coords.lng.toFixed(4)}` : 
    '❌ MISSING'
  console.log(`${index + 1}. ${stage.name || stage.id}`)
  console.log(`   Location: ${stage.location?.address || 'NO ADDRESS'}`)
  console.log(`   Coordinates: ${coordsStr}`)
  if (!coords?.lat || !coords?.lng) {
    console.log('   ⚠️  WARNING: Missing or invalid coordinates!')
  }
}
```

**Validation:** Retourne 400 si stages invalides
```json
{
  "error": "Some stages are missing location coordinates",
  "invalidStages": [
    { "id": "abc123", "name": "Paris" }
  ]
}
```

---

### Backend Service (routeOptimization.service.ts)

#### Logs TSP algorithme:
```typescript
console.log(`   Current: ${current.name} (${lat}, ${lng})`)
console.log(`   Evaluating ${unvisited.size} candidates:`)
for (const candidate of unvisited) {
  const distance = calculateDistance(current, candidate)
  console.log(`     - ${candidate.name}: ${distance.toFixed(1)} km`)
}
console.log(`   ✓ Selected: ${nearest.name} (${minDistance} km away)`)
```

#### Logs rapport final:
```
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
📊 ROUTE OPTIMIZATION REPORT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
⏱️  Computation time: 15ms
🚗 Profile: balanced
📍 Stages: 5 (3 intermediate)

📏 DISTANCE:
   Original:  1850.00 km
   Optimized: 1785.00 km
   Saved:     65.00 km (3.5%)

⏰ DURATION:
   Original:  1110 min
   Optimized: 1071 min
   Saved:     39 min

💰 ECONOMICS:
   Fuel saved: 4.55 L
   Cost saved: 9.10 €
   CO₂ saved:  10.40 kg
```

---

## Comment tester maintenant

### 1. Créer un plan test avec détours volontaires
```
1. Paris (48.8566, 2.3522) - DÉPART FIXE
2. Marseille (43.2965, 5.3698) - Sud (660 km)
3. Lille (50.6292, 3.0573) - Nord (220 km) ← Détour!
4. Lyon (45.7640, 4.8357) - Sud-Est (392 km)
5. Bordeaux (44.8378, -0.5792) - ARRIVÉE FIXE
```

**Distance originale:**
```
Paris → Marseille: 660 km
Marseille → Lille: 880 km (énorme détour!)
Lille → Lyon: 560 km
Lyon → Bordeaux: 430 km
TOTAL: 2530 km
```

**Distance optimisée:**
```
Paris → Lille: 220 km (proche!)
Lille → Lyon: 560 km
Lyon → Marseille: 280 km
Marseille → Bordeaux: 510 km
TOTAL: 1570 km
━━━━━━━━━━━━━━━━
ÉCONOMIE: 960 km (38%) ← Grosse économie!
```

---

### 2. Ouvrir console backend
```bash
# Terminal 1 - Backend logs
cd apps/api
pnpm dev

# Terminal 2 - Frontend
cd apps/web
pnpm dev
```

---

### 3. Tester l'optimisation
1. Créer plan avec 5+ stages dans ordre illogique
2. Cliquer "Optimiser l'itinéraire"
3. **Regarder console backend** pour voir:
   - ✅ Coordonnées des stages reçues
   - ✅ Distances calculées entre chaque paire
   - ✅ Choix du stage le plus proche à chaque itération
   - ✅ Rapport final avec économies

---

### 4. Interpréter les résultats

#### ✅ Cas normal (ça marche):
```
📍 STAGES RECEIVED
1. Paris - Coordinates: 48.8566, 2.3522
2. Marseille - Coordinates: 43.2965, 5.3698
3. Lille - Coordinates: 50.6292, 3.0573

🔄 TSP Optimization:
   Current: Paris (48.86, 2.35)
   Evaluating 2 candidates:
     - Marseille: 660.3 km
     - Lille: 220.4 km
   ✓ Selected: Lille (220.4 km)

📊 ROUTE OPTIMIZATION REPORT
   Saved: 440 km (38%)
```

#### ❌ Cas problème #1 (pas de coordonnées):
```
📍 STAGES RECEIVED
1. Paris
   Coordinates: ❌ MISSING
   ⚠️  WARNING: Missing coordinates!

Response: 400 Bad Request
{
  "error": "Some stages are missing location coordinates",
  "invalidStages": [{"id": "abc", "name": "Paris"}]
}
```

#### ❌ Cas problème #2 (tous au même endroit):
```
📍 STAGES RECEIVED
1. Paris - Coordinates: 48.8566, 2.3522
2. Lyon - Coordinates: 48.8566, 2.3522 ← MÊME QUE PARIS!
3. Marseille - Coordinates: 48.8566, 2.3522 ← MÊME!

🔄 TSP Optimization:
   Evaluating candidates:
     - Lyon: 0.0 km ← PROBLÈME!
     - Marseille: 0.0 km ← PROBLÈME!

📊 ROUTE OPTIMIZATION REPORT
   Saved: 0 km (0%)
```

#### ℹ️ Cas normal (déjà optimal):
```
📍 STAGES RECEIVED (ordre logique)
1. Paris → 2. Lyon → 3. Marseille

🔄 TSP Optimization:
   Current: Paris
     - Lyon: 392 km (plus proche)
     - Marseille: 660 km
   ✓ Selected: Lyon

   Current: Lyon
     - Marseille: 280 km
   ✓ Selected: Marseille

📊 Saved: 0 km (0%) ← Normal! Déjà optimal
```

---

## Prochaines étapes si problème persiste

### Si stages sans coordonnées:
1. Vérifier frontend: comment sont créés les stages?
2. Vérifier si Mapbox Places API est appelé
3. S'assurer que `location.coordinates` est sauvegardé dans Firestore

### Si distances toutes à 0:
1. Bug dans calcul Haversine? (peu probable, formule standard)
2. Coordonnées swappées lat/lng?
3. Coordonnées en radians au lieu de degrés?

### Si pas d'économies malgré détours:
1. Vérifier que l'ordre optimisé est différent de l'ordre original
2. Calculer manuellement les distances avec Google Maps
3. Comparer avec résultat TSP

---

## Résumé des changements

| Fichier | Changement | But |
|---------|------------|-----|
| `routeOptimization.controller.ts` | Logs validation stages | Vérifier coordonnées présentes |
| `routeOptimization.controller.ts` | Return 400 si invalid | Erreur explicite côté frontend |
| `routeOptimization.service.ts` | Logs TSP détaillés | Voir décisions algorithme |
| `routeOptimization.service.ts` | Rapport économies | Confirmer que ça fonctionne |

**Status:** Ready to test - Les logs vont révéler le problème exact. 🔍
