（计算机软件与理论专业论文）有车辆数限制的开放式车辆调度问题.pdf

有车辆数限制的开放式车辆调度问题 计算机软件与理论 硕士生：李志业 指导教师：郭嵩山教授 摘要 本文研究的是车辆调度类问题( 潆) 的一个新的分支有车辆数限制的开放 式车辆调度问题( m - o 坤) 。在本文中，作者采用改进的禁忌搜索算法来解决 m 0 冲问题，提出了多初始解选优、平滑动态的禁忌长度等改进方法，并引入 了遗传算法中变异的思想来增加算法的活力。实验结果表明，本文提出的算法不 仅能很好地解决m o v l 诤问题，对o v r p 问题也能得到稳定的结果。在研究的 过程中作者还发现，m 0 冲问题的解和以所有客户( 包括仓库) 所在点的 d e l 肌n a y 三角剖分有紧密联系。因此，猜想心o 潆问题解的大多数边会落在 相应的d c l 鲫n a y 三角剖分的边上。本文尝试用该猜想去加速算法，取得不错的 结果。 事实上，本文所提出的一些方法可以很方便地应用到其他的一些启发式搜索 问题的求解中。 关键词：开放式车辆调度问题，禁忌搜索，平滑动态的禁忌长度，d e l 锄m y 三角剖分 o p e n 、碡h i d er o u 6 n gp m b l e m w i t hu m i t e dn u m b e ro fv b l l i d e s c o m p u t e r s o f t w a r ea n d t l i e o i 了 n a m e ：uz h i y e s u p c i s o r ：p r o f g u os o n g s h a n a b 8 t r a o t i nt h i sp a p e r is t u d yan e wu 辩f l i lc 】【t e n s i o no fv c h i c l cm u t i n gp m b l e m ( v r p ) 一 o p e nv e j l i c l em u 血gp b l c mw 矗hl i m j l e dn u m b e ro fv c h j c l e s ( 1 l 卜o 、喂p ) ip f o p o s e a ni m p m v e dt 曲us c a r c ha i g o r i t h l nb yt c c h n i q u 船o fb e s t - l e c c i o n 白o m 舢1 t i p l c j l l i t i a l i z a t j o 璐，s 脚o t hd y n a m i ct a b ut e 肌托，柚d 删t a t i d ni m p m v c m e tf r o mg c a l g o r 劬i f r o mt l l ec 冲c r i m c n t a lm 辄n s m ya 培。血h i n to n l yw e l ls o l v c st h c 卜0 v i 冲p r o b k m ，b u ta l o b t a i 璐9 0 0 d l u 豳璐如rt h eo 、，】冲p r o b l c mw i t hs t a b l c p c r 如r 瑚n c c d u r i n gt h es t u d y ，i 如u n dn 垃c l o n m c t i o n sb c t w e e t h cs o l u t j o no f m o v l ；t pp b k ma n dl h ed e l 觚瓶yt r i a n g l l l 砒主o no fa hc l l s t o m e 塔( i n c l u d i i l gt h c d e p o t ) s 0ia s 如m ct h a tm o s te d g 镐o ft h c l u t 幻no fm - o v l 冲p m b k m 缸ct h ce d g c s o ft h ed e h u n a yt r i a n g l l l a t j o no fa l lc i l s t o 鹏r s ( i n c l u d 啦t h cd c p o t ) ia i s ou s ct h c a s 叭n l p t i o nt oa c c c l e m t em ya l g o r i t h i i l l nh d ，t h e 村c ht c c h n i q u 酷p m p o s c di nt h i sp a p c r 啪b c s n ya p p l i e d 幻r 0 t h c rm c t a - h c u r i s t k 葛幻fp 帕b l c m l v 缸g k e yw o m 戤o p c nv c h i d cr o u t i n gp m b l c m ，t a b us c a r c h ，d ”a l i l i cs 脚o t h t a b ut c 仙r e ，d c h u 腿y 删柚g i i l a 豳n 第1 章概述 现实生活中，很多物流方面的问题都可以归结为车辆调度问题( v e h i c l e r o u t i f l gp r o b k m v r p ) ，比如货车如何选取路线以最短的时间去给所有客户送 货、运钞车选取怎么的路线可以最快的完成所有运钞任务、公共汽车线路如何设 计可以最节约成本。所以，对冲类问题的研究是很有现实意义的。 早在二十世纪的五十年代末期，d a l l t z 谵和r a m s e r 就发表了关于u 类问 题研究的学术论文，此后，关于冲类问题的研究就一直非常系统地进行着。 之所以有这么多人对v r p 的研究感兴趣，主要有三个方面的原因：一是问题本 身来源于实际，问题的解决可以降低生产成本、促进生产效率的提高；二是问题 的学术研究非常的有意义，v r p 类问题大多数都是n p h 缸d 问题，解决该类问 题要做的是在合理的时间内得到一个尽可能优的解，是需要充分利用问题本身的 限制来改进算法，有时候，在某个问题中提出的算法改进思想可以扩展到其他的 n p h a r d 问题中，从而对其他问题的解决产生帮助；三是v r p 的分支非常多， 因为实际问题本身不可能是完全相同的，源于实际问题的冲自然也就有了各 种各样有意义的分支，各个分支之间的解决方案有时候可以互相借鉴，从而促进 各个分支的共同发展。 车辆容量有限制的车辆调度问题c v i 冲( c a p a c n a t e dv e h i c kr o u t i n g p m b l e m ) 、有时间窗限制的车辆调度问题t 町w ( v c h i c l em u t i i l gp r o b l e mw i n l t h n ew 砌o w ) 、多起点的车辆调度问题佃v 】强( v c h i c kr o u t i n gp r o b l e mb y m u h i p l ed e p o t s ) 、中途可以装载货物的车辆调度问题v r p p d ( v c h i c km u t h i g p r o b k mw i l hp i c k u pa n dd e 曲c r 蛐、周期性的车辆调度问题p v r p 俨e r i o d i c 坤) 、可以分开运送的车辆调度问题s d ( s p l i td e l i v e f yv c h i c l cr o u t i n g p r o b l c m ) 、有时间窗和车辆数限制的车辆调度问题m - v r p l w ( v c h i c kr o u t i i i g 邮b k mw 曲b o t ht i n l ew 妯d o wa n dl i l n i t c d 姗m t 脚o f v c h i c l e s ) 、开放式的车辆调度 问题o v 】u ( o p c nv e h i c kr o u t i l l gp r o b k m ) 等等v r p 的分支都有人做了相关的研 究【1 】【3 】。 本文要研究的问题也是冲类问题的一个分支，有车辆数限制的开放式车 辆调度问题m - 0 v 】 ( 0 p e nv e h i c l em u t j i l gp m b k mw i l hl i m i t e d 肌m b c ro f v c h i c l e s ) 。 v l 王p 类问题按问题的目标分一般可以分为两类，第一类问题的目标可以粗 略地描述为“满足所有客户最少需要多少辆车”，c v r p 、t n w 、m d v r p 、 v r p p d 、p 强、s d v r p 、0 渖都是这一类问题；第二类问题与第一类问题相 反，目标是“在给定的车辆数限制下最多可以满足多少客户”，作者之前在 i e 刖灿e 2 0 0 4 上发表的关于m 啦t w 问题的论文【1 7 】以及本文将要讨论的 m ，o v l 冲问题都属于这类问题。作者认为，在各种资源都日益紧张的今天，对第 二类问题的研究变得越来越重要了。 本文章节的具体组织如下：第2 章是问题的描述部分，包括可能的实际问题、 问题的形式化描述及相关文献的回顾等。第3 章是测试数据，包括测试数据的来 源、生成方法，并提出计算m _ o v r p 问题上界的整数方程。第4 章和第5 章是 本篇论文的核心部分，即解决m - o v r p 问题的算法。在第4 章中，作者提出了 多初试解选优、平滑动态的禁忌长度等算法的改进思想，还通过引入遗传算法中 变异的思想来增加算法的活力。在第5 章中，作者提出了m o v r p 问题的解的 大多数边会与相应的d c l a u n a y 三角剖分的边重合这样个猜想，并利用该猜想 加速算法，取得了不错的效果。第6 章是实验结果及分析，除了比较前面各章节 中算法的结果之外，还比较了m - o v r p 问题的解和o v r p 问题的解，以及 m _ 0 v r p 问题的解和上界之间的关系。第7 章是论文的结束语，作者在该部分中 总结了全文并指出m - o v r p 问题进一步的研究方向。 2 1 实际问题 第2 章问题描述 假设的实际问题一：在一个城市里有很多家商店，这些商店都希望能从公司 购进一定数量的货物。该公司在城市c 里设有一个仓库，因此决定从该仓库向 这些商店发货。遗憾的是，该公司并没与足够的货车同时满足所有商店的需求， 因此只能根据商店的分布及需求货物的多少去满足尽可能多的商店。 每家商店需要的货物数量和服务时间( 比如说卸货需要的时间) 是知道的； 货车的载货量和最长行驶时间也是知道的；如果货车与货车之间没有区别、客户 与客户之间也没有优先级之分，如果每家商店最多只能安排一辆车给它供货，如 果这些车在服务完相应的商店后不需要返回仓库，问这些货车最多可以满足给多 少家商店送货的任务。 假设的实际问题二：某个国家新开发了口油田，很多城市都想得到这口油 田的石油，出于长远的考虑，在油田和城市之间架设一些输油管道是很有必要的， 出于成本和油田产量的考虑，没有办法在所有的城市和油田之间都架设输油管 道，如何选择输油管道的铺设路线就成为一个关键的问题。 2 每个城市需要的石油数量是知道的：一条输油管道每天最多输送的石油量和 管道铺设的最大长度也是知道的；如果管道与管道之间没有区别、城市与城市之 间也没有优先级之分，如果每座城市最多只能安排一条管道经过，问这些输油管 道最多可以满足给多少座城市输油的任务。 2 2 形式化描述 问题可以形式化定义如下： 给一个无向图g ，彳) ，y = v 。，v ，v 。 ，v 。代表仓库，v o ) 是客户，每 个客户有需求吐和服务时间黾；4 = ( 吒，v ) i f ，u ，v ， ，每一条边( u ，v ，) 有 一个运输的距离( 或时间) b ：车辆的数量为耽每辆车的最大载货量为q ；每 辆车的最长工作时间为m 要求这m 辆车最多能服务多少客户每辆车都是从仓 库出发，并且车在服务完相应客户后不需要返回仓库，每辆车服务的客户q 的需求总和2 五；要小于等于车的最大载货量q 。每个客户q 最多只能被一辆车 服务( 由于车的数量是有限制的，有些客户不能被任何车辆服务) ，车辆的工作 时间不能超过其最长工作时间h 问题的目标是在只使用m 辆车的情况下，服务尽可能多的客户。 强类问题是在t s p ( 旅行商问题) 和b b p ( 二维背包问题) 的基础上扩 展而来，是n p h a r d 的问题，叶o 冲属于v r p 类问题，也是n p h a r d 的，因 此不存在一个多项式时间的算法，本文要做的是找一个有效时间的算法尽可能优 的解决m 0 v i 冲问题。 2 3 已有的研究 根据所查阅的文献资料，目前尚未发现有专门研究m _ o v r p 问题的学术论 文。然而在对最原始的c v r p 问题的研究上，近年来也有不少论文问世，比如【9 】、 【1 0 】、【1 1 】、1 1 3 】。在与m _ 0 m 啦问题关系非常密切的0 v 】心问题方面，j o 西b r 柚d 矗o ( 2 0 0 4 ) 也发表了最新的研究成果【7 】。另外，与心0 坤问题目标相似的 m - v r i 叮w 问题，h ( m n gc h u 缸l 丑u ，m c l v y ns i l n k 0 n gm c n 9 1 铀( 2 0 0 3 ) 及z i i i y e us o n g s h 她g u 0 ，跏w h n g ，山曲wl i n l ( 2 0 0 4 ) 也做了相应的研究【1 5 】【1 7 】。 在这些问题的研究当中，很多启发式的算法得到了广泛的应用。例如： g l l a s p ( 觚c d y 捌1 d o m i z 。da d a p t 溉s c a r c h ) 、模拟退火算法s a ( s i m u l a t e d a n 鹅a l i n g ) 、禁忌搜索算法t s 佃a b u a f c h ) 、遗传算法g a ( g c n c t ；ca k o r i t h m s ) 、 3 蚁群系统a s ( a m ts y s t c 嘲【2 卜另外，一些很有效的算法( 改进) 也不断出现。 例如：求初始解的k 最小生成树算法k - m s t ( k m i l l i m a l s p a n n i n g t r c e ) 【5 】【6 】【1 4 】、 修正某一条路径的片断优化算法f o ( f h g m e n t a lo p t i m i z a 内n ) 【4 】、参考模拟退火 的领域搜索算法( l d c a ls e a r c hw i t ha l l l l e a l i l l 哥l i k er e s t a n s ) 通过研究发现， 对于v r p 类问题的某些分支，两个算法或三个算法的结合可以产生不错的结果。 第3 章测试数据 在研究问题的过程中，作者采用实验的方法来比较算法的优劣，所以测试的 数据是必不可少的。但是m o 、哏p 问题是一个相对较新的问题，没有现成的权 威数据可以选用，因此需要自己构造测试数据。 构造数据的方法一般有两种，一种是随机生成，一种是修改相关问题的数据。 考虑到v l 璩类问题一直以来很多人在研究，一些相关问题的数据经过很小的改 动就可阻用在m o 冲问题上，而且自己随机生成的数据会缺乏权威性和代表 性，所以作者采用修改现成数据的方法来构造m 0 强问题的数据。 3 1 通过o v r p 问题构造数据 在v i 冲类问题中，与肚o 邛问题关系最为密切的是0 v r p 问题。与 m o 心问题不同，o 冲问题没有车辆数限制，其问题的目标是用尽量少的车 辆去满足所有的客户。 j o s 6b r 髓d 矗o ( 2 0 0 4 ) 在研究o v r p 问题的时候使用了1 6 组测试数据，如下 表所示： d a t ac lc 2c 3c 4c 5c uc 1 2f n n5 07 51 0 01 5 01 9 91 2 01 0 07 1 工 d a t an 2c 6c 8c 9c 1 0c 1 3c 1 4 1 3 45 07 51 0 01 5 01 9 91 2 01 0 0 上1 8 01 4 42 0 71 8 01 8 06 4 89 3 6 d 咖为数据名n 为客户教。l 为最长行驶畦牺 表3 1 ：0 v r p 问题的1 6 组测试数据 其中，c 1 、c 2 、c 3 、c 4 、c 5 、c l l 、c 1 2 、f 1 1 、f 1 2 这9 组数据没有最长 行驶时间的限制，所以不在这里考虑。剩下的c 6 、c 7 、c 8 、c 9 、c 1 0 、c 1 3 、 4 c 1 4 这7 组数据有最长行驶时间的限制，可以作为构造m 0 v r p 的基础。 根据j o s eb r 锄d a 0 ( 2 0 0 4 ) 的研究，这7 组数据在o 婶问题中需要的最少 车辆数如下表所示： d a t ac 6c 7 c 8 c 9 c l o c 1 3c 1 4 n5 07 51 0 01 5 01 9 91 2 01 0 0 工1 8 0 1 4 4 2 0 71 8 01 8 06 4 89 3 6 尼61 191 4 1 71 21 1 n 砒4 为数据名，n 为窖户数l 为最长行驶时间 k 为在o 憎辆毽中需要韵最少车辆数 表3 2 ：o v r p 问题的研究结果 作者采用下面的方法来构造m o v r p 问题的数据。以数据c 6 为例，因为在 0 冲问题中最少需要6 辆车才能服务所有的客户，所以在c 6 的基础上取车辆 数小分别为1 - 6 ，可以得到6 组不同的数据。每个数据单独命名，依次为j 1 6 _ 0 1 ， 儿c 6 - 0 2 ，j 1 o 臣6 ，同理其它数据也可以这样处理。 为了便于区分，所有从0 呱p 问题的数据中改造得到的数据都以儿为前缀。 3 2 通过v r 、问题构造数据 s o l o m o n 为v r p l w 问题设计了6 组测试数据，这些测试数据被称为s o l o l n o n 的标准测试数据( s o l o i n sb e n c h m a f kp l i 曲k m ) 【1 8 】，在埽类问题中具有很 高的地位。因此，作者选择这些数据来构造n 卜o v 】 问题的另一部份数据。 s o l 0 瑚n 的这6 组数据分别是r 1 、r 2 、c l 、c 2 、r c l 、r c 2 。 r 1 、r 2 中的客户分布是随机的，没有什么规律：c 1 、c 2 中的客户是聚集 分布的( 所有客户分为若干组分别聚集在一起) ；而r c l 、r c 2 有一部分数据来 自r 1 、r 2 ，另一部分数据来之c 1 、c 2 ，包含上述两种特点。 在这6 组数据中r 1 、c l 、r c l 每条路径可以容纳比较多的客户，相对应的 r 2 、c 2 、r c 2 每条路径只能容纳比较少的客户。 在s o l o i n 的设计中，通过时间窗( t i m ew m l o m 噶) 的变化，每组数据又 包含若干个不同的数据。m - o 心问题是没有时间窗限制的，这些变化不会对 m _ 0 v r p 问题的求解产生影响，所以每组数据只取其中一个做变换。 值得注意的是，在t p l w 问题中所有的车辆在服务完相应的客户后需要返 回出发点( 仓库) 的，而在m - o v r p 问题中车辆是不需要返回出发点的，所以 这里需要修正车辆的最长行驶时间限制，作者在生成新数据时将原有数据的最长 行驶时间限制乘以0 9 来获得新的最长行使时间限制。 5 d a t a s e tr l r 2c 1c 2 ”r c l ”r c 2 h 2 3 01 0 0 01 2 3 63 3 9 0 2 4 0 9 6 0 以 2 0 79 0 0 1 1 1 2 3 0 5 1 2 1 68 6 4 d 武s 吐为数据名d 为酿始帕最长行驶距离d 2 为额的最长行驶距离 表3 3 ：修正之后的最长行驶时间限制 在本文的数据文件命名中，所有从s o l o m o n 的标准测试数据中改造得到的数 据都以】2 为前缀。 作者从o 冲问题数据和s o l 0 瑚n 的标准测试数据中总共构造出1 1 5 个 m o v i 冲问题的数据，详细的数据列表可以在6 1 节中查到。 3 3 上界 在满足车辆载货限制和车辆行驶距离限制的情况下，假设每条路线上每个客 户( 仓库) 的两个邻居( 如果存在的话) 是在平面上离自己最近的( 如果有邻居， 一个最近，一个第二近) ，在这种极限的情况下得到的m 条路线上客户的总数肯 定会大于或等于最终m o v r p 问题的解，这样就确定了m 0 v r p 问题的上界。 定义集合u = 仉2 ，m 为川辆车的索引，矿为客户顶点的集合( 不包括仓 库) 。定义。唑气，。，器飘j k ，f ，七y ，是顶点f 到它最近的邻居车 辆需要行驶的时间( 距离) ，而。是顶点f 到它第二近的邻居车辆需要行驶的时 间( 距离) 。因为每个一条路径上的顶点都是和其他两个顶点相邻( 最后一个顶 点除外) ，所以、1 是车辆从顶点f 运行到它的邻居的下界。 考虑到现实的情况，本文假设一条路径中的顶点数会至少有3 个( 数据中也 会保证这一点) 。 定义决策变量为 o 皿，f 矿。，u ，一1 表示顶点f 在路径j 上。则以 下的整数方程返回小条路径( m 辆车) 能访问的顶点数的上界。 6 一墨荟b s t 蓍嘞虬 粥s q ，u i 甘” ( 勰+ + ) + r o + 矗s 删，w c ， 拒r ( 3 - 1 ) ( 3 2 ) ( 3 3 ) 限制( 3 1 ) 保证了每个顶点只能出现在一条路上； 限制( 3 2 ) 保证了每条路上所有客户的需求之和不会超过车辆的最大载 货量； 限制( 3 3 ) 保证了每条路的行驶时间( 包括服务时间) 不会车辆的最长 行驶时间。 根据上面的整数方程，使用i l d gc p l e x 可以很方便得到每个测试数据的上 界，具体各个数据的上界值可以在6 1 节中查到。 第4 章算法 下面将介绍本人结合m - o v l 冲问题的特点，改进禁忌搜索算法( t a b us c a r c h ) 来解决问题的过程。 4 1 禁忌搜索算法介绍 4 1 1概述 禁忌搜索的思想最早由g b v c f ( 1 9 8 6 ) 提出，它是对局部邻域搜索的一种扩 展，是一种全局逐步寻优的算法，是人工智能思想的体现。【8 】 局部邻域搜索是基予贪心思想持续地在当前解的邻域中进行搜索，其搜索的 性能完全依赖于邻域结构和初始解，很容易陷入一个局部最优的状态。禁忌搜索 是对局部邻域搜索的一种扩展，它最重要的思想是标记对应己搜索到的当前解的 一些对象，并在进一步的迭代搜索过程中尽量避开这些对象，从而保证对不同的 有效搜索途径的探索。【8 】 迄今为止，禁忌搜索算法在组合优化、生产调度、电路设计和神经网络等领 7 域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发 展的趋势。【8 】 4 1 2 基本思想 禁忌搜索算法的基本思想是：给定一个当前解( 初始解) 和一种邻域，然后 在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于当前的最优 解，则忽视其禁忌特性，用其代替当前解和当前的最优解，并将相应得对象加入 禁忌表，同时修改禁忌表中各对象的任期：若不存在上述候选解，则在候选解中 选择非禁忌的最优状态为新的当前解，而无视它与当前解的优劣，同时将相应的 对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程， 直至满足停止准则。 图4 1 为禁忌搜索算法的流程图。 = ：二：竺二竺：j 适t 匹三 l 竺竺：竺1 4 1 3 算法细节 墨 医= 习 一崔麟m 摹孽 囊的对， l 1 畔。i l 图4 1 ：禁忌搜索算法流程图 算法涉及到的邻域( n c i g h b o r h o o d ) 、适配值函数、禁忌对象( t a b i io b j c c t s ) 、 禁忌表( 1 曲ul i s t ) 、禁忌长度( t a b u | i i c n u f c ) 、候选解( c 姐d i d a t e ) 、藐视准则 ( a s p i r a t i o nc r i t e r i o n ) 、终止准则( t e m i n a t ec f i t e f i o n ) 等概念，下面逐一解释。 8 领域是整个解空间中当前解可以跳转到的所有解的集合。简单来说，就是通 过些解变换规则可以从当前解得到哪些解，当然这些解里既有比当前解优的， 也有比当前解差的。 适配值函数是用于对搜索状态的评价，进而结合禁忌准则和藐视准则来选取 新的当前状态。选择目标函数直接做为适配值函数是比较容易理解也是使用比较 普遍的方法。 禁忌对象就是被置入禁忌表中的那些变化元素，而禁忌的目的则是为了尽量 避免迂回搜索而多探索一些有效的搜索途径。禁忌对象通常可选取状态本身或状 态分量或是适配值的变化等。 所谓禁忌长度，即禁忌对象在不考虑藐视准则情况下不允许被选取的最大次 数( 可视为对象在禁忌表中的任期) ，对象只有当其任期为o 时才被解禁。 候选解是当前状态的领域中的解，通过某种规则的确定，用于进行下一次迭 代。 在禁忌搜索算法中，可能会出现候选解全部被禁忌，或者存在一个优于当前 最优状态的禁忌候选解，此时藐视准则将使某些状态解禁。 禁忌搜索算法需要一个终止准则来结束算法的搜索进程，由于实现状态空间 的完全遍历是不可能的，因此通常在设计算法时选用近似的收敛准则。和模拟退 火、遗传算法差不多，常用的终止准则有：给定一个迭代步数；设定与估计的最 优解的距离小于某个范围时，就终止搜索；当与最优解的距离连续若干步保持不 变时，终止搜索。 可以看到，邻域函数、禁忌对象、禁忌表和藐视准则，构成了禁忌搜索算法 的关键。其中，邻域函数沿用局部邻域搜索的思想，用于实现邻域搜索：禁忌表 和禁忌对象的设置，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状 态的奖励，它是对禁忌策略的一种放松。 与传统的优化算法相比，禁忌搜索算法主要有以下特点： 在搜索过程中可以接受劣解，具有较强的爬山能力； 新解不是在当前解的邻域中随机产生，而或是由于当前的最优解的解， 或是非禁忌的最佳解，因此选取优良解得概率远远大于其他解。 4 2 基本算法 在解决舟o v r p 的基本算法中，作者采用贪心算法而不是通常所用的随机 算法来生成初始解，用客户的交换和插入删除来确定解的邻域，禁忌表中的对象 是客户，禁忌长度是根据经验及实验选用的固定的值，候选解集为邻域中最好的 一组解，每次找到一个优于当前最优状态的解迭代计数器臼蝴f 都清零，算法的 终止通过迭代次数进行控制。 9 有关应用该算法所得到的解和运行时间请参看6 3 节。 4 3 初始解 原始的禁忌搜索算法采用髓机生成的方法来构造初始解，这显然是不够好 的，需要根据问题的特点有针对性的生成初始解。在编程实验的过程中，作者比 较了两种生成初始解的方法，一种是使用得比较普遍的最近邻居优先算法 ( n e a r c s tn c i 窖血b o rh m 妇i c ，n n h ) ，另一种是根据m - o v l 诤特点新提出的极坐 标扫描算法( p o l a r a x i ss c a i l p a s ) 。 4 3 1初始解构造算法之一；最近邻居优先算法 最近邻居优先算法是一种贪心算法。这种算法在构造路线的时候每次都选择 离当前客户最近的客户来扩展，不断地重复直到所有的客户都在路线上或所有线 路都无法容纳更多的客户为止。 1 0 a 设初始解勘f 为空，将所有客户放到等待列表目口肠魄正纽中； b 重复直到没有客户能被加入到勋f 中的任何路线中或者协f d 拥豇斑为空 a )尝试将每一个不在胁矗妇牡纽中的客户放到勋f 中每条路线的最后，计 算新增的行驶距离( 包括服务时间) ； b ) 选取新增的行驶距离最小的情况，假设在这种情况下是尝试将客户c 加 入到& 竹的路线，中； c ) 将客户c 从舶触_ ，l 罟“娃中移除，将客户c 加入到线路r 中 4 3 2 初始解构造算法之二：极坐标扫描算法 极坐标扫描算法也是一种贪心算法。这种算法以仓库为原点进行扫描，先被 扫描到的客户有优先被加入解中线路的权利。扫描一圈后就可以把所有可能的客 户都加入线路中。 极坐标扫描算法 a 设初始解勘z 为空，假设有 个客户； b 以仓库所在点为原点，将所有客户按照时钟扫描的顺序排序，假设排好序的 客户队列为七； c 将队列中七的每一个客户做为一次起点( 即重复一次) 进行如下操作 a )设临时解砌 衄f 为空，将所有客户放到等待列表肋磁啦栅中； b )依次构造砌秭鼬f 的每一条路线 i 尝试将当前客户加入线路中，若成功将该客户从舶f 鲰牡衄中移除： i i 取队列中的下一个不在凰咄妇牡衙的客户为当前客户，若到队列尾则从 队列头开始取： i i i 若无法将客户添加到当前线路中或励) 此妇吐衙为空则结束当前线路的 构造； c )比较蛐z 和蹦，若嘞f 优于勘f 则将砌归f 赋值给曲z 。 4 3 3 初始解构造算法的比较 选取儿_ 1 0 遥5 、j 2 _ c 1 _ 0 9 这两个数据对初始解的构造算法进行比较( 图4 2 、 图4 3 、图4 4 、图4 5 ) 。 1 1 图4 2 ：数据n 0 8 一0 5 运用最近邻居优先算法得到的结果 图4 2 共有6 0 个点( 除了仓库所在的点) 在各种边上，表明数据儿_ 0 8 _ 0 5 运用最近邻居优先算法得到的结果为6 0 。图中d 表示仓库，其他点表示客户， 点旁边的编号为客户编号。 ”一牛嘶m ：m 娜2 0 巴 m 5m 杩 图4 3 ：数据儿一0 8 一0 5 运用板坐标扫描算法得到的结果 图4 3 表明数据j 10 80 5 运用极坐标扫描算法得到的结果为4 9 。实验结果 表明，在j 1 瑚- 0 5 这个数据上，采用最近邻居优先算法要优于极坐标扫描算法。 图4 4 ：数据儿一c 1 0 9 运用最近邻居优先算法得到的结果 图4 4 表明数据儿c 1 p 9 运用最近邻居优先算法得到的结果为9 1 。 图4 5 ：数据儿一c 1 - 0 9 运用极坐标扫描算法得到的结果 图4 5 表明数据j 1 c 1 运用极坐标扫描算法得到的结果为9 7 。在j 1 c 1 0 9 这个数据上，采用极坐标扫描算法要优于最近邻居优先算法。 通过比较可以发现，不同的客户分布情况会对算法的结果造成很大的影响。 当客户分布比较随机的时候，最近邻居优先算法得到的初始解明显优于极坐标扫 描算法；当客户的分布状态是分为若干组分别聚集在一起的时候，极坐标扫描算 法得到的初始解明显优于最近邻居优先算法。 6 1 节中提供了所有数据在两种不同初始解构造算法下得到的结果。 4 3 4 用多种算法构造初始解 在解决问题的时候可以尝试用多种不同的算法去构造初始解，从中选取较优 的做为初始解可以尽快的逼近最后的结果；由于构造初始解的算法的复杂度一般 较低( 多采用贪心算法或随机算法) ，用多种算法构造初始解并不会对整个算法 的时间复杂度造成影响。 因此在解决m - 0 v r p 问题的时候，选择最近邻居优先算法和极坐标扫描算 法得到的解中较优的那个做为初始解。作者把这种构造初始解的算法称为多初始 解选优。 构造初始解的算法 ；v j a 调用最近邻居优先算法得到解曲f f ； b 凋用极坐标扫描算法得到解勋陀； c 比较曲，j 和勋f 2 ，返回较优的做为初始解 4 4 禁忌长度 禁忌长度是禁忌搜索算法的一个重要的参数，对应不同的禁忌长度，同一个 算法会得到明显不同的结果。本文对禁忌长度对算法的影响作了比较详细研究， 比较了固定的禁忌长度、针对数据的固定禁忌长度、动态的禁忌长度和平滑动态 的禁忌长度。 4 4 1 固定的禁忌长度 算法在设定禁忌长度的时候不考虑考虑客户的数量、不考虑当前的迭代次 数，根据经验直接设定一个禁忌长度，这种方法最直观，也完全符合禁忌搜索算 法的要求，是采用得最普遍的一种禁忌长度设定方法。在文中，将这种禁忌长度 的设定方法称为固定的禁忌长度( f 奴c dt a b l it e 肌他) 。 这种方法的缺点是没有充分利用数据的信息，也没有考虑算法执行过程的变 化，有时候效果会不够好。 在6 2 节中，作者列出了禁忌长度分别固定为5 、1 0 、2 0 、3 0 、4 0 的情况下 得到的结果。 通过观察列出的结果可以发现，在5 、1 0 、2 0 、3 0 、4 0 这五种禁忌长度中， 禁忌长度为2 0 的情况下算法的结果最好，禁忌长度定得太小( 5 、1 0 ) 或太大 1 4 ( 3 0 、4 0 ) 都会使算法的结果变坏。禁忌长度的选取没有一般的规律可循，唯一 可以依靠的是反复的实验。 4 4 2 针对数据的固定禁忌长度 上一节中禁忌长度的设定没有考虑到数据的具体情况，比如客户的数目、车 辆的数目等等。在接下来的两种禁忌长度的设定方法中，将禁忌长度与客户的数 目、车辆的数目结合起来，在文中，称之为针对数据的固定禁忌长度 ( d a t a o d e n t e df i 】【e dt 抽ur i e 肌r e ) 。 假设客户数目越多的情况下禁忌长度越大，车辆数越多的情况下禁忌长度也 越大。客户数目为 ，车辆数目为m ，第一种方法只考虑客户的数目，设禁忌长 度为2 l 也l ，第二种方法同时考虑客户的数目和车辆的数目，设禁忌长度为 陋卜卅。 和固定的禁忌长度一样，针对数据的禁忌长度也有很多种选择，这同样需要 结合问题和数据的特点进行反复的实验。 在6 2 节中，作者列出了禁忌长度分别为2 l 石l 、l i l + m 的情况下得到的 结果。 比较上一节固定的禁忌长度，算法在使用针对数据的固定禁忌长度之后，结 果要优于禁忌长度为5 、1 0 、3 0 、4 0 的情况，接近但是并没有优于禁总长度为 2 0 的情况。 分析测试数据可以发现，客户数目的范围仅仅是从5 0 到1 9 9 ，并不是非常 的大，而且在这个范围之内客户数目也仅仅是5 0 、7 5 、1 0 0 、1 2 0 、1 5 0 、1 9 9 这 六种情况，所以依赖客户数目变化的禁忌长度并没能充分显示出它的优势。只有 当数据中客户数目的范围很大并且客户数目比较随机的情况下，针对数据的固定 禁恿长度才能有用武之地，而在现实中，抽象出来的数据恰恰能满足这个条件， 所以说针对数据的固定禁忌长度还是很有潜力的。 4 4 3 动态的禁忌长度 针对数据的禁忌长度是根据客户的数目和车辆的数目来设定禁忌步数，考虑 的是数据本身；而动态的禁忌步数( d y n a m i c t a b ut e 咖e ) 是根据当前的迭代步 数来修改禁忌步数，考虑的是算法的执行过程。 当迭代刚刚开始的时候，可以将禁忌长度设得稍微大些，使搜索的范围尽可 能的扩大；而当迭代接近结束时，需要将禁忌长度设得比较小，让更多的可能性 可以被尽快地尝试。这里尝试两种设置禁忌长度的方法，一种是禁忌长度根据迭 代次数c 0 u m 的递增线形递减( 公式4 1 ) ，一种是根据迭代次数c o u m 的递增按 余弦曲线递减( 公式4 2 ) 。 禁忌长度根据迭代次数c o u m 的递增线性递减： 乃h 弛n “，e 1 缸x 死缸z 锄h 陀鱼竺型塑生二皇鱼兰竺l ( 4 1 ) 【 c o “n 此泐打 j 禁忌长度根据迭代次数c o u n t 的递增按余弦曲线递减： m 洳“l 撇黝“砌u 刚晚x 盏i c 4 彩 在6 2 节中，作者列出了禁忌长度线性递减和按余弦曲线递减这两种的情况 下算法得到的结果。 与上两节的固定禁忌长度和针对数据的固定禁忌长度相比，选用动态的禁忌 长度能得到更加优的解。 4 4 4 平滑动态的禁忌长度 根据上一节计算当前禁忌长度的公式，可以得到在程序的运行过程中禁忌长 度变化的示意图。 “t “畦r 图4 6 ：动态的禁忌长度算法中禁忌长度变化的示意图 当一个当前最优解& s 渤f 被更好的解替代时，迭代计数器c d h t 立即变成 0 ，因此根据c d 删f 变化的禁忌长度会立刻恢复至最大的禁忌步数，禁忌长度这 种突然的变化会对禁忌表的稳定造成一些不利的影响，因此有必要找一种方法既 可以利用动态的禁忌长度又可以消除禁忌长度这种突然的变化。 1 6 禁忌长度是由迭代计数器c b “眦决定的，因此解决禁忌长度突然变化的问题 就是要解决迭代计数器c 。棚f 突然变化的问题。本文在新的算法中引入一个辅助 变量c 妇眦，c c 蝴f 2 的作用就是用来逼近原来的迭代计数器c b 姗f ，让禁忌长度 是根据c d h t 2 来进行变化，这样禁忌长度的变化就会更加合理。改进之后的算 法如下： 利用改进后的算法，可以画出新的禁忌长度的变化图，可以发现，禁忌长度 突然的变化已经给修正了，作者将这种方法取名为平滑动态的禁忌长度( s m o o t h 1 7 d y n a m i cr i a b ut e n u i e ) 。 图4 7 ：平滑动态的禁忌长度算法中禁忌长度变化的示意图 在6 2 节中，作者列出了采用平滑动态的禁忌长度时算法得到的结果。与动 态的禁忌长度相比，选用平滑动态的禁忌长度时的解的质量又有小幅度改进。 4 5 引入随机因素 在遗传算法和其他的一些启发式搜索算法中，经常会利用变异的思想来帮助 得到更优的解。在解决n 卜o v i 强问题的禁忌搜索算法中也可以采用这样的思想， 称为引入随机因素。 随机因素的引入可以让解从当前的子空间迅速的跳到另一个子空间，扩大搜 索的范围，增加得到更优解的机会。从另一个方面说，对于一个没有随机因素的 算法而言，如果输入的是同一个数据，无论运行程序多少次，得到的结果都是一 样的。如果这时候有足够的机器资源，能够多次运行程序对同一个数据进行求解， 随机因素的引入就显得更有意义了。可以这么说，随机因素让算法更具活力。 随机因素的引入也有一个度的问题，过少的随机因素达不到提高解质量的效 果，过多的随机因素会使算法的主体遭到破坏。 经过反复的比较，在本文提出的解决m _ 0 v r p 问题的算法中取随机因子为 1 5 ，即在算法的运行过程中会有1 5 的机会候选解集中的一半解被随机重构， 具体的重构算法如下： 引入随机舔索的算法。 ： 翟 a 1 5 的机会执行以下算法( 使用随机函数) a )随机取候选解集o ”d i 出据s 甜中的一半解，依次处理 i 假设要随机重构的解为7 确p 勋f j i 随机取n 币曲f 中的条路径，设为， 洫假设c 是r 中距两个孝h 邻的客户( 或仓库) 距离之和最远的客户，将c 从r 巾删除 作者在6 3 节中比较了算法运行一次和运行二十次的情况，由于加入随机因 素，随着运行次数的增多，解的质量也越来越好，可以看到解的总和从7 9 7 3 提 高到了8 0 2 3 。 4 6 改进后的算法 在4 2 节基本算法的基础上，算法采用多初始解选优、平滑动态的禁忌长度 及遗传算法中变异的思想进行改进；另外在每次迭代中，对候选解集。硝池f 岱“ 中的解进行调整，调整每条路径中客户的顺序，使路径更加合理。 改进后的算法如下： 改遂雇的算法。、 ” 、； ， a 用多种算法，l 三成初始解，取觑f “n 如z 为这螋初始解巾最优的一个 b 没背当前最优解b 如f = 如f f 如 如z c 设置禁忌k 度肘甜而h 殆h h 肥 d 设置最人迭代次数c d “n 见咖缸 c 设迭代次数c 臼“h f = o ，辅助迭代变量c d “n 口= 0 t 设候选鼹集合c n n d i d n t e s e t 为空，将j n m a l s o l 弧入c n h d i d a 把s e f 中 g 当c b “小 c 白“h 圮砌打并且口e s 如f 中仍有客户未被服务 曲( 0 h 埘= c o h n f + 1 b 1女h 果c 白“n f 2 c b “玎f 贝0c b “肛f 2 = c b h 肛f 2 + 1 ；否贝l jc b “咒f 2 = c b “n f 2 1 c )调用领域搜索生成新的c 口n 饿如，e & f d 1如果找到比b 倒曲f 更优的解则更新b e s 如，则令c o 肿= 0 e )加死n “，e ；l 肘“弛加死n “，e 。鱼竺竺坚型尘羔咝l 【 c d h n f l 抽打 j f ) 根据o n 删日圯f 的解和计算出的而妇殆”“圮更新禁忌表勋h 勋6 k g )对候选解集o n d 池f b 站f 中的解进行调整，调整每条路径中客户的顺序 h )1 5 的机会对c 口耐 妇把f 中的解进行随机重构 作者在6 3 节中提供了所有数据在原始的禁忌搜索算法和改进之后的禁忌搜 索算法下的结果。在近乎相同的运行时间下( 原始的禁忌搜索算法为2 4 2 2 4 秒， 改进后的禁忌搜索算法为2 4 1 3 8 秒) ，原始的禁忌搜索算法得到的解的总和为 7 9 5 1 ，改进后的禁忌搜索算法得到的解的总和为7 9 7 3 。 显然，改进之后的禁忌搜索算法要优于原始的禁忌搜索算法。 第5 章用d e l a u n a y 三角剖分加速算法 把数据中的所有点( 仓库和客户) 做d e k m m y 三角剖分，发现解中路径的 大部分边会落在d c h u 越y 三角剖分的边上。因此，猜想