Wenn linienmäßig, dann ist eh klar, dass wir nur die Strecken fahren können, die befahren werden.
Mittlerweile habe ich eine Lösung gefunden. Es gibt einen Algorithmus dafür, der sich in der Graphentheorie das "Briefträgerproblem" (chinese postman problem) nennt. Dazu geht man im gerichteten (gewichtet durch die Fahrzeiten zwischen den Knoten) Graphen die minimale Kantenfolge mind. einmal durch (manche Strecken werden sicher mehrmals befahren werden müssen).
Das Problem ist glücklicherweise in polynomieller Zeit lösbar.
Ich habe im Moment leider keine Zeit dafür, aber ich werds mir hoffentlich recht bald mal ansehen können, ob wir eine gute Lösung finden. Ob es dann wirklich die optimale Lösung ist, kann man nur schwer beweisen. Vor allem, weil es ja auch noch Betriebsverbindungen und diese Sonderstrecken gibt, die das ganze sehr sehr aufwändig machen. Da müsste man mehrere Varianten durchrechnen und schauen, ob sich damit etwas verkürzen lässt.
