Übung vom 15.03.2013
Übung
Laden Sie sich Beispielinstanzen für das TSPTW
hier
Schreiben Sie ein Programm, welches eines dieser Probleme einliest (egal welches) und danach den in der Vorlesung besprochenen backtracking-Algorithmus umsetzt, um eine gültige Lösung zu erzeugen. Dafür werden Job-Objekte benötigt, die folgende Parameter besitzen:
- int earliest_start
- int latest start
- in location_id
- int id
Neben den Jobs muss auch die Entfernungsmatrix aus der Datei eingelesen werden. Sie soll als zweidimensionales Array int[,] repräsentiert werden.
Die TSPTW-Instanzen sind folgendermaßen aufgebaut:
Zeile 1: Anzahl der Jobs
Zeile 2 - Zeile <Anzahl der Jobs>: Entfernungsmatrix
Ab Zeile <Anzahl der Jobs>: Zeitfenster der Jobs
Die Reihenfolge der Zeitfenster entspricht dabei der Jobnummer und der Reihenfolge der Einträge in der Entfernungsmatrix. Das heißt, zu Job 3 gehören die Einträge in der dritten Zeile und der dritten Spalte der Matrix.
C#-Codeschnipsel