Combinatorial online optimization in real time
An online optimization problem occurs when a decision has to be met before all data of the problem are known. In a real-time optimization problem the decisions have to be computed within tight time bounds. This paper surveys combinatorial online and real-time optimization. Concepts are discussed which allow to analyze online and real-time algorithms. In particular the sequence model and the time stamp model are discussed. In the sequence model requests have to be served immediately in the order of their occurences. In the time stamp model a decision at time \(t\) can be based on all requests released up to time \(t\), one may wait and can also revoke earlier decisions (which increases costs). The competitive analysis compares an online algorithm with an optimal offline algorithm. As the competitive analysis is overly pessimistic, certain possible alternatives are outlined. The paper surveys also real time decision support systems, in particular in the context of local transportation systems. Moreover, approximation algorithms are addressed and general purpose heuristics for online optimization are described. These comprise first-in-first-out strategies, greedy algorithms, replanning and the ignore-strategy. For the entire collection see [Zbl 0971.00007].
- Online decision making and automatic decision model adaptation
- Evaluating the quality of online optimization algorithms by discrete event simulation
- An algorithm with performance guarantee for the online container relocation problem
- Ronald Graham: laying the foundations of online optimization
- Online stochastic optimization under time constraints
- The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments
- Online-optimization of multi-elevator transport systems with reoptimization algorithms based on set-partitioning models
- Combinatorial online optimization
- scientific article; zbMATH DE number 797445 (Why is no real title available?)
- Amsaa: A Multistep Anticipatory Algorithm for Online Stochastic Combinatorial Optimization
- Logistics in real time inventory routing operations under stochastic demand
- Online optimization: probabilistic analysis and algorithm engineering
- Railway crew planning with fairness over time
- A neural-tabu search heuristic for the real time vehicle routing problem
This page was built for publication: Combinatorial online optimization in real time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2762577)
