Wir berichten über eine experimentelle Studie zu lokalen Suchverfahren für das Pairing-Problem bei Fluggesellschaften unter Benutzung realer Testdatensätze mit bis zu 4600 Fl"ugen kurzer Reichweite. Unter einer Run-Cutting Formulierung vergleichen wir Verfahren wie Simulated Annealing, Modifikationen der Wasserspiegel-Algorithmen nach Dueck, eine elementare Implementation von Tabu Suche sowie einen GRASP Ansatz. Es zeigt sich, da"s die Wasserspiegel-Algorithmen vergleichbare Ergebnisse wie Simulated Annealing, und um etwa 40% bessere Ergebnisse als blo"se lokale Verbesserungsheuristiken liefern, w"ahrend Tabu Suche und GRASP hier ungeeignet erscheinen. Die Ergebnisse von Simulated Annealing und der Wasserspiegel-Algorithmen k"onnen sich auch mit den LP-Schranken f"ur die SET PARTITIONING Formulierung mit Packungsungleichungen und bis zu 3.9 Millionen Spalten messen. Eine Clustering-Parallelisierung des Simulated Annealings auf einem Parallelrechner GigaCluster PowerPlus weist eine sehr gute Beschleunigung auf. / For the airline pairing problem using a run-cutting formulation. Computational results are reported for some real-world short-haul testproblems with up to 4600 flights per month. In particular, we evaluate the relative performance of simulated annealing, modified versions of the waterlevel algorithms proposed by Dueck, an elementary tabu search, and a GRASP approach. We find that the waterlevel algorithms compare well with simulated annealing and both improve on mere improvement heuristics by about 40%. Tabu search and GRASP do not yield competitive results here. Simulated annealing and the waterlevel algorithms also compare favourably with LP-bounds for a SET PARTITIONING formulation with knapsack constraints containing up to 3.9 million columns. A clustering parallelization of simulated annealing on a GigaCluster PowerPlus parallel computer exhibits an excellent speed-up.
| Identifer | oai:union.ndltd.org:HUMBOLT/oai:edoc.hu-berlin.de:18452/15006 |
| Date | 29 January 1999 |
| Creators | Emden-Weinert, Thomas |
| Publisher | Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Source Sets | Humboldt University of Berlin |
| Language | German |
| Detected Language | English |
| Type | doctoralThesis, doc-type:doctoralThesis |
| Format | application/postscript |
Page generated in 0.0031 seconds