局内配送车调度及其竞争算法

Scheduling for on-line distributing-truck problem and

经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解),其最优性在条件发生变化时就会失去.局内问题与竞争算法则是针对特定的优化问题提出一种策略,对已知条件变化的每一个特例都能给出一个方案,使得该方案的解离最优方案的解总在一定的比例之内.针对在一个有限网络上建立了s个配送中心,并且有k辆配送车进行服务的局内配送车问题,在时间目标函数下给出了当配送中心、配送车和需求点个数变化时的3种竞争算法.

Most traditional optimization theories produce the optimal solutions for problems at hand on the basis that the known conditions are unchanged, while their optimality may be lost in most cases with varying of conditions. The on_line problem and the competitive algorithm try to explore a strategy which can produce a solution that is in a certain range proportional to the optimal solution for a given problem even in the worst cases.In on_line distributing_truck problem with objective function of time, assuming that there are s distributing_centers and k distributing_trucks in the network, three competitive algorithms are given when the numbers of distributing_center, distributing_truck and demand_point are varied.