90B06 Transportation, logistics
Refine
Document Type
- ZIB-Report (14)
Has Fulltext
- yes (14)
Is part of the Bibliography
- no (14)
Keywords
- real-time (5)
- ADAC (4)
- competitive analysis (4)
- soft time windows (4)
- vehicle dispatching (4)
- Online Optimization (3)
- elevator (3)
- online (3)
- online optimization (3)
- branch and bound (2)
- column generation (2)
- combinatorial optimization (2)
- pricing (2)
- real world data (2)
- real-world problems (2)
- Aufzüge (1)
- Competitive Analysis (1)
- Echtzeit-Optimierung (1)
- Heuristics (1)
- Hochregallagerbediengeräte (1)
- Kommissioniermobile (1)
- Kompetitive Analyse (1)
- Logistik (1)
- Online Algorithmen (1)
- Online Optimierung (1)
- Online optimization (1)
- Online-Optimierung (1)
- Realtime Optimization (1)
- Simulation (1)
- Survey (1)
- competitiveness (1)
- elevator group control (1)
- high load (1)
- kompetitive Analyse (1)
- lower bounds (1)
- optimality gap (1)
- policy (1)
- randomized algorithms (1)
- reoptimization (1)
- simulation (1)
- simulation studies (1)
Institute
- ZIB Allgemein (14)
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.
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.
This paper gives a short introduction into combinatorial online optimization. It explains a few evaluation concepts of online algorithms, such as competitiveness, and discusses limitations in their application to real--world problems. The main focus, however, is a survey of combinatorial online problems coming up in practice, in particular, in large scale material flow and flexible manufacturing systems.
In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material.