用于一般指派问题的禁忌搜索算法 http://www.paper.edu.cn 窦晖 兰州交通大学交通运输学院，甘肃兰州 (730070） E-mail : huihui5027@163.com 摘 要：本文研究了日常生活中常遇到的指派问题，并针对其特点，建立指派问题的数学模 型。运用禁忌搜索算法来求解模型的最优解，通过对具体指派问题算例的仿真实现，说明禁 忌搜索算法是可行和有效的。 关键词：禁忌搜索；指派问题；禁忌表；全局优化 中图分类号：C93 1. 引 言 指派问题是将若干个体分配到若干位置，并求一个线性费用函数的最小值。在生产管理 中，决策者总是希望能够把人员进行最佳分配。由于任务的性质和每个人的知识、能力、经 验等各不相同，各人去完成各项不同任务的效益（所费时间或所花费用）就有差别。那么这 m 项任务究竟该如何分配给 n 个人去完成使最后的总花费最少，所有任务的总效益最大呢？ 这就是标准的指派问题。这类问题的效率矩阵中的元素均为确定的量。针对这类组合优化问 题,解决方法可有许多种启发式方法。其中，禁忌搜索(tabu search)是局部领域搜索算法的推 广，是人工智能在组合最优化算法中的一个成功应用，其特点是采用了禁忌技术，能够避免 陷入局部最优，在短时间内找到全局最优解[1]。 2. 指派问题描述 在生活中，一般的指派问题是指，有 n 个人，m 项工作（m ≤ n），一个人最多只能干 一项工作，一项工作只能一个人干，找任务的最优分配方案，使总费用最小[2]。 一般指派问题可以表示为以下形式的 0-1 整数线性规划问题： min n m ∑∑ i 1 = j 1 = ij xc ij (1) s.t. n =∑ x ij i 1 = m ,1 j ,2,1 L= , m (2) x ij , n ,1 i ,2,1 L= (3) ≤∑ j 1 = } { xij ,1,0 (4) nm ≤ (5) ,2,1 ,2,1 jn , L , m L ∈ i = = , ijc ——第i 个人干第 j 项工作的费用 当且仅当 1=ijx 时，表示第i 个人被分配做第 j 项工作，否则， 0=ijx 。方程(1)即为 目标函数，求最小的费用；方程(2)表示的是每个人只能做一项工作；方程(3)表示的是每项 工作最多由一个人来完成；方程(4)、(5)则表示的是对决策变量的 0-1 整数约束，并说明人 - 1 - 

http://www.paper.edu.cn 数要多于工作的数目。 3. 禁忌搜索算法 3.1 算法的基本思想 禁忌搜索(TS)是一种模仿人类智力过程的亚启发式(meta-heuristic)搜索技术，由 Glover 教授在 1986 年首先提出，进而形成一套完整算法，并成功应用于复杂组合优化问题的求解 [3]。 禁忌搜索算法中充分体现了集中和扩散两个策略。它的集中策略体现在局部搜索，即从 一点出发，在这点的领域内寻求更好的解，以达到局部最优解而结束。为了跳出局部最优解， 扩散策略通过禁忌表的功能来实现。禁忌表中记录下已经到达点的某些信息，算法通过对禁 忌表中点的禁忌，而达到一些没有搜索的点，从而实现更大区域的搜索。因此，在求解一些 最优化问题时，在获得解的所需时间及解的准确性方面，禁忌搜索算法的性能都优于一些算 法。 构造禁忌搜索算法的一些基本要素： （1）目标函数：明确所要解决的问题，构造对应的函数。 （2）邻域(候选集合)：当前解可以搜索取值的范围。 （3）禁忌表：计算过程中用于记忆的一张表，被禁忌的活动放在这张表中。 （4）特赦规则：在禁忌搜索算法的迭代过程中，会出现候选集中的全部对象被禁，或 一对象被禁但若解禁后其当前最优值将更优的情况。在这样的情况下，为了达到全局的最优， 我们制定一些优先的规则，让一些禁忌对象重新可选。 3.2 算法的基本步骤 禁忌搜索算法的一般步骤如下[4]： STEP 1 给以禁忌表 H=∅ ,并选定一个初始解 nowx ； STEP 2 满足停止规则时，停止计算，输出结果；否则，在 ( _ now Can N x ；在 满足不受禁忌的候选集 nowx := nextx 更新历史记录 H,重复 STEP2 。 4. 对于指派问题的禁忌搜索求解 ) nowx 的邻域 ( Can N x 中选一个评价值最佳的解 now _ ( ) ) now N x 中选出 nextx ， 4.1 算法实现 对于指派问题的禁忌搜索算法实现流程如图 1 所示。 - 2 - 

