Das dynamische Travelling-Salesman Problem

Das TSP wird auf zeitabhängige Kosten und Wegelängen verallgemeinert, der Komplexitätstatus untersucht, verschiedene Formulierungen verglichen, Spezialfälle untersucht und ein auf Lagrange-Relaxation und Branch&Bound beruhendes exaktes Lösungsverfahren von Lucena erweitert, implementiert und getestet. Für das TDTSP wird die Dimension des ganzzahligen Polyeders bestimmt.

Metadaten
Author:	Martin C. Müller
URN:	urn:nbn:de:hbz:386-kluedo-10827
Document Type:	Diploma Thesis
Language of publication:	German
Year of Completion:	1996
Year of first Publication:	1996
Publishing Institution:	Technische Universität Kaiserslautern
Granting Institution:	Technische Universität Kaiserslautern
Date of the Publication (Server):	2000/12/05
Tag:	Lagrange; Lucena; Relaxation; TDTSP; TSP; kombinatorische Optimierung
Faculties / Organisational entities:	Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:	5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):	65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx]
	65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K10 Optimization and variational techniques [See also 49Mxx, 93B40]
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
Licence (German):	Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011