局内车辆选线问题和竞争策略分析

Scheduling for on-line routing problem and its competitive strategy analysis

将现实物流配送中所遇到的问题抽象为一个局内车辆选线问题,考虑堵塞点动态产生、一个个遇到的情况下的车辆调度方案.经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解),在条件发生变化时就会失去其最优性.而论文所考虑的竞争算法能使得调度方案对于变化因素的每一个特例得到的解离最优方案给出的解总在一定范围之内.不仅设计了解决局内车辆选线问题的竞争算法:贪婪策略和复位策略,分析了不同情况下算法各自的竞争比,而且给出了此问题的竞争比下界.

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 online 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 online scheduling of shortest path problem, analyzing their competitive ratios in different situations. Finally, the lower bound of the problem is discussed.