Scheduling for on-line routing problem and its competitive strategy analysis
Zhi Hong Zhu · Journal of systems engineering · 2003
The paper abstracts the concrete problem in logistics to an on_line problem. The solution for routing is considered when the congested vertex is met one by one. Most traditional optimization theories produce the optimal solutions for problems at hand on the basis that the known conditions are unchanged, which may lose their optimality in most cases when conditions vary. The researches on online problem and competitive algorithm try to explore strategies which can produce solutions that is in a certain range proportional to the optimal solution for a given problem even in worst cases. This paper gives the greedy strategy and the reposition strategy for online scheduling of shortest path problem, analyzing their competitive ratios in different situations. Finally, the lower bound of the problem is discussed.