operations_research/bilder_04/erzeuge_vrp_subtours.py

#!/usr/bin/env python3

# erzeuge_vrp_subtours.py
"""
Erzeugt das Kurzzyklus-Diagramm zum Graphen-Kapitel:

    bilder_04/kap_graphen_subtouren.svg

Links, was ein Tourenmodell OHNE Kurzzyklus-Bedingungen zurueckgeben darf:
Jeder Kunde hat genau einen Vorgaenger und einen Nachfolger - alle
Gradbedingungen sind erfuellt -, und trotzdem ist die Loesung unbrauchbar, weil
die Fahrzeuge nie am Depot vorbeikommen. Rechts dieselbe Instanz mit gueltiger
Rundreise ab und bis Depot.

Der Punkt: Das linke Bild ist kein Rechenfehler. Es erfuellt jede Bedingung,
die naiv formuliert wurde. Was fehlt, ist eine Bedingung, an die man beim
Aufschreiben nicht denkt - und genau dafuer gibt es MTZ.

Die Instanz stammt aus erzeuge_vrp_touren.py, also aus demselben Datensatz wie
das Buchprogramm. Die Kurzzyklen links sind daraus konstruiert: Es sind die
Kundenfolgen der gueltigen Loesung, nur ohne das Depot geschlossen. So zeigt
das Bild denselben Fall und nicht ein zweites, erfundenes Beispiel.

Aufruf (aus dem Repository-Wurzelverzeichnis):
    python3 bilder_04/erzeuge_vrp_subtours.py

Benoetigt: numpy, matplotlib, ortools
"""

from __future__ import annotations

import os
import sys

import numpy as np

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from stil_04 import FARBEN, speichere                     # noqa: E402
import matplotlib.pyplot as plt                           # noqa: E402
from erzeuge_vrp_touren import (TOURFARBEN, erzeuge_daten,  # noqa: E402
                                loese)


def kurzzyklen(touren) -> list[list[int]]:
    """Aus jeder gueltigen Tour einen Kreis ohne Depot machen.

    Genau das darf ein Modell liefern, das nur 'jeder Kunde einmal angefahren'
    fordert: In sich geschlossene Kreise, die das Depot nie beruehren."""
    aus = []
    for tour in touren:
        kunden = [k for k in tour["stationen"] if k != 0]
        if len(kunden) >= 2:
            aus.append(kunden + [kunden[0]])
    return aus


def pruefe_grade(zyklen, anzahl_kunden: int) -> None:
    """Die unzulaessige Loesung muss die Gradbedingungen trotzdem erfuellen."""
    besucht = [k for z in zyklen for k in z[:-1]]
    if sorted(besucht) != list(range(1, anzahl_kunden + 1)):
        raise SystemExit(
            "Subtour-Bild: Die konstruierten Kurzzyklen besuchen nicht jeden "
            "Kunden genau einmal. Dann waere das linke Bild kein gueltiges "
            "Gegenbeispiel, sondern einfach falsch.")


def zeichne(koordinaten, touren, zyklen) -> None:
    figur, achsen = plt.subplots(1, 2, figsize=(9.6, 4.6), sharex=True,
                                 sharey=True)

    for achse, titel in ((achsen[0], "ohne Kurzzyklus-Bedingungen"),
                         (achsen[1], "mit MTZ — jede Tour über das Depot")):
        for ort in range(1, len(koordinaten)):
            achse.scatter(*koordinaten[ort], s=34, color=FARBEN["text"],
                          zorder=3)
        achse.scatter(*koordinaten[0], marker="s", s=150,
                      color=FARBEN["fehler"], zorder=4)
        achse.annotate("Depot", koordinaten[0], textcoords="offset points",
                       xytext=(9, 7), fontsize=9, color=FARBEN["fehler"],
                       fontweight="bold")
        achse.set_xlabel("km")
        achse.set_title(titel, fontsize=10.5, color=FARBEN["text"])

    # links: die Kurzzyklen
    for nummer, (zyklus, farbe) in enumerate(zip(zyklen, TOURFARBEN), start=1):
        weg = koordinaten[zyklus]
        achsen[0].plot(weg[:, 0], weg[:, 1], "-", color=farbe, linewidth=1.8,
                       alpha=0.9, zorder=2)
    achsen[0].annotate(
        "Jeder Kunde hat genau einen Vor- und\n"
        "einen Nachfolger — und kein Fahrzeug\n"
        "kommt je am Depot vorbei.",
        xy=(0.03, 0.03), xycoords="axes fraction", fontsize=9,
        color=FARBEN["fehler"], va="bottom")

    # rechts: die gueltige Loesung
    for tour, farbe in zip(touren, TOURFARBEN):
        weg = koordinaten[tour["stationen"]]
        achsen[1].plot(weg[:, 0], weg[:, 1], "-", color=farbe, linewidth=1.8,
                       alpha=0.9, zorder=2)

    achsen[0].set_ylabel("km")
    figur.suptitle("Warum Gradbedingungen allein nicht genügen",
                   fontsize=11, color=FARBEN["text"], y=1.01)
    speichere(figur, "kap_graphen_subtouren")


if __name__ == "__main__":
    koordinaten, distanz = erzeuge_daten()
    touren = loese(distanz)
    zyklen = kurzzyklen(touren)
    pruefe_grade(zyklen, len(koordinaten) - 1)
    print(f"  {len(zyklen)} Kurzzyklen konstruiert, "
          f"{sum(len(z) - 1 for z in zyklen)} Kunden — jeder genau einmal.")
    zeichne(koordinaten, touren, zyklen)