第二章 禁忌搜索算法概要

基于禁忌搜索算法求解定位－运输路线安排问题林晖钢1，胡大伟1，徐丽蕊1，21 长安大学汽车学院，西安（710064）2 陕西工业职业技术学院工商管理系，陕西咸阳（712000）E-mail ：lhgzhl@摘要：定位—运输路线安排问题（location routing problems, LRP）是集成化物流系统分销网络设计和管理决策中的难题，也是任何一个大型物流配送企业必须要面对的问题。

由于LRP 的NP—HARD属性，其求解方法目前大多局限在将定位—配给问题（location allocation problems, LAP）的输出作为车辆路线安排问题（vehicle routing problems, VRP）的输入而求解。

然而，在LAP 最优的前提下求出的VRP 的最优并不一定就是LRP 的最优解，从而导致这样的处理方式不可避免的会陷入局部最优解的状态。

本文针对多站点定位—运输路线安排问题（multi-depot location routing problems, MDLRP）数学模型，用Lingo 软件对小规模测试数据情形进行了验证, 然后采用禁忌搜索法(TS）分别求解LAP 和对应的每一个设施的VRP ，并将VRP 的结果作为LAP 的输入，再将LAP 解及其邻域解作为VRP 输入不断反复循环求解MDLRP ，并在此基础上对较大规模测试数据进行了仿真运算。

结果表明采用禁忌搜索方法求解一定规模的MDLRP 快速有效。

关键词：定位—运输路线安排问题；定位—配给问题；车辆路线问题；禁忌搜索1. 引言设施定位、车辆路线各自作为单独的问题，国内外已有较多学者进行了研究，其理论也已比较完善，这些研究为物流管理的优化决策奠定了坚实的基础。

国外一批学者对LRP 进行了一系列的研究[1]。

LRP 的概念认为：在设施（制造厂、库存点或分销中心）相对于客户的位置、货物的配给、货物运输的车辆路线安排之间存在相互依赖的关系，根据这种关系来进行综合优化与管理；相比单一的物流系统优化问题，LRP 更加贴近目前物流系统复杂的实际特征，对进一步优化整个物流系统，降低系统成本具有一定的理论价值和现实意义。

注意：移动的意义是灵活的，目的是便于搜索。 注意：移动的意义是灵活的，目的是便于搜索。
17
二.禁忌搜索
2. 构成要素
禁忌表 禁忌表( 的作用： 禁忌表(T表)的作用：防止搜索出现循环 将移动、 ① 将移动、移动分量或适值作为禁忌对象 表的长度称为Tabu-Size， ② 表的长度称为Tabu-Size，可以用来控制局域 搜索和广域搜索 表是动态更新的——把最新的解记入， ——把最新的解记入 ③ 表是动态更新的——把最新的解记入，最老 的解从表中释放(解禁) 的解从表中释放(解禁)
第三章 禁忌搜索
1
第三章 禁忌搜索
一.导言 二.禁忌搜索 TS举例 三. TS举例 TS中短 中短、 四. TS中短、中、长期表的使用 学习TS TS的几点体会 五.学习TS的几点体会
2
一.导言
1. 问题描述
min f ( x)
目标函数
s.t. g ( x) ≥ 0
x∈ X
约束条件 定义域
注：X为离散点的集合，TS排斥实优化 为离散点的集合， 排斥实优化
12
一.导言
2. 局域搜索
优劣性 通用易实现， ① 通用易实现，易于理解 搜索结果依赖于初始点和邻域结构， ② 搜索结果依赖于初始点和邻域结构，容易陷 入局优
x0
x0
13
一.导言
2. 局域搜索
优劣性 通用易实现， ① 通用易实现，易于理解 搜索结果依赖于初始点和邻域结构， ② 搜索结果依赖于初始点和邻域结构，容易陷 入局优
2. 局域搜索
示例 方法： 方法：全邻域搜索 第 1步 N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB) ，(ABDCE)，(ABEDC)，(ABCED)}， ， 对应目标函数为f(x)={45, 43, 45, 60, 60, 59, 44} 对应目标函数为 xbest:=xnow=(ACBDE)

C x 16 x* x A(s, x) C(x*) 16
移动 Sx
3，1 2，3 3，4 7，1 6，1
C x
2 1 -1 -2 -4
T表 1 4，5
2 3
…… ……
结论：互换1和3
30
三.TS举例
③ 迭代2 编码：2-4-7-1-5-6-3
C x 18 x* x A(s, x) C(x*) 18
第三章 禁忌搜索
1
第三章 禁忌搜索
一.导言 二.禁忌搜索 三. TS举例 四. TS中短、中、长久表旳使用 五.学习TS旳几点体会
2
1. 问题描述
一.导言
min f (x) s.t. g(x) 0
x X
目的函数 约束条件 定义域
注：X为离散点旳集合，TS排斥实优化
3
一.导言
2. 局域搜索
➢ 邻域旳概念 ① 函数优化问题： 邻域(N(x))一般定义为在给定距离空间内，以一点 (x)为中心旳一种球体 ② 组合优化问题：
xbest:=xnow=(ACBDE)
ABCDE
11
一.导言
2. 局域搜索
➢ 示例 措施：全邻域搜索 第2步 N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC) ，(ACDBE)，(ACEDB)，(ACBED)}， 相应目的函数为f(x)={43, 45, 44, 59, 59, 58, 43}
5
一.导言
2. 局域搜索
➢ 邻域旳概念 例： 解旳邻域映射可由2-opt，推广到k-opt，即对k个元 素按一定规则互换。
邻域旳构造依赖于解旳表达，邻域旳构造 在智能优化算法中起主要旳作用。
6
练习

禁忌搜索算法又名“tabu搜索算法”为了找到“全局最优解”，就不应该执着于某一个特定的区域。

局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。

禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。

兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。

就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。

当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。

这就是禁忌搜索中“禁忌表（tabu list）”的含义。

那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。

这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。

伪码表达：procedure tabu search;begininitialize a string vc at random,clear up the tabu list;cur:=vc;repeatselect a new string vn in the neighborhood of vc;if va>best_to_far then {va is a string in the tabu list}begincur:=va;let va take place of the oldest string in the tabu list;best_to_far:=va;end elsebegincur:=vn;let vn take place of the oldest string in the tabu list;end;until (termination-condition);end;以上程序中有关键的几点：（1）禁忌对象：可以选取当前的值（cur）作为禁忌对象放进tabu list，也可以把和当前值在同一“等高线”上的都放进tabu list。