Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum Diskrete Optimierung (Modul P2C1)
Sommersemester 2017
Thema: Tourenplanung
Thema dieses Programmierpraktikums ist die Implementierung von
Algorithmen für die Tourenplanung (engl. Vehicle Routing Problem (VRP)),
welche in der Logistik eine große Rolle spielen aber auch im Chip-Design vorkommen.
Eine kurze Beschreibung des Problems und der Aufgaben finden Sie
hier.
Vorbesprechung:
Dienstag, 7. Februar, 2017, 18 Uhr s.t.
im Seminarraum des Forschungsinstituts für Diskrete Mathematik, Lennéstraße 2
Testinstanzen
Alle Instanzen liegen im sogenannten TSPLIB-Format vor,
wobei wir uns auf geometrische Instanzen in der Ebene beschränken.
Für erste Versuche eignen sich die kleinen Testinstanzen, die sich
auch noch von Hand lösen lassen.
Später sollten die Algorithmen auch auf den VLSI-Instanzen Ergebnisse liefern.
Kleine CVRP Benchmarks z.T. mit Optimallösungen.
VLSI Instanzen (Scan-Ketten Optimierung)
Abgabetermin der Einführungsaufgabe: 30.04.2017.
(per E-Mail an den Betreuer)
Abgabetermin der Abschlussaufgabe: 23.07.2017.
(per E-Mail an den Betreuer)
Vorstellung der Ergebnisse:
Am Ende des Semesters muss jeder Teilnehmer seine Implementierung im
Rahmen eines Blockseminars vorgestellen.
Hierbei sollen in 15 Minuten (12 Minuten Vortrag + 3 Minuten Diskussion) der
Algorithmus, die interessantesten Code-Fragmente, sowie experimentelle
Ergebnisse vorgestellt werden.
Voraussichtlicher Termin für das Blockseminar ist der 28.07.2017.
Ort: Seminarraum Diskrete Mathematik.
Prof. Dr.
B. Korte,
Prof. Dr.
J. Vygen,
Prof.
Dr. S. Hougardy,
Prof.
Dr. S. Held,
Dr. U.
Brenner