单车场多送货点车辆调度优化的一种改进禁忌算法

An Improved Tabu Search Algorithm(TS) for the Single-depot Vehicle Scheduling Problem

为解决单车场容量约束车辆调度问题提出了一种改进禁忌算法。在传统的禁忌算法思想中,它的解受算法的唯一初始解的状态影响很大,因此优化结果的稳定性得不到保证。此改进算法使用多初始解和全局禁忌表,它能够减小解的不稳定性和扩大搜索范围。与标准禁忌算法比较,它的全局搜索能力和稳定性都大大增强。通过算例试验,取得了良好的结果。

In order to solve the single-depot and capacity constraint vehicle-scheduling problem, an improved tabu-searching algorithm （TS） is presented in the paper. For a traditional TS algorithm, its solution was greatly influenced by the state of the only initial solution of the algorithm, and the stability of optimal solution cannot be guaranteed. In this paper, a multi-initial-solution and global tabu table is used in the algorithm to increase the stability and enlarge the search scopes. Compared with the standard TS, the proposed TS algorithm has greatly increased its global search ability and stability. Finally, the paper gives some examples and shows good results from these experiments.