Refine
Year of publication
Document Type
- ZIB-Report (29)
- Article (6)
- In Proceedings (4)
- Book chapter (2)
- Doctoral Thesis (1)
Is part of the Bibliography
- no (42)
Keywords
- real-time (5)
- ADAC (4)
- competitive analysis (4)
- soft time windows (4)
- triangulation (4)
- vehicle dispatching (4)
- Generalized Baues Problem (3)
- Online Optimization (3)
- column generation (3)
- elevator (3)
Institute
- ZIB Allgemein (29)
- Mathematical Optimization (11)
Wo bleibt der Aufzug?
(1999)
Wo bleibt der Aufzug?
(2006)
Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield.
Making the Yellow Angels Fly
(2002)
Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.
In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis.
Euler is Standing in Line
(1999)
In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$.