## Ersatzplanung für ein Lieferfahrzeug

Ein Kurierdienst braucht für die nächsten drei Jahre ein Lieferfahrzeug. Danach stellt er auf eine gemietete Elektroflotte um, das Fahrzeug wird dann nicht mehr benötigt. Weil das Fahrzeug im Stadtverkehr stark beansprucht wird, steigen Reparatur- und Betriebskosten mit dem Alter deutlich an. Es kann sich deshalb lohnen, das Fahrzeug nach einem und/oder nach zwei Jahren gegen ein neues gleichen Typs auszutauschen.

Die folgende Kostenmatrix C gibt an, welche Kosten (Wertverlust, Reparatur- und Betriebskosten, in Tausend Euro) entstehen, wenn am Ende von Jahr i = 0,1,2 (also zu Beginn von Jahr i+1) ein neues Fahrzeug gekauft und bis zum Ende von Jahr j = 1,2,3 genutzt wird.

Zu welchen Zeitpunkten sollte das Fahrzeug gegebenenfalls ersetzt werden, damit die Fahrzeugkosten der nächsten drei Jahre möglichst gering sind?

|   i \ j | 1   | 2   |   3 |
|---------|-----|-----|-----|
|       0 | 8   | 18  |  31 |
|       1 | -   | 10  |  21 |
|       2 | -   | -   |  12 |

- a) Beschreiben Sie die Situation als Kürzeste-Wege-Problem und zeichnen Sie den zugehörigen Graphen!
- b) Bestimmen Sie die Lösung mit dem Dijkstra-Algorithmus!