http://www.paper.edu.cn 图 1 禁忌搜索算法流程 - 3 - 

4.2 仿真实验 利用下面一个具体的简单例子来说明禁忌搜索算法对于指派问题的求解。 现有四个人，三项工作，且一个人最多只能干一项工作，一项工作只能由一个人来干， 找其最优的任务分配方案使总费用最小。对应的费用矩阵为： http://www.paper.edu.cn ijc )= D=( 1232 2213 2321 ⎡ ⎢ ⎢ ⎢ ⎣ ⎤ ⎥ ⎥ ⎥ ⎦ （1）考虑目标函数 指派问题的目标是任务分配后，所花费的总费用最小。我们首先设定一个初始解，前三 个人依次做前三项工作，第四个人空闲。1 表示有任务，0 则无任务。以行、列分别表示工 作和人的初始单位矩阵如下： 1 0 0 ⎡ ⎢ ⎢ ⎢ ⎣ 0 1 0 0 0 1 0 0 0 ⎤ ⎥ ⎥ ⎥ ⎦ （2） 邻域构造 在求解之前，我们首先要考虑此问题的邻域构造。第一种方法的基本思想是：通过交换 交错偶圈或交错路上的边得到。第二种方法是：随机选择两个任务指派，交换相关的两个人 所完成的任务。 本文随机选取两个人并交换任务，随机选取的次数为 10 次，即为本例题的邻域。 （3） 禁忌表 每交换一次任务，记录一次费用总和，在一个邻域范围内寻找最小的费用，并将其禁忌， 即放入一个充当禁忌表的一维数组中。针对本题的规模，将禁忌长度定为 3 。 对于此问题，邻域为 10，搜索为 300 次用 C 语言编程在计算机上求解，所得的结果如 表 1 所示。 项目 1 项目 2 项目 3 工人 1 表 1 仿真结果 工人 2 工人 3 工人 4 0 0 1 0 1 0 0 0 0 1 0 0 从上面的结果可以看出，经过禁忌搜索算法求解，得到的最优指派方案为： 项目 1：由工人 4 来完成； 项目 2：由工人 2 来完成； 项目 3：由工人 1 来完成。 - 4 - 

http://www.paper.edu.cn 5. 结 论 本文提出了一种用于求解指派问题的禁忌搜索算法，并对这种求全局最优的方法的性能 用数值例子进行了验证。仿真结果表明，禁忌搜索算法具有很快的搜索速度和优良的求解质 量，具有一定的通用性。 参考文献 [1] 冯媛. 一类模糊指派问题及其禁忌搜索算法[J]. 北京石油化工学院学报,2004(9):20-23. [2]王东平,李绍荣. 模糊禁忌搜索算法用于求解分配问题[J]. 计算机科学,2003(7):29-31. [3]贺一,邱玉辉,刘光远,曾绍华. 多维背包问题的禁忌搜索求解[J]. 计算机科学,2006(9):18-20. [4]刘宝碇,赵瑞清,王纲. 不确定规划及应用[M]. 北京:清华大学出版社,2003,156-160. Tabu Search Algorithm of General Assignment Problems School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou (730070) Dou Hui Abstract In this paper the often encountered in daily life assignment problem is described and according to its characteristics build its mathematical model. Tabu search algorithm used to solve the model of the optimal solution. According to implement and test the algorithm on classical instances, prove the tabu search algorithm is feasible and effective. Keywords: Tabu search algorithm; Assignment problem; Tabu list; Overall optimization 作者简介： 窦晖 女, 出生年月 1 984 年 1 月 山东省临沂人, 兰州交通大学交通运输学院，兰州交通大 学 交通运输规划与管理 06 级硕士。 - 5 -