（应用数学专业论文）有时间窗的车辆路径问题（vrptw）的近似算法研究.pdf

摘要 日. 曰 . . . . . . .口 . 口 -. .口.口.州 州 叫口口. . 州峨 口门 . . 脚曰. . . . 口.曰.口.口.曰口.口. 摘要 车辆路径问题( v e h i c l e r o u t i n g p r o b l e m ) 是近二十年来运筹学、应用数学、网 络分析、图论、计算机应用及交通运输等学科研究的一个热点问题，也是组合优 化中的n p完全难题。v r p 不但为离散优化领域中其他的各类算法提供了思想方 法平台，而且还广泛地应用于运输、生产、国防、生物、计算机应用等领域。本 文着重于对有时间窗的 车辆路径问 题( v e h i c l e r o u t i n g p r o b le m w i t h t i m e w i n d o w , 简称v r p t w) 的近似算法进行研究，主要的工作可分为以下三部分: 首先，本文详细阐明了v r p t w 的数学模型，着重介绍了近二十年 v r p t w 研究所取得的一些成果:包括算法的求解思路、优点、局限和适用范围。另外本 文还简单介绍了一下算法的实验评价标准和具体操作，为各种算法的比较提出了 一些建议。 其次，本文通过分析客户间的距离、客户的时间窗、开始为客户服务的时间 等之间的关系，构造了一种快速的确定性的初始算法一一基于 “ 开始服务时间最 早优先” 法来产生初始可行解， 其时间 复杂度为o ( n l o g i ) ， 明显快于节约法o ( n 4 ) a 通过与节约法的实验结果比较，不仅进一步说明了我们的算法的 “ 快速性”，而 且还说明了用我们的算法得到的初始解也是“ 不错的” 一一总体上略优于节约法， 某些时候还占有很强的优势。 最后，针对现有的l n s算法不能很好解决r 2 , c 2 , r c 2 等时间窗比较宽的 问题的缺陷， 本文提出了一种新的r e m o v e 过程一一 “ 短路径优先” 策略， 该过程 也可以嵌入到时间窗比较窄的问题的r e m o v e 过程中， 达到加速搜索的目的。 另外， 本文还运用最小支撑k 一 树 ( t h e m i n i m u m s p a n n i n g k - t r e e ) 解决了p a u l s h a w在 文章中提出的一个问 题 一一m i n 丛( d , s ) 下界的 估计。 实验结果 表明， 改进的l n s 算法不仅可以很好地解决r 2 , c 2 , r c 2 等时间窗比较宽的问题， 而且对于s o l o m o n 的5 6 个例子都可以在很短的时间内达到接近最优的状态。如果需要进一步优化， 则需要稍微长一些的时间。 关键字有时间窗的车辆路径问题;v r p t w; l n s ;组合优化;算法 华南理工大学硕士学位论文 ab s t r a c t v e h i c l e r o u t i n g p r o b l e m ( v r p ) , w h i c h i s a n p - c o m p l e t e p r o b l e m o f c o m b i n a t o r i a l o p t i m i z a t i o n r e a l m , i s a h o t s p o t p r o b l e m i n t h e s u b j e c t o f o p e r a t i o n r e s e a r c h , a p p l i e d m a t h e m a t i c s , n e t w o r k a n a l y s i s , t h e o r y o f c h a r t , c o m p u t e r a p p l i c a t i o n a n d t r a n s p o r t a t i o n d u r i n g t h e l a s t t w e n t y y e a r s . b e s i d e s i t s w i d e a p p l i c a t i o n , i t b u i l d s a t h o u g h t p l a t f o r m f o r o t h e r a l g o r i t h m s i n d i s c r e t e o p t i m i z a t i o n s t u d y . i n t h i s p a p e r , w e p u t e m p h a s i s o n a p p r o x i m a t e a l g o r i t h m s o f v e h i c l e r o u t i n g p r o b l e m w i t h t i m e wi n d o w s ( v r p t w) . t h e ma i n w o r k i s a s f o l l o w s : f i r s t l y , w e i n t r o d u c e t h e m a t h e m a t i c a l m o d e l a n d g i v e a r e v i e w o f a c h i e v e m e n t s o f v e h i c l e r o u t i n g p r o b l e m w i t h t i m e wi n d o w s w h i c h i n c l u d e d i v e r s e a l g o r i t h m s i d e a s , a d v a n t a g e s , l i m i t a t i o n a n d a p p l i c a t i o n c o p e . i n a d d i t i o n , w e s i m p l y i n t r o d u c e t h e e x p e r i m e n t a l e v a l u a t i o n c r i t e r i a o f h e u r i s t i c s a n d p u t f o r w a r d s o m e a d v i c e . s e c o n d l y , w e c o n s t r u c t a f a s t d e t e r m i n i s t i c i n i t i a l a l g o r i t h m -b a s e d o n s t a r t s e r v i c e t i m e p r i o r i t y t o g e n e r a t e i n i t i a l f e a s i b l e s o l u t i o n b y a n a l y z i n g t h e r e l a t i o n o f c u s t o m e r s d i s t a n c e , c u s t o m e r s t i m e w i n d o w a n d t h e s t a rt t i m e f o r s e r v i n g c u s t o m e r . i t s t i m e c o m p l e x i t y i s 0 ( n 2 lo g , ) w h i c h i s m u c h f a s t e r t h a n s a v i n g s a l g o r i t h m s t i m e c o m p l e x i t y 0 ( n ) . t h e e x p e r i m e n t a l r e s u l t s n o t o n l y c o n fi r m t h e s p e e d i n e s s o f o u r a l g o r i t h m , b u t a l s o s h o w t h e f i n e i n i t i a l s o l u t i o n s o b t a i n e d b y o u r a l g o r i t h m . l a s t l y , a i m i n g a t t h e s h o r t c o m i n g o f l n s , w e p u t f o r w a r d a n e w re m o v e p r o c e s s -s h o r t r o u t e p r i o r i t y s t r a t e g y w h i c h c a n s o l v e p r o b l e m s w i t h l o n g s c h e d u l i n g h o r i z o n . t h e s h o r t r o u t e p r i o r i t y s t r a t e g y c a n a l s o b e i n s e r t e d i n t o t h e r e m o v e p r o c e s s o f p r o b l e m s w i t h s h o r t s c h e d u l i n g h o r i z o n t o a c c e l e r a t e t h e s e a r c h i n g p r o c e s s . i n a d d i t i o n , w e u s e t h e m i n i m u m s p a n n i n g k - t r e e t o s o l v e t h e p r o b l e m o f e s t i m a t i n g t h e l o w e r b o u n d o f m in n , ( a , s ) w h i c h w a s p r o p o s e d b y p a u l s h a w i n h i s a r t i c l e . t h e e x p e r i m e n t a l r e s u l t s s h o w t h a t c o m p a r i n g t o o t h e r e x c e l l e n t a l g o r i t h m s , i t c a n q u i c k l y r e a c h t h e s t a t e c l o s e t o t h e o p t i m a l s t a t e w h i c h n e e d a l i t t l e m o r e t i m e t o b e o p t i mi z e d k e y w o r d s v e h i c l e r o u t i n g p r o b l e m w i t h t i m e wi n d o w s ; v r p t w; l n s ; c o m b i n a t o r i a l o p t i m i z a t i o n ; a l g o r i h m s n 华南理工大学 学位论文原创性声明 本人郑重声 明:所呈交的论文是本人在导师 的指导下独立 进行研究所取得的研究成果。除了文中特别加以标注引用的内 容外，本论文不包含任何其他个人或集体 己经发表或撰写的成 果作 品。对本文的研究做 出重要贡献 的个人和集体 ，均 已在文 中以明确方式标 明。本人完全意识到本声明的法律后果 由本人 承担 。 作 者 签 名 : 刘 小 生 日 期 : 枷 年 上 a 习日 学位论文版权使用授权书 本学位论文作者完全 了解学校有关保留、使用学位论文的 规定，同意学校保留并向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅。本人授权华南理工大学 可 以将本学位论文的全部或部分 内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文 。 保密口，在年解密后适用本授权书。 本 学 位 论 文 属 于 / 不 保 密 曰 a ( 请在 以上相应方框 内打 “, / ) 作者签 名 导师签名 : , rq 。 “ 沁 国 孤 日 期 : 训年 了 “ 甲 日 日期:沁乡 年 士月 ; 。 日 第一章绪 论 第一章 绪论 1 . 1 本文的选题背景 1 . 1 . 1 路径安排问题 ( r o u t i n g p r o b l e m )研究的重要性 交通运输 ( t a n s p o r t a t i o n ) 是人类活动的 一个重要领域， 它支撑着人类其它 大部分的社会和经济活动。当我们使用电话，到食品店购买食物，阅读信件或者 坐飞机洽谈生意或旅游等，我们都是某种系统一一能够把信息、货物或人从一个 地方载到另一个地方的受益者。尤其是货物运输，它是当今人类重要活动之一， 不仅因为它是衡量一个国家国民生产总值 ( g r o s s n a t i o n p r o d u c t g n p )的准绳， 而且由于货物运输和配送对其它经济活动的巨大影响。让我们来看一组具体的数 字。 .早至 1 9 8 3 年， b o d i n 等人在文章 1 中提到:1 9 8 0 年，美国花在物流配送 方面的费用将近4千亿美元，而英国为 1 5 0 亿英镑。 .f i s h e r 1 9 9 7年在他的文章i l l 中写到:来自 全国物流配送理事会的研究表 明， 1 9 7 8 年运输费用占美国g n p的1 5 %, 1 9 8 1 年运输费用占丹麦g n p的 1 3 %, 1 9 9 4 年占丹麦的 1 5 %。其他国家也有类似的数字:加拿大 1 6 y o ( 1 9 9 3 )，法国9 % ( 1 9 9 0 )。随着供应链管理和物流配送的不断发展，这个比例现在都有了大幅 度的增长。 .根据d e b a c k e r 等人1 9 9 7 年的报告 3 1货物运输费用占了整个产品成本的 一半左右，某些行业，如食品和饮料等，这个比例可高达7 0 %. .h a l s e 引用丹麦一份报纸的资料指出4 1 , 1 9 8 9 年，丹麦7 6 . 5 %的货物运输 都是由 汽车来完成的， 这足以 说明 运输路径安排问 题 ( r o u t i n g p r o b l e m )的重要 性。 每个公司那怕只是减小很少一部分费用，总体上却可以节约很大一笔费用， 而且还可以减少由于污染和噪声等带给环境的压力。因此，解决不同类型的运输 路径安排问题是运筹学、应用数学、网络分析、图论和计算机应用等学科的专家 与运输计划制订者和管理者等一个很重要的研究领域。 最著名的，同时也是最简单的运输路径安排问题是旅行商问题 ( t s p )。它 讲述的是这样一个问题 5 1 :一个商人欲到 n 个城市推销商品，如何选择一条道路 使得商人从起点出发，每个城市走一遍后再回到起点所走的路径最短?图 1 -i 显示了 t s p的一个可行解，白圆圈表示出发点。 运输问题是t s p最自然的应用， 如在校区内如何安排校车路线接送学生的问题，货舱中找式起重机的路线安排， 华南理工大学硕士学位论文 图 1 一1 t s p的一个可行解 收邮包的卡车行车路线安排等。t s p在制造业中也扮演着重要角色，如如何安排 机器在一块电路板或其他物体上钻孔等。 m - t s p 是t s p的 扩展， 它描述的是这样一个问 题( 5 l : m个商人要一起将n 个 城市走完，每个城市需要且只能由一个商人来拜访一次，每个商人必须从出发点 出发，最后再返回出发点所在地。目的是确定m条路径， 使所有商人走过的总路 程最短。图 i -2 显示了m - t s p的一个可行解，白圆圈表示出发点，1 , 2 分别表 示第 1 和第2 个商人走过的路径。 刚才提到的如何安排校车路线接送学生的问题， 如果学生住的地方比较分散，则只派一辆校车去接送学生，不仅校车要兜很多路 去接住在不同地方的学生，非常耗时，而且学生的正常作息时间也会受到影响， 有些学生为了搭车，必须很早起床。因此，派几辆校车同时去接住在不同地方的 学生是比较合实际的。 图1 一2 m - t s p的一个可行解 车辆路径问题 ( v e h i c l e r o u t i n g p r o b l e m, v p r )也是一个m -t s p ，只不过 每一个城市附加了一个对货物的需求量，每一辆汽车都有一定的载重量 ( 不必都 相同)。 不过v r p还是有别于m - t s p的， m-t s p实质上只是由城市的地理位置 决定的， 而v r p却不能，因为需求的加入构成了问题的一个约束条件。 后来有人 把这种v r p 严格定义为c v r p ( c a p a c i t a t e d v e h i c l e r o u t i n g p r o b l e m ) ，因为每辆 汽车 ( 即每条路径)装的货物总量不能超过汽车的最大负载。 从以上分析可以看出， v r p是比t s p , m - t s p都要复杂的一类运输路径安排 第一章绪 论 问题，同时也是更符合实际情况的一类模型。由于汽车都是有最大负载的，因此 前面提到的校车接送学生路线安排问题更切实际的模型应该是v r p ， 这也进一步 说明了v r p在现实生活中的实用性。 图 1 -3 显示了v r p的一个可行解。 值得注 意的是，前面以及这儿给出的都是对称情形，即从城市 i 到城市.1 的路程与从城 市j 到城市i 是相等的。 图1 - 3 v r p的一个可行解 1 . 1 . 2 v r p的主要类型 v r p其实是一大类问题的基本模型，在此基础上还可以添加许多附加条件， 从而构成不同 类型的v r p 。主要的附加条件有 6 ) ( 1 ) v r p t w ( 带有时间窗的v r p ):每一个客户 ( 包括出发点d e p o r t )都对 应有一个时间窗 a ; , 瓦 】 。 汽车可以 在时刻a 之前到达该客户所在地，但它必须等 待直到a 才可以为该客户服务， 并且不允许迟于b , 到达。 有些情况下允许汽车提 前或者晚一些到达客户 ( 也称之为带有软时间窗口的v r p , v r p s t w )，只是相 应地要给予惩罚，比如迟到了可能会给客户带来一些损失，从而可以转嫁到运输 费用上，引起运输费用的增加等。本文不讨论带有软时间窗口的v r p o ( 2 ) v r p l c( 带有运行时间约束的v r p ):每辆汽车运行的时间不能超过预 先给定的界 l 。每辆汽车的运行时间由汽车在客户间的行驶时间和汽车为客户服 务的时间所构成。 ( 3 ) mv r p ( 多处发点的v r p ) :允许从多个不同的出发点出发给客户供货。 ( 4 ) s d v r p( 可切分供货) :一个客户的需求可以同时由若干辆汽车来满足。 该模型下求得的解至少都和正常的v r p一样好，因而可以充分利用汽车的资源， 从而节省汽车。 ( 5 )随机v r p ( s v r p ) 。某些值，如客户的数目、客户的需求、客户的服务时 华南理工大学硕士学位论文 间不是事先确定的，而是随机变化的。 这些问题都是很 “ 难”求解的 (“ 难解”的确切定义见下一小节)，而且在 现实中都有着广泛的应用价值。例如，单机调度问题，己知每个工序的加工时间 以及从一个工序切换到另一个工序的时间，如何安排工序在机器上的加工顺序使 得完工时间最早? 这个问 题可以看成是v r p t w:一个d e p o t ，机器相当于汽车， 工序相当于客户，从一个工序切换到另一个工序的时间相当于客户间的距离，工 序的加工时间相当于汽车为客户服务的时间。还有其他的运输问题、排序问题和 快递收发路线编排、 邮政投递、 火车及公共汽车的调度等都可以归结为v r p t w, 但处理的好坏将直接影响到一个企业的效益和客户的服务质量，所以对它的研究 越来越受到人们的重视。因此本文主要考虑的是v r p t w. 1 . 2 组合优化及计算复杂性理论 组合 最优化7 ( c o m b i n a t o r i a l o p t i m i z a t i o n ) 是通过 对数学方法的 研究去寻找 离散事件的最优编排、分组、次序或筛选等，所研究的问题涉及信息技术、经济 管理、 工业工程、 交通运输、 通信网络等诸多领域。 该问题可用数学模型描述为: mi n f ( x) s .r . g ( x) o , xed 其中，f ( x ) 为目 标函 数，g ( x ) 为约束函数，x为决策变量，d 表示有限个点组 成的集合。 一个组合最优化问题可用三个参数( d , f , f ) 表示，其中d表示决策变量的定 义域， f 表示可行解区 域f = ( xi x e d , g ( x ) 0 ) , f 中的任何一个元素称为该问 题的可行解， f 表示目 标函数。 满足f ( x * ) = m i n f f ( x ) i xe f 的可行解x 称为该 问题的最优解。现实生活中大量的问题都是组合优化问题，如 0 -1背包问题， t s p ，装箱问题等。组合最优化的特点是可行解集合为有限点集。由直观可知， 只要将d中有限个点逐一判别是否满足g ( x ) ? 0 的约束和比较目 标值的大小，该 问题的最优解一定存在和可以得到。然而枚举是以时间为代价的，有的枚举时间 还可以接受，有的则不能接受。例如非对称 t s p ,枚举 3 0 个城市，需要 1 0 . =允许为客户 b i =允许为客户 变量 i 服务的最早时间，令a o = 0 o i 服务的最晚时间 如果 汽车 k 7 顾客 服务 完 后直 接开往顾苟 否则 ( v r p t w ) m in yy,y , , x , ( 2 - 1 ) 胜f掩n j e n , ,x rk - 1 艺 d i 艺 z uk : r k kc大n e x . , = 1 vi e c ( 2 - 2 ) 丫无 任v ( 2 - 3 ) v 壳v ( 2 - 4 ) ix . -x , = q v h 住c, v k cv( 2 - 5 ) 艺 x i,n + l.k 二 1 s ik 十 a i 十 t , 一 a ; s s , 热 x l k 。 1 0 ,1 1 vk e v ( 2 - 6 ) t ( 1 一 x , k ) s k v i , j e n, v k e v ( 2 - 7 ) v i e n , v k e v ( 2 - 约束( 2 - 3 ) 说明任一辆 汽车装载的货物都不能超过它的最大载重量; ( 2 - 4 ) , ( 2 - 5 ) 和( 2 - 6 ) 保证每辆汽车始 于出发点， 访问客户后， 最终返回出发点; 不等式( 2 - 7 ) 表达了汽车k 在从客户i 向 华南理工大学硕士学位论文 客 户i 行 使 的 过 程中 ， 在s jk + c r 十 与 之 前 不 能 到 达 客 户i i 其 中t 是 一 个 大的 标 量; ( 2 - 8 ) 表达了在汽车的行使过程中要满足时间窗的约束;条件( 2 - 9 ) 是整数化的约 束。 这个模型通用型很强，经过参数的不同设定，可以将其转换为其他组合优化 问 题的 数学模型。 如果我们设定a ; = 0 ,愁 = m ( m是一个很大的数) ， 则可以把 时间约束( 2 - 7 ) 和( 2 - 8 ) 去掉，这样， v r p t w模型就变成了普通的v r p 模型;如果 只提供一辆汽车，则该问题就是 t s p了;如果有多辆汽车利用，并且附加条件 殉= 1 , j e c 和t ， = 0 ， 我们就得到了 装箱问 题的 数学 模型 如果去掉 汽车载重量 约束( 2 - 3 ) ， 则该模型就变成了m - t s p t w的问题模型; 如果仅有一辆汽车被利用， 又变成了t s p t w 的问题模型;如果去掉约束( 2 - 2 ) ，对每个车辆模型变成了基本 的有时间窗和能力约束的最短路径问题，由于所有的车辆相同，所以每个汽车的 最短路也是相同的。 2 . 2 求解 v r p t w算法回顾 自1 9 5 9 年g . d a n t z i g + i l 首先提出v r p以 来，很快引起运筹学、 应用数学、 网络分析、图论和计算机应用等学科的专家与运输计划制订者和管理者的极大重 视。历经多年的研究发展，衍生出多种不同类型的问题。而有时间窗的车辆路径 问题v r p t w 由于其在现实生活中的实用性，所以对它的研究越来越受到人们的 重视:从早期的精确算法研究，到9 0 年代的各种h e u r i s t i c s 算法研究，到遗传算 法、禁忌搜索、模拟退火和神经网络等智能化方法的研究。 己被证明v r p t w是一个n p -h a r d ， 因而寻找其实际而有效的算法显得颇为 重要。遗憾的是，计算复杂性理论告诉我们的结论是:这种可能性尚属未知。尽 管己有一些指数级的算法可精确地求解 v r p t w，但随着它们在大规模问题上的 失效 ( 组合爆炸)，人们只能退而求次之，转向寻找近似算法或启发式算法。下 面我们来回顾一下己有的一些求解算法。以下算法主要是针对 v r p t w 的。当然 有些算法对于其他的v r p也是适用的。 2 . 2 . 1精确算法 ( 1 )集分割和列生成。v r p的集分割是由 b a l i n s k i 1 z 1 等人提出的。它直接考 虑可行解集合，在此基础上进行优化，因此建立的v r p模型最为简单。 其缺陷在 于，如果问题所受约束不严格，则所需要计算的状态空间非常大。另外，要确定 每个可行解的最小成本也是件困难的事情。对于其中规模相对较小、约束严格的 问题，可通过线性松弛，引入割平面进行求解。在该方法中，原问题被转化为简 化问题，考虑的范围是所有可能的可行解的子集。在此基础上反复求解。通过引 第二章 v r mv 的研究现状 入优化对偶变量向a，对该简化问题松弛，通过计算列的最小边际成本，确定最 优解。其算法本质上是最短路径算法，同时结合了分枝定界算法。d e s r o c h e r s用 它求解有 1 0 0 个客户的带时间窗口的v r p . ( z ) 三下标车辆流方程。 f i s h e r 1 3 1 等人针对带能力约束、 时间窗口以 及无停留 时间的v r p ， 提出了三下标车辆流方程。 在该方程中， 其中两个下标表示弧或边， 另外一个下标表示特定车辆的序号。基于 b e n d e r s 的分解算法，他们提出了一种 启发式算法，保证在有限步内找到最优解。f i s h e r 等人用它计算了有 5 0 -1 9 9 个 客户的v r p . ma r t e l l o 和d e s r o c h e r s 分别提出了相应的改进算法。 ( 3 )分枝定界算法。该算法是 f i s h e r j 1 4 1最早提出的。 它的核心思想是将解空 间划分为若干个小的子空间， 再依次搜索各个子空间。 通过与当前最好解的比较， 可以剪去那些不可能产生最优解的分枝，只搜索那些能产生最优解的分枝。它可 以解决 1 0 0 个客户的c v r p v r p t w等。 总的来说，精确算法在可以求解的情况下，其解通常要优于近似算法。但由 于引入严格的数学方法，因而无法避开指数爆炸问题，从而使该类算法只能有效 求解中小规模的v r p t w a 2 . 2 . 2近似算法 在求解大规模v r p t w时，近似算法总可以在有限时间里，找到满意的次优 解或可行解， 这是精确算法难以做到的。 因此在实际应用中， 近似算法要更广泛。 常见的有特色的近似算法主要有两大类。 第一类是h e u r i s t i c s ， 这类算法只搜索解 空间中相对有限的一部分子空间，力求在比较合理的时间内取得比较好的解。它 又分为两小类算法:路径构造算法 ( 包括节约法，匹配算法，路径改进算法等)， 两阶段算法 先聚类后构造路径法，先构造路径后聚类法等);第二类是 m e t a h e u r i s t i c s ， 这类算法的侧重点放在搜索最有可能产生最优解的区域， 并对该 空间进行比较全面的搜索。这类算法产生的解的质量通常比典型的 h e u r i s t i “ 要 高。主要包括蚁群算法，约束规划，遗传算法，禁忌搜索等算法。 he u r i s t i c s ( 1 ) 节约算法 ( s a v i n g s a l g o r i t h m s ) 节约法是求解v r p和v r p t w 的一种非常流行的方法。 它是 1 9 5 4 年由c l a r k e 和 w r i g h t ( i s 基于 d a n t z i g和 r a m s e r i i i 的思想提出来的，因此也称之为 c l a r k e - w r i g h t 算法。该算法最初按所需访问的客户数n( 不含出发点) 生成同 样数 量 的 路 径， 计 算 合 并 任 意 两 条 路 径 后 可以 节 省 的 成 本 量s o = d 1。 十 d . j - d t 然 后 对 可节省的成本量进行排序。 最后根据排序结果以及可行性条件， 对路径进行合并， 华南理工大学硕士学位论文 直到无法找到更好的解。 ( 这里的合并是指:去掉分别位于原来两条路径中的弧 ( t , 4 ) , ( 0 1 j ) ，用( i , j ) 代替)。对于v r p t w，这种算法的复杂度为) ( n o ) a g o l d e n , n e l s o n , p a e s e n s 1 6 1等人通过使用适当的数据结构和技巧， 使其复杂度降 低为。 ( n ) . ( 2 )向前插入法 ( p u s h - f o r w a r d i n s e r t i o n h e u r i s t i c , p f i h ) 最初是s o l o m o n 1将 p f i h引进到带有时间窗口的车辆路径问题中。这种方 法 是 逐 个 将 未 访问 过 的 客 户 加 入 到 路 径当 中 假 设 一 条 路 径为 r p = q ， .,c 卜下 一个加入到当前路径的客户是如下选取的:计算所有未访问客户的最佳插入点: 把 一 个 客 户 插 入 到r ， 中 的 任 何 一 条 边， 计 算 新 路 径 的 总 旅 行距 离 ， 选出 使 总 旅 行 距离达到最小的位置。然后在未访问客户中选择一个使总旅行距离最小的客户， 即 是 下 一 个 加 入 到r ， 的 客 户， 将 其 插 入 到 最 佳 位 置 重 复 此 过 程， 直 到 插 入 任 何 一个未访问过的客户或者导致当前路径超载，或者不满足该客户的时间窗口时， 则重新开辟一条路径。再按照一定的规则选出一条路径的第一个客户。再重复上 面的过程，直到所有的客户都插入到合适的路径为止。 ( 3 )路径改进算法 这类算法是在一个可行解或者某种近似算法产生的最好解的基础上进行进一 步的 优化， 主要采用的算子有 2 - o p t , c r o s s o v e r , r e l o c a t i o n , e x c h a n g e , c y c l i c t r a n s f o r 等 l a ) 2 - o p t o p e r a t o r 图2 一1 2 - e x c h a n g e o p e r a t o r 考虑一条路径中不相邻的两条边，如上图2 - 1 , ( i , i + i ) , ( j j十 1 ) ，如果将它 们删除， 用( i , j ) , ( i + l , j + i ) 两条边代替后可以 减少总的 行驶路程， 则进行替换并 继续此过程。 注意此时要逆转介于i 十 1 和j 之间的 所有客户的顺序。 该过程就叫做 2 - e x c h a n g e 。如果对一己 知解t ，不能通过2 - e x c h a n g e 得到进一步优化，则t就 是2 - o p t i m a l ，算法结束。 2 - o p t 可以 很自 然的 推广到k - o p t ， 只要我们考虑一条路径中 所有大小为k 或 第二章 v r p t w的 研究现状 最多为 k的子集。但问题是，子集的个数是 k的指数集，基于这个原因，k - o p t 当k 3时很少使用。 c r o s s o v e r o p e r a t o r 图2 一2 c r o s s o v e r o p e r a t o r 不同于2 - o p t ，该算子是交换两条不同路径中的两条边，如上图2 -2 , i 的 后续节点i 十 1 被重新插入到另一条路径j 的后面， 而j 原来的后续节点j 十 1 被插入 到i 的后面。 此过程相当于用( i , j + l ) , ( j , i + l ) 替换( i , i + l ) , ( j , j + l ) 。如果对一己 知解t ，不能通过c r o s s o v e r 得到进一步优化，则t就是c r o s s o v e r - o p t i m a l ，算 法结束。 r e l o c a t i o n o p e r a t o r 该算子是从一条路径中移走一个客户， 然后将它插到另外一条路径上， 如下 图2 -3 所示。 可以将此算子进一步扩展:每次从一条路径上移走多个客户，这些客户可 i - 1 i + l i - 1 i +1 j j + 1j 一 j + 1 图2 一3 c r o s s o v e r o p e r a t o r 以是连续的，也可以是分散在路径不同地方的。只不过这时插到另一条路径上将 会有很多种不同的插入组合。 e x c h a n g e o p e r a t o r 如下图 2 -4所示。 华南理工大学硕士学位论文 图2 一4 e x c h a n g e o p e r a t o r c y c l i c t r a n s f e r o p e r a t o r 如下图 2 一5所示。 图2 一5 c y c l i c t a n s f e r o p e r a t o r ( 4 ) g i d e o n算法 ( 两阶段算法) 这是t h a n g i a h 1 9 在1 9 9 5 年提出的。 该算法第一 阶段用遗传算 法将客户 聚 类， 在每一类中 按照最廉价插入法 t h e c h e a p e s t i n s e r t i o n ) 形成各条子路径:第二阶 段再使用a - i n t e r c h a n g e 算法来进一步优化第一阶段所得到的最好解， 主要是在各 子路径间进行客户的交换，以减少总行程。该算法的优点是，在计算过程中，考 虑了所需要访问的点数量增加的情况。 me t a h e u r i s t i c s 算法 ( 1 )禁忌搜索算法 g e n d r e a u t2 o l等人最先将该方法应用于v r p 。 先构造一系列的 解， 然后对所得 解不断地进行改进。该算法所得的解不一定是可行的，它们对可行性的偏离程度 是通过目标函数里的惩罚函数来体现的。 该算法求解过程中的邻域， 是通g n e n i 过程得到的。 它是针对v r p的比较好的启发式算法， 可以成功地应用于许多经典 的v r p 。 其后e . t a i l l a r d f2 1 1 等人通过按角 度和路径重心对原问 题的空间 进行分割， 再用禁忌搜索结合模拟退火对子问题进行求解，实现了对问题求解的并行化。后 来k . q . z h u 2 2 1等人对其 进行了 改进，并成功应用于v r p t w中。 第二章 v r p t w的 研究现状 ( 2 )模拟退火算法 这是一种源于5 0 年代，基于mo n t e c a r l o 迭代求解思想的随机搜索算法，其 出发点是将组合优化问题与统计力学的热平衡作类比，把优化的目标函数视作能 量函数，模仿物理学中固体物质的退火处理，先加温使之具有足够高的能量，然 后再逐渐降温，其内部能量也相应下降，在热平衡条件下，物体内部处于不同状 态的概率服从b o l t z m a n分布，若退火步骤恰当，则最终会形成最低能量的基态。 这种算法思想在求解优化问题时，不但接受对目标m数有改进的状态，还以某种 概率接受使目标函数恶化的状态，从而可使之避免过早收敛到某个局部极值点， 故通常可以得到比较好的解。 模拟退火算法得到的解的好坏与初始状态、温度函数等都有一定的联系，降 温较快的效果不一定很好，效果好的往往降温过程又极其漫长。但由于该方法适 用范围 广， 并可人为控制迭代次数， 反复求解， 因 此具有很强的实用性。 k . q . z h u 2 2 1 等人通过恰当地设置上述参数，并当温度降得很低或者邻域内没有可行移动时， 加入重设温度过程，使得接受恶化状态的概率不至于太小，有效避免收敛到某个 局部最优。 ( 3 ) 遗传算法 j . l a w r e n c e 2 3 1 最先将该方法用于 v r p的研究，并可有效求解 v r p t w a鉴 于传统的遗传算法是个大范围、粗粒度的寻优算法，因此 b a r m i e r 2 4 将它与约束 满足问题 ( c s p )的技术相结合，通过遗传算法来处理c s p参数的子域 ( 基因的 适应度是通过对 c s p解的计算得到的)，从而减少搜索空间，降低 c s p问题目 标函数和遗传算法约束的复杂度。 我国张涛t 2 5 等人则通过遗传算法来保证搜索的 全局性，用3 -o p t算法来加强局部搜索能力，得到针对v r p的混合算法。 这类 算法目前己可以求解较大规模的问题 ( 1 9 9 个客户)。 2 . 3 算法的实验评价 对同一个问题可以有很多种不同的求解算法。当我们面对众多的算法时，我 们到底该选择哪种算法来求解呢? 2 . 3 . 1评价各种算法的标准 比较各种不同的算法的效果，可以有很多个标准，比如，算法的运行时间、 最好解的质量、 算法实现的难易程度、 鲁棒性和灵活性等 2 6 1 。灵活性指的是一种 好的算法应该能够很容易地对付模型、约束条件和目 标函数的微小改变。而鲁棒 性指的是，即使在非常困难的条件下， 如病态的例子， 该算法也能产生最终结果。 解的质量，可以通过该解与最优解的接近程度来度量。如果一种算法只是设计来 华南理工大学硕士学位论文 产生可行解，那它能产生可行解的能力就是评价解的质量的重要因素。算法的运 行时间可以从两个方面来考虑:一是算法搜索到最好解所需要的时间，二是给定 运行时间， 算法能搜索到的最好解。 运行时间当然是与计算机c p u速度、内存大 小、所用的编程语言和编译器等密切相关的。 2 . 3 . 2如何评价各种算法的优劣 我们在实际比较各种算法的效果时，却面临诸多问题:各个作者使用的计算 机配置不同;每个作者的编码技术不同:通常作者报告的只是找到的最好解，而 没有提到运行的时间，迭代的次数等。由于这些问题的存在，使得各种算法之间 很难进行公正的比较。为了能够得出比较合理的结论，我们建议从以下几个方面 来考虑。 ( 1 )使用相同的测试数据 目前比较通用的方法是用一组包含各种情况的测试用例来实验，从而可以比 较全面的分析一种算法在各种形态下的执行效果。同时，由于各种算法都使用了 相同的测试数据，因此便于比较各种算法所得到的最好解。 ( 4 ) 跟踪时间和解之间的关系 我们不只应该关注算法的运行时间和迭代的次数， 还必须弄清楚诸如此类的 问题:这种算法能达到的最好解是什么?在给定的时间内，算法能得到什么样的 解?我们可以用图形来描述解的质量和运行时间之间的关系，借助图形可以让我 们更清楚地了解各种算法的寻优能力。 ( 3 )处理好运行时间和解的质量的关系1 2 6 1 一般情况下，算法运行的时间越长，得到的最好解也越好。因此我们需要在 运行时间和解的质量之间找一个平衡点在合理的时间内找到比较好的解。这 种期望也来自求解多目标与多态优化问题的需要。我们知道，一个多目标优化问 题可以描述作 v 一 二 f ( x ) = ( f ( x ) f ( x ) , .-, f , ( x ) ) s 1 . x sqc r a ( 2 - 1 0 ) 这里v - m i n 代表向量极小化，即需要寻找这样的最优解x . ，它使得每一个目 标 几( ， 无 5 0 %* ? 5 %, 1 0 0 %e r 2 . c 1 和 r c l 类中的每一个例子中的中心 仓库具有较窄的时间窗，这使得每辆车能够服务的客户数较少，实际负载较小， 因此一般需要 9到 1 9辆汽车。而 r 2 , c 2 和 r c 2 类中的每一个例子中的中心仓 库具有较宽的时间窗，这使得每辆车可以为比较多的客户服务，具有较大的实际 负载， 因此一般只需要2 到4 辆汽车。 所有的距离和时间都是以点之间的e u c l i d e a n 距离计算的。 2 . 5本章小结 本章详细阐明了v r p t w 的数学模型，着重介绍了近二十年 v r p t w研究所 取