Chinese Postman Problem Solver

Eine Python-Anwendung zur Lösung des Chinese Postman Problems mit interaktiver Karteneingabe und Visualisierung der optimalen Tour.

🎯 Überblick

Dieses Projekt ermöglicht es, das Chinese Postman Problem auf realen Kartendaten zu lösen. Sie können:

• Interaktiv Knoten und Kanten auf einer Karte setzen
• Automatische Berechnung der kürzesten Tour, die alle Kanten mindestens einmal durchläuft
• Wahlweise offene oder geschlossene Touren berechnen
• Georeferenzierung mit GPS-Koordinaten
• Performance-Monitoring und -Analyse
• Automatische Backup-Verwaltung

🚀 Features

• Interaktive Karteneingabe: Klicken Sie Knoten und Kanten direkt auf Ihre Karte
• Georeferenzierung: JSON-basierte Konfiguration mit GPS-Koordinaten
• Algorithmische Optimierung:
  • Chinese Postman Algorithmus für Eulersche Touren
  • Minimum Weight Perfect Matching für ungerade Knoten
  • Dijkstra für kürzeste Pfade
• Performance-Monitoring: Detaillierte Zeitmessungen und Speicheranalyse
• Flexible Konfiguration: JSON-basierte Einstellungen für Transformation und Visualisierung
• Automatische Backups: Alle Änderungen werden automatisch gesichert

📦 Installation

Voraussetzungen

• Python 3.8 oder höher
• pip für Paketinstallation

Dependencies installieren

pip install -r requirements.txt

Hauptabhängigkeiten:

• numpy - Numerische Berechnungen
• pandas - Datenverarbeitung
• matplotlib - Visualisierung
• networkx - Graph-Algorithmen
• scikit-image - Bildverarbeitung und Transformationen
• pyproj - GPS-Koordinatentransformationen
• psutil - Systemressourcen-Monitoring

🎮 Verwendung

1. Grundsetup

1. Legen Sie Ihre Kartendatei als karte.png im Projektverzeichnis ab
2. Führen Sie das Hauptskript aus:

python map2graph2tour.py

2. Interaktive Bedienung

Knoten setzen:

• Linksklick: Neuen Knoten hinzufügen
• Rechtsklick: Letzten Knoten entfernen
• Fenster schließen: Weiter zu Kanten

Kanten zeichnen:

• Linksklick auf Startknoten: Kantenzeichnung beginnen
• Linksklick auf Zielknoten: Endpunkt festlegen
• Weitere Linksklicks: Zwischenpunkte setzen
• Rechtsklick: Kante speichern
• Rechtsklick ohne aktive Kante: Letzte Kante entfernen

3. Konfiguration

Bearbeiten Sie karte.json für erweiterte Einstellungen:

{
  "map_info": {
    "filename": "karte.png",
    "ellipsoid": "WGS84"
  },
  "reference_points": [
    {
      "name": "Nordwest-Referenzpunkt",
      "pixel_coords": [110, 29],
      "gps_coords": [50.131174, 8.655728]
    }
  ],
  "transformation": {
    "method": "affine",
    "fallback_method": "linear"
  }
}

🔧 Konfiguration

Tourtypen

Ändern Sie in map2graph2tour.py:

OPEN_TOUR = True   # Offene Tour (Start ≠ Ziel)
OPEN_TOUR = False  # Geschlossene Tour (Rundweg)

Georeferenzierung

Lineare Transformation (2 Punkte):

• Nur Skalierung und Translation
• Schnell, aber weniger präzise

Affine Transformation (3+ Punkte):

• Rotation, Skalierung, Translation
• Präziser, aber aufwändiger

📊 Ausgabedateien

• nodes.csv: Knoten mit Pixel- und GPS-Koordinaten
• edges.csv: Kanten mit Pfaden und Längen
• postman_tour.png: Visualisierung der berechneten Tour
• backup/: Automatische Sicherungen aller Änderungen

🎨 Visualisierung

Die generierte Tour zeigt:

• Schwarze Punkte: Knoten mit IDs
• Blaue Linien: Ursprüngliche Kanten
• Rote Linien mit Pfeilen: Berechnete Tour-Reihenfolge
• Rote Zahlen: Schritt-Nummern der Tour

⚡ Performance-Features

Das System bietet umfassendes Performance-Monitoring:

• Automatisches Profiling wichtiger Funktionen
• Speicher-Monitoring während der Ausführung
• Progress-Tracking für lange Operationen
• Benchmark-Tools für Algorithmus-Vergleiche

# Beispiel Performance-Ausgabe
Performance: chinese_postman_algorithm took 2.347s, Memory: 145.2MB (12.3%)
Dijkstra-Pfade: 15/15 (100.0%, 1.2s)
Komplexes Matching berechnet in 0.89s

🛠️ Erweiterte Features

Backup-System

Alle Dateien werden automatisch gesichert:

• Format: datei_YYYYMMDD_HHMMSS.extension
• Speicherort: backup/ Ordner
• Keine Überschreibung existierender Backups

Multi-Ellipsoid-Support

Unterstützte Koordinatensysteme:

• WGS84 (Standard, global)
• NAD83 (Nordamerika)
• ETRS89 (Europa)
• Weitere über pyproj

📈 Algorithmus-Details

Chinese Postman Algorithmus

1. Eulersch? Prüfung auf gerade Knotgrade
2. Ungerade Knoten finden und Minimum Weight Perfect Matching
3. Pfad-Duplikation für Eulersche Eigenschaft
4. Tour-Berechnung via Eulerscher Pfad/Kreis

Komplexität

• Zeitkomplexität: O(V³) für das Matching
• Speicherplatz: O(V²) für Distanzmatrizen
• Praktisch: Effizient bis ~1000 Knoten

🐛 Troubleshooting

Häufige Probleme

Transformation schlägt fehl:

Fehler: Nicht genügend Referenzpunkte
→ Mindestens 2 GPS-Referenzpunkte in karte.json erforderlich

Tour kann nicht berechnet werden:

Fehler: Graph ist nicht zusammenhängend
→ Alle Knoten müssen über Kanten erreichbar sein

Performance-Probleme:

→ Weniger Zwischenpunkte bei Kanten verwenden

Debug-Modus

Aktivieren Sie detailliertes Logging:

import logging
logging.basicConfig(level=logging.DEBUG)

🤝 Mitwirken

Beiträge sind willkommen!

1. Forken Sie das Repository
2. Erstellen Sie einen Feature-Branch
3. Implementieren Sie Ihre Änderungen
4. Fügen Sie Tests hinzu
5. Erstellen Sie einen Pull Request

Code-Standards

• Typ-Hints für alle Funktionen
• Docstrings im Google-Format
• Performance-Profiling für kritische Funktionen
• Automatische Backups für alle Dateischreiboperationen

🙏 Danksagungen

• NetworkX für die hervorragenden Graph-Algorithmen
• Matplotlib für die Visualisierung
• pyproj für präzise Koordinatentransformationen

📞 Support

Bei Fragen oder Problemen:

1. Überprüfen Sie die Issues
2. Erstellen Sie ein neues Issue mit:
   • Detaillierter Problembeschreibung
   • Reproduktionsschritten
   • Systemkonfiguration
   • Log-Ausgaben

---

Viel Erfolg bei der Routenoptimierung! 🗺️✨