（计算机应用技术专业论文）基于ia与ts的带时间窗车辆路径优化算法研究.pdf

，u 5 3 仿真实验的实现与分析2 6 5 3 1s o l o m o nb e n c h m a r k 测试集数据的仿真实验实现2 6 5 3 2 实验结果与分析2 8 第6 章结束语3 5 6 1 总结3 5 6 2 展望3 5 参考文献3 6 致谢3 8 硕士期间发表的论文3 9 t k r l 摘要 研究车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 的相关理论和算法是为了降低物流的成 本。该问题通过规划出合理的行驶路线来实现运输成本的最小化。这个问题是运筹学和组合 优化领域的研究热点。对这个问题的不断深入研究使得它已经延伸出了许多新的研究分支。 本文首先分析了目前车辆路径问题的研究现状，再结合实际提出了本文的研究问题带时 间窗的车辆路径问题( v r p t w ) 。通过对带时间窗车辆路径问题的数学建模，明确定义了问 题的目标函数和约束条件。在考虑了配送的距离、配送的时间性和配送的车辆数等冈素的影 响，最后构建了以配送总路径最短为目标。在分析了目前多种求解方法后，本文采用的是免 疫禁忌搜索算法的混合策略。 首先，对禁忌搜索算法和免疫算法分别进行了分析。了解了禁忌搜索算法的求解思想，重 点是渴望水平的设计，针对车辆路径问题目标函数的特点求解最短路径，将禁忌搜索算法渴 望水平设计为与目标函数相同的函数。对t s p 问题分别用禁忌搜索算法、遗传算法和蚁群算 法进行了求解。用平均值，方差和平均计算时间进行了比较，实验验证了禁忌搜索算法的有 效性，同时验证了对初始解的依赖性。其次了解了免疫算法的算法思想，免疫算法的特点是 疫苗的提取。用t s p 问题验证了免疫算法能够在全局范围内求得最优解，从实验的结果验证 了免疫算法改进了遗传算法的不足。最后介绍了免疫禁忌搜索算法的混合策略的算法，本文 是通过免疫算法产生的最优解作为禁忌搜索算法的初始解，设计了适合建立的数学模型的编 码方式和渴望水平和亲和度等。 本文应用s o l o m o nb e n c h m a r k 测试数据集进行了仿真实验，利用m a t l a b 软件计算出了 最优目标函数值和最优配送路径方案，通过对实验结果的分析，验证了所建模型和求解算法 对s o l o m o nb e n c h m a r k 测试集中的r 类和r c 类数据是合理并有效的。 关键字：车辆路径问题，时间窗，禁忌搜索算法，免疫算法 i ， s u p e r v i s o r ：p r o f d e n gh u i w e n a u t h o r ：w a n gr o n g ( 112 0 0 8 3 2 10 018 7 6 ) a bs t r a c t r e s e a r c ht h er e l a t e dt h e o r ya n dm e t h o do fv e h i c l er o u t i n gp r o b l e m ( v r p ) i st or e d u c et h e c o s t so fp h y s i c a ld i s t r i b u t i o n ，w h i c hi sa no p t i m i z a t i o np r o b l e mb yr e a s o n a b l ys c h e m i n gd r i v i n g r o u t et om i n i m i z et h ec o s t so ft r a n s p o r t a t i o n ，a n di ti sah o tr e s e a r c hi no p e r a t i o n a lr e s e a r c ha n d c o m b i n a t o r i a lo p t i m i z a t i o nf i e l d s t h r o u g hd e e p l yr e s e a r c h i n gt h i sp r o b l e m ，m a n yn e wr e s e a r c h b r a n c h e sh a v eb e e ne x t e n d e df r o mt h i sp r o b l e m t h i sp a p e rf i r s ta n a l y z e st h er e s e a r c hc u r r e n t s i t u a t i o no fv r p a n dt h e np r e s e n t st h er e s e a r c hp r o b l e mo ft h i sp a p e r - v e h i c l er o u t i n gp r o b l e mw i t h t i m ew i n d o w s ( v r p t w ) 一c o m b i n i n gt h ea c t u a ls i t u a t i o n b yb u i l d i n gt h em a t h e m a t i c a lm o d e l i n go f b a s e do nt h ev e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，t h i sp a p e rc l e a r l yd e f i n e st h et a r g e t f u n c t i o na n dt h ec o n s t r a i n t sc o n d i t i o no f 心a f t e rc o n s i d e r i n gt h ei n f l u e n c e so ft h ed i s p a t c h i n g d i s t a n c e ，t i m ea n dt h en u m b e ro fv e h i c l e s ，t h i sp a p e rf i n a l l yc o n s t r u c t st h eg o a lo fs h o r t e s t d i s p a t c h i n gt o t a ld i s t a n c e a f t e ra n a l y z i n gt h ec u r r e n tv a r i e t ys o l v i n gm e t h o d s ，t h i sp a p e ru s em i x e d s t r a t e g yo fi m m u n ea l g o r i t h ma n dt a b us e a r c h f i r s t l y ，t h i sp a p e ra n a l y z e st h et a b us e a r c ha n di m m u n ea l g o r i t h mr e s p e c t i v e l y ，a n da n a l y z e s t h es o l v i n gt h o u g h to ft a b us e a r c h ，e s p e c i a l l yt h ed e s i g no fa s p i r a t i o nl e v e l a f t e ru n d e r s t a n d i n gt h e f e a t u r et h a tt h et a r g e tf u n c t i o n so fv r pi st h es h o r t e s td i s t a n c e ，t h i sp a p e rt a k e st h et a r g e tf u n c t i o na s t h ea s p i r a t i o nl e v e lo ft a b us e a r c h b ym a k i n gac o m p a r i s o no fa v e r a g e ，v a r i a n c ea n da v e r a g e c o m p u t i n gt i m e ，t a b us e a r c h , t h i sp a p e ru s et a b ua l g o r i t h m ，g e n e t i ca l g o r i t h ma n da n tc o l o n y a l g o r i t h mt os o l v et s p t h i sp a p e ro b t a i n st h ev a l i d i t yo f t h ea l g o r i t h mo ft a b us e a r c ha n dp r o v et h e i n d e p e n d e n c eo fi n i t i a ls o l u t i o n s e c o n d l y ，t h i sp a p e ra n a l y z e st h et h o u g h to fi m m u n ea l g o r i t h m ，a n d k n o w st h a tt h ef e a t u r eo fi m m u n ea l g o r i t h mi se x t r a c t i o nv a c c i n e a n dt h i sp a p e rp r o v e st h a t i m m u n ea l g o r i t h mc a ng e tt h eo p t i m a ls o l u t i o ni ng l o b a ls c o p e ，a n dv e r i f i e si m m u n ea l g o r i t h mc a n i m p r o v et h es h o r t a g eo fg e n e t i ca l g o r i t h m f i n a l l y ，t h i sp a p e ri n t r o d u c e st h ea l g o r i t h mo fm i x e d 伟t、 f i 一 两南火学硕十学位论文a b s t r a c t s t r a t e g yo fi m m u n ea l g o r i t h ma n dt a b us e 锄c h a n dt a k e st h eo p t i m a ls o l u t i o no fi m m u n ea l g o r i t h m a st h ei n i t i a ls o l u t i o no ft a b us e a r c h a n dt h i sp a p e rd e s i g nt h ec o d i n gw a yo fb u i l d i n gm a t h e m a t i c a l m o d e l i n ga n dt h ea f f i n i t yo fa s p i r a t i o nl e v e l t h i sp a p e rc o n d u c t ss i m u l a t i o ne x p e r i m e n t sb yu s i n gt h et e s td a t as e t so fs o l o m o nb e n c h m a r k i nm a t l a b ，a n dc a l c u l a t e st h eb e s tt a r g e tf u n c t i o na n dt h eb e s td i s p a t c h i n gd i s t a n c e ，a n dp r o v e st h e r e a s o n a b i l i t ya n de f f e c t i v e n e s so fm a t h e m a t i c a lm o d e la n ds o l u t i o na l g o r i t h mf o rc l a s sra n dc l a s s r co fs o l o m o nb e n c h m a r kt e s ts e tb ya n a l y z i n gt h er e s u l to fe x p e r i m e n t s k e y w o d s ：v e h i c l er o u t i n gp r o b l e m ，t h et i m ew i n d o w , t a b us e a r c ha l g o r i t h m ，i m m u n ea l g o r i t h m 小规模的车辆路径优化问题，对于较大规模的车辆路径优化问题，算法计算时间随问题规模 的增长呈指数化增加。冈此现在的学者都应用智能优化算法来解决这类问题，试图寻找优化 解。 s a v e l s b e r g h 和s o l o m o n 指出带时间窗的姆比一般的冲更加复杂，带时间窗的心 问题更加接近现实问题，它要求车辆必须在客户要求的时间内到达。 近年来一些学者针对动态v r p 问题进行了一定的研究，这些算法在v r p 的求解结果方面 有了一定程度的改进，但每一种算法都会存在一些缺陷，而且随着社会的发展，问题规模不 断扩大化，结构不断复杂化，单一的算法很难解决现实中复杂化的问题。如果在考虑用户需 求及车辆行驶时间等多个约束条件随机变动的情况下，虽然可以建立车辆路径问题的数学模 型，但是用单个方法难以实现对车辆路径问题的求解。 现代智能优化算法中的禁忌搜索算法是最早应用于车辆路径优化问题的算法。禁忌搜索 ( ；t a b us e a r c h ，t s ) 是对人类智力过程的一种模拟，是人工智能的一种体现，它通过引入一 个灵活的存储结构和相应的禁总准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的 优良状态，进而保证多样化的有效探索以最终实现全局优化。禁忌搜索算法的最终目的正是 带时间窗车辆路径优化问题期望达到的目标。 同时由于t s 算法的一些局限性使得产生t s 算法与其他算法混合优化策略的产生。尽管 禁忌搜索算法与免疫算法之间有很大的区别，但是也存在着一定的内在联系，可以在很大范 围内混合两种算法来进行优化。 综上所述，随着社会经济的发展，以运筹学以及计算机科学为基础的优化建模技术将被 越来越多地应用到各个领域以降低运作成本。在此基础上，运用运筹学以及智能优化算法等 工具，对标准车辆路径问题的假设条件引入新的约束，研究满足经济实际需要的各种类型的 车辆路径问题，同时构建高质量的求解算法的具有重要的理论意义和实践价值。 1 2 研究的内容 本文是在前人的基础上对车辆路径问题做更进一步的研究，通过结合不同的人工智能式 的启发式算法，来达到弥补它们之间的缺陷，期望提高算法的效率。该文研究的内容主要有 以下几个方面： ( 1 ) 带时间窗车辆问题的数学模型； 本文选择的是三下标的车辆流模型，对带时间窗的车辆路径问题的最终目标和约束条件 l 两南人学硕十学伊论文 a b s t r a c t 转换成数学表达方式。 ( 2 ) 免疫算法的设计方法； 从生物的角度引入了人工免疫算法的概念，把免疫算法与遗传算法进行比较，通过人工 免疫算法中的免疫疫苗提高遗传算法中过早收敛的缺陷。 ( 3 ) 禁忌搜索算法的设计方法； 禁忌搜索算法是目前所用智能算法求解该问题的得到最好解，但是由于禁忌搜索算法较 大的依赖于给定的初始解，如何给出初始解是人家目前研究的个重点。 ( 4 ) 免疫算法与禁忌搜索算法的结合； 由于免疫算法具有提取免疫疫苗的功能使得在求解问题的时候是根据问题本身的特征来 得到最优解，于是能够得到局部最优，而把这样的结果最为禁忌算法的初始解则能够让禁忌 算法发挥出它本身的特征。 ( 5 ) 运用免疫算法与禁忌搜索算法结合得到的混合策略来求解s o l o m o n 标准数据库中的 大量实例。 1 3 论文的组织结构 本文大体上可以分成三个部分，第一部分主要是研究问题的研究背景，研究现状；第二部 分是本文的重点部分，主要是研究问题的数学模型以及对该问题的算法研究。第三部分是通 过实验来验证该算法是否有效。全文共分六章，组织结构安排如下 第一章给出了带时间窗车辆路径问题的研究综述，首先介绍了车辆路径问题的几种模型及 其表示方法，然后从精确算法到启发式算法来求解该问题。由于已经证明带时间窗车辆路径 问题是n p h a r d 问题，所以对于小规模的问题可以用精确算法来求解，考虑到算法的可行性 问题对大规模的问题还是只能用启发式算法求解。从所给出的综述中也可以看出，通过改进 启发式算法对于求解带时间窗的车辆路径问题来达到更好的效率。 第二章给出了本文的主要研究内容。 第三章是对带时间窗车辆路径优化问题的建模。首先对带时间窗的车辆路径问题进行了描 述，然后用三下标的车辆流模型表示该模型。 第四章基于免疫算法和禁忌搜索算法提出了对该问题的混合策略。对免疫算法和禁忌搜索 算法分别进行介绍，详细描述免疫算法中的疫苗提取过程，介绍免疫算法中的抗体新陈代谢 和疫苗的接种。如何将免疫算法的结果作为禁忌搜索算法的初始解储存在禁忌表中。 第五章利用测试数据集s o l o m o nb e n c h m a r k 进行了仿真实验，通过实验结果进行对比与分 析，比较算法的性能。 第六章是总结本文提出的混合算法对解决带时间窗的车辆路径问题的求解方案是否可行，分 析它的优缺点。 2 两南大学硕十学位论文第2 章绪论 第2 章文献综述 2 1 车辆路径问题的模型以及算法研究的进展 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 是运筹学中一类经典的组合优化问题， 由d a n z i g 和r a m s e r 于1 9 5 9 年提出，旨在借助构造适当的车辆行驶路线来实现运输成本的最 优化。车辆路径问题是指对一系列客户点，要求合理安排车辆及其行车路径和出行时间，在 满足一定约束条件的情况下，把客户需要的货物从物流中心的仓库点运送到该客户点，并且 要满足一定的目标( 诸如路径最短、费用最小，耗费时间尽量少等) 。车辆路径问题的典型路 径如图1 1 所示。 图1 1 车辆路径问题的典型路径 不难发现车辆路径问题的根源就是运筹学中的经典问题旅行商问题( t r a v e l l i n g s a l e m a np r o b l e m ，简称t s p ) 。 它们之间的相似之处( 1 ) 车辆( 旅行商) 都是从某个站点( 城市) 出发，遍历完所有的 客户点( 城市) 之后，返回到原点( 原城市) 的过程；( 2 ) 都必须是把每个点都访问到并且只 访问一次的过程。可以将车辆路径问题看成是对多旅行商问题的一种拓展，也就是车辆路径 问题是一种带有容量约束的多旅行商问题。 车辆路径问题的最终目标是为了满足在一定约束条件下达到总运送成本最小，而总运送 成本最小通常是一种或者几种情况的综合。( 1 ) 总费用最小化车辆在完成配送任务的时候 必然会产生各种费用，比如，车辆租赁费用，车辆在行驶过程中的燃油费，停车费用等等。( 2 ) 所需要的车辆数最小化也就是完成全部配送任务所需要的车辆总数最小。假设一条路径上 只需要一辆车辆，不同的配送路径对应的配送车辆总数也是不同的。要使所需要的车辆最小 化就需要配送路径最少。( 3 ) 总距离最小化完成全部配送任务后行驶的总距离最小。( 4 ) 总时间最小化完成全部配送任务行驶的总时间最少。总时间包括车辆的行驶时间，服务 等待时间，服务时间和延迟时间等。针对最终追求的目标不同，采用的算法也是不一样的。 比如，在文献中川利用g r a s p 算法求解了以最小化总距离为次优目标的带时间窗车辆路径问 题，在文献中1 2 】利用分支定界法求解了以最小化总距离为目标的带时间窗车辆路径问题。在文 献中【3 1 利用亚启发式算法对最小化总时间的多车型带时间窗车辆路径问题进行了研究。文献中 1 4 】用一种三阶段启发式算法求解了以总配送时间最小为目标的带时间窗车辆路径问题。 3 文采用的是无向图这种方式。 a 有向连通图 b 无向连通图 图1 2 车辆路径问题的图论表示方法 ( 2 ) 数学建模表示方法 目前车辆路径问题的数学模型人致有三种方法车辆流模型【引、物资流模型【6 l 和集覆盖模 型7 1 ，本文在有向图的基础上来介绍这几种方法。 i 车辆流模型 车辆流模型中【5 】为每一条弧都分配一个变量，用来表示车辆经过每条弧的次数。其中有二 下标法和三下标法。二下标法引入变量勖表示车辆经过弧 的次数，其中，表示的是弧 的起点和终点。这种表示方法对车辆没有记录，也就是只适用于单车型的问题。而三下标法 引入变量m 表示的是车辆k 经过弧 驴的次数，引入的这个变量包含了车辆的信息，因 此这种方法比较适合多车型的问题。 如果用有向图g = 吲来抽象出配送的路径。其中净 o ，1 ，2 ，刀 表示节点集，其中 0 表示的是仓库，其余的节点表示的是客户，庐 f 户l i , e v ，游) 表示弧集， 驴表示从节点 f 到节点，的一条弧；q 表示车辆的容积，4 表示用户i 的需求量，c 。女表示车辆l j 经过弧q 户 的配送成本。并引入了决策变量： 被访问 未被访问 4 r 。k 、 i i 坳 纨介章 三 第在将型模学数的 立 建 两南人学硕十学伊论文第2 章绪论 i i 物资流模型 物资流模型与车辆流模型所不同的，它【6 】为每条弧分配的变量用来表示经过该弧的货物 量。这种模型刻画了配送各种物资的物流总量及配送路线，可以用来描述能源的流动状况。 i 集覆盖模型 从图论的角度来看，车辆路径问题实际上就是遍历完网络中所有客户点的路径集合。也 可以从集合论【7 】的角度来刻画数学模型，如果将配送中的全部可行路径看成一个集合，那么问 题的最优解应该是包括在该集合中找到能够产生最小配送成本的一个子集和。集覆盖模型为 每一条路径分配给一个决策变量中，这个变量用来表示这条路径是否包含在最优路径中。 以上三种模型，各有各的优缺点。其中最简单的是集覆盖模型，但是该模型不适用于大 规模问题的求解，而物资流模型目前还不是很成熟，不利丁约束条件的扩展。最为常见的就 是车辆流模型，该模型比较灵活，对约束条件的扩展也比较方便。本文就是采用的三下标的 车辆流模型。 在实际的物流过程中，存在着太多的不确定因素。比如道路的通畅问题，车辆的状况问 题，需求的随机性问题，这些问题都有可能会造成车辆路径问题的条件不稳定和不可预测， 给物流的控制带来负面的影响。车辆路径问题已经被证明是n p h a r d 问题了，s a v e l s b e r g h 在 1 9 8 5 年也证明了带时间窗的车辆路径问题是一个n p - h a r d 问趔引，想要得到精确解是不现实 的，只有寻找该问题的最优解，因此对该问题的启发式算法和智能算法的研究是非常重要的。 早期的研究主要是精确算法，最常见的精确算法有分支算法、动态规划方法、列生成 法和基于最短路径算法等。评价算法的性能是通过计算时间复杂度和求解规模的大小。 i 分支算法 一 如果把分支算法的可行解用树形结构来描述，分支算法的求解过程就是对树进行深度遍 历得到最优解，因此树的深度决定了算法效率的好坏。要保证该算法具有好的效率也就是要 求树的深度尽可能的低，只有通过有效的修剪规则才能达到该目的。目前一些常见的做法有 首先利用各种线性松弛技术如拉格朗日松弛方法【9 】对原问题进行松弛，通过求松弛问题的方法 得到最优解的下界，再利用精确算法或者启发式算法对原问题求得一个可行解作为最优解的 上界；最后利用得到的上、下界来制定修剪规则。如果上、下界非常的接近最优解，说明采 用的修剪规则的效果非常好，那么算法的效率也是很高的。 分支算法主要有如下几种分支切平面法；分支定界法：分支定价法 i i 动态规划方法 动态规划方法【1 0 】实际上是一种多阶段求解算法，首先要将原问题分解成若干个简单的、 易求解的子问题，并且这些子问题不是相互独立的，用状态变量把各个子问题联系起来。先 求出各个子问题的解，然后通过递归过程来求得原问题的解。这篇文章j 对开放式危险品运 输问题进行了研究，问题中运送危险品的卡车允许停留在某一用户节点，文献利用动态规划 方法进行了求解并取得了较好的结果。 i 列生成法 列生成法的基本思想【9 】是：找到原问题的一个简化问题，先求解这个简化问题，然后通过 5 ， 两南火学硕十学伊论文第2 章绪论 反复迭代求得最小边际效益对应的最优解。由于该算法是从简化问题出发，计算的复杂度就 大大的降低了，相对于其他精确算法，该算法可以用来求解较大规模的车辆路径问题。文献【1 2 l 对实时制装卸问题进行了研究，分别利用列生成法和禁忌搜索算法对问题进行了求解，并通 过实验说明了算法的有效性。 基于最短路径算法等 文献基于原始的最短路径算法设计出一种精确算法用于单车带时间窗的车辆路径问题 求解，实验说明算法可以有效处理2 5 到3 8 个用户规模的问题。 当问题的规模较大的时候，上述的精确算法不能够在有效的时间内求得问题的解，通常 情况下只能用启发式算法来求得一个满意解。对这类算法的性能评价一般是用算法的鲁棒性、 求解的效率和解的性能来衡量。搜索的范围不同又把这类算法分成传统的启发式算法和人工 智能的启发式算法。传统的启发式算法进行的是局部搜索，它的缺点是容易陷入局部最优； 而人工智能的启发式算法进行的是全局搜索。这种算法它的要求更高，需要提供初始解。比 较常见的启发式算法有如下几种： i s w e e p 算法 s w e e p 算法是一种逆时针扫描算法，它从当前节点开始进行逆时针扫描，选择与当前节 点极角夹角最小的节点来构造路径。文献【1 4 】利用s w e e p 算法求解了满载配送的基本车辆路径 问题，实验证明了s w e e p 算法具有较强的鲁棒性。 贪婪算法 贪婪算法的基本思想是：从站点开始，依次选择离当前节点最近的节点构造路径。文献【1 5 】 研究了带服务半径的服务站截流选址问题，建立了o 1 整数规划模型，并利用贪婪算法对问 题求解，实验表明算法求得的满意解与最优解是比较接近的。 i i i 禁忌搜索算法 禁忌搜索算法是g l o v e r 于1 9 8 6 年提出的一种基于人工智能的启发式算法，它的基本思想 是：利用禁忌表来记录到达过的局部最优点或其过程，让其在下一次搜索时有选择地搜索这 些点或者过程，这样就能跳出局部最优。文献【l6 】利用禁忌搜索算法求解了非满载的车辆路径 问题，实验表明用禁忌搜索算法求解对解的改进是非常明显的。 蚁群算法 d o r i g om 等于1 9 9 2 年根据蚂蚁的正反馈特征提出了一种叫做蚂蚁的系统( a n ts y s t e m ， a s ) 的优化方法，该算法的模型是基于人工蚂蚁的特点设计出来的。蚁群算法的基本思想是： 通过正反馈、分布式协作来寻找最优路径。文献【1 7 1 采用一种基于最大一最小蚁群系统的改进蚁 群算法对带时间窗的物流配送车辆路径问题进行研究。实验表明提高了算法的效率。 2 2 国内外相关研究小结 本文是对带时间窗车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t h t i m ew i n d o w s ，v r p t w ) 的 研究，对常见的求解算法进行了总结。 6 两南人学硕十学伊论文第2 章绪论 2 2 1 国内研究现状 随着人工智能技术的引入和不断发展，模拟退火算法和遗传算法等新方法以及人工神经 网络和专家系统等新技术，为解决人规模、多目标车辆调度问题提供了新的辅助手段。浙江 大学蔡延光等人运用模拟退火算法和遗传算法求解多重车辆调度问趔限1 9 】，并将其集成智能 算法库，作为设计智能运输调度系统的依据。鞍山钢铁学院李大卫等【2 0 】和东北大学姜大立等【2 i 】 分别针对有时间窗和无时间窗约束下的车辆路径问题用基冈编码遗传算法求解。西南交通大 学的郭耀煌教授、李军教授、谢秉磊博士在该领域也做了相当的研究。刘诚【2 2 】等人于2 0 0 5 年 针对遗传算法在求解带时间窗车辆路径问题时初始群体的单一性，提出了一种并行的遗传算 法，该算法有比较理想的效果是因为它对不同的种群采用不同的初始化方法。杨宇栋【2 3 】等2 0 0 6 年通过对客户直接排列的解的表示方法改进了模拟退火算法，也提高了v r p t m 的效率。 对于这类问题，国内现在有很多的混合策略来解决。张丽艳【2 4 】等于2 0 0 6 年利用粒子群算 法和模拟退火算法的混合算法求解了v r p t w 问题。张海刚【2 5 】等于2 0 0 7 年研究了基于改进免 疫遗传算法的带硬时间窗车辆调度问题的实现，并对算法的信息熵计算加以改进，显著提高 了算法的全局收敛的可靠性和收敛速度。吴瑕莉等【2 6 1 人用遗传算法与禁忌搜索算法的混合策 略在v r p t m 问题上的应用。唐忠掣2 7 j 人用免疫禁忌混合算法在电压稳定分析中的应用。 免疫算法比其他的智能优化算法比较晚，在中国也还没有发展多久，但中国科技大学的 王煦法等人对基于遗传操作的人工免疫模型和基于j e m e 网络的人工免疫系统的算法也进行了 较为深入的研究【2 引。焦李成教授系统地提出了免疫进化计算理论框架( 包括免疫算法、免疫 规划、免疫策略、免疫网络等) 并把这些算法都用于了车辆路径问题的研究f 2 9 1 。1 9 9 9 年王煦 法等模拟免疫行为中的抗原识别、抗原记忆和抗体抑止、促进等免疫行为设计出相应的免疫 模块，从而构成免疫遗传算法并应用于t s p 优化。 2 2 2 国外研究现状 国外对车辆路径问题的研究比较早，最早研究带时间窗约束的车辆路径问题是1 9 8 1 年 c h r i s t o f i d e s 在一篇技术报告中对带时间约束的旅行售货员问题( t s p t w ) 的优化算法研究，最 早对带时间窗车辆路径问题的算法研究是1 9 8 6 年s o l o m o n l 3 0 的启发式算法研究。 x u 和k e l l y 提出了基于网络流模型的局域搜索方法【3 l 】。在一个网络流模型中，使用插值 和节点交换，通过使用惩罚机制放松容量约束，容量的参数值可根据时间和搜索过程中的反 馈来调整，因此允许出现不满足车载容量限制的解。引入改进的加强化( i n t e n s i f i c a t i o n ) ；b l 多样 化( d i v e r s i f i c a t i o n ) 操作来克服禁忌搜索算法中的局部优化。加强化表示在邻域内的搜索空间快 速得到最优解多样化表示尽量搜索还未搜索过的空间。 2 0 0 2 年t a r a n t i l i sa n dk i r a n o u d i s 提出了b o n e r o u t e 方法1 3 引。其关键之处在于从一个解集 中提炼出一系列核心的节点，并根据适应性记。| ：l ( a d a p t i v em e m o r y ) 来生成一条路径。如果这个 解集中的许多路径中都包含同一个节点，那么可认为这节点是一个核心节点，并且较好的解 中一定会包含这个核心节点。该算法包含两个阶段第一阶段，使用权重节缬w e i g h t e ds a v i n g s ) 算法产生初始解集，再使用标准的禁忌搜索算法不断改进解集第二阶段，提炼出核心的节点， 7 一 两南人学硕十学伊论文第2 章绪论 使用禁忌搜索产生和改进解，并更新解集。 对于免疫算法的研究源于美国新墨西哥大学s f o r r e s t 和洛斯邓可拉莫斯实验室的 a p e r e l s o n 首先提出的免疫系统遗传建模方法，1 9 9 7 年，c h u n 等基于体细胞理论和免疫网络 理论提出了基本免疫算法。k a z u y u k i 等将免疫优化算法应用于解决自适应调度问题1 33 1 ，抗体 亲和力的计算使用了等位基因和信息熵，同时还使用了传统遗传算法的交叉和变异算子生成 新个体以保持抗体的多样性。 8 若干车辆从配送中心也就是仓库出发，在返回到仓库之前，应该是以最低的总成本( 总路程 或者总时间等) ，并满足在不同地理位置的客户对货物的数量、类型和服务时间的要求。下面 给出一个v r p t w 的一个简单示例，如图3 1 ： 2 ( 1 7 ) 1 0 ， 6 ( 6 ) 3 ，6 9 ，1 1 4 ( 1 1 ) e 5 ，7 图3 1 一个三条路径的v r p t w 求解 在图3 1 中，每辆车的装载能力为3 0 个单位。节点周围的数字有如下解释，例如l ( 1 0 ) 0 ，7 】： 1 表示的是第一个客户，1 0 代表的是客户要求的货物单位，0 表示的是客户允许的最早服务时 间，7 表示的是客户允许的最迟服务时间。边上的数据表示车行驶这段距离的时间。从图中可 以很明显的看出带时间窗车辆路径问题和车辆路径问题之间的不同。如果是车辆路径问题这 个网络就只需要两辆车就可以完成运送，客户点1 、2 和5 由一辆车配送，客户点3 、4 和6 由一辆车配送。而加上了时间窗这个约束条件之后，就需要三辆车才能够完成，图中的6 号 客户要求在时间窗为【3 ，6 】内完成，则及时在第二条路径中的车辆满足装载的情况下也不能够在 第二条路径中。 而带时间窗这个约束条件又可以有不同的分类，根据形式的不同可以分为单边时间窗和 双边时间窗。在图3 1 中采用的就是双边的时间窗，而单边时间窗就是客户不要求车辆的最早 服务时间，只要求在某个时间点之前开始提供服务。本文是基于双边时间窗的研究。 根据车辆的行驶速度可以将带时间窗车辆路径问题分为时变问题( t i m e d e p e n d e n tv e h i c l e r o u t i n gp r o b l e m ，简称t d v r p t w ) 和非时变问题，时变问题主要考虑的是更加真实的情况， 比如由于交通拥挤的情况造成的行驶速度不一致等，目前针对这种问题一般是通过时变函数 来处理行驶的速度。本文是基于非时变时间窗的讨论。 9 两南大学硕十学伊论文第3 章带时问窗车辆路径问题的建模 而根据客户的满意程度又可以分成硬时i 日j 窗( h a r dt i m ew i n d o w s ，简称h t w ) 约束问题 和软时间窗( s o f tt i m ew i n d o w s ，简称s t w ) 约束问题。硬时间窗约束问题是客户要求货物必须 在规定的时间窗内送剑或取走，不能提前也不能拖后；软时间窗约束问题是指允许客户提前 或延后到达，只是如果没有在时间窗内完成则会有一定的惩罚。软时间窗约束的问题更贴近 现实生活，但是由丁：要对惩罚进行建模所以软时间窗问题要比硬时间窗问题复杂很多。在这 里只对硬时间窗问题进行研究。 从对带时间窗车辆路径问题的描述中可以看出：所用车辆的数量也是决策变量，假设所 用的车辆数越少，对应的成本也是越小，如何在不违背车辆装载能力和时间窗的约束条件下， 使用尽量少的车辆是决策者关心的问题之一。基于这个原因，在建立模型的时候就要建立多 目标多层次的目标函数。具体要求的不同，目标函数的层次也是不同的。通常，首先要使服 务所有客户所需车辆数最小化，因为每多增加一辆车意味着多增加一条服务路线和一名司机， 其成本会高很多，而且需要的车辆越多，车辆的购置成本越高。在使用相同数量的车辆情况 下，使行驶的总路程或者行驶的总时间最小化。 3 2 建立数学模型 本文将带时间窗的车辆路径问题描述为：使车辆从仓库出发服务客户，完成客户需求后 返回仓库，并规定每个客户只能被一辆车服务且仅服务一次。且对用户的服务必须在用户事 先指定的时间窗内进行，问题的优化目标是如何选择适当的路径，使得在满足一定的约束条 件下，完成全部需要的总路径最小。 假设用有向图g = 来表示配送网络，净 0 ，1 ，刀) 表示节点集，节点0 表示的 是仓库，n o ) 表示客户的节点，庐 - o , c 搴：l( 4 1 ) i i( 厂( x ) ) 2 这里需要注意的是目标函数的变形必须和原来目标函数的大小顺序保持一致。 ( 3 ) 初始解的获得 在局部搜索算法中计算结果主要依赖的是初始点的选取和邻域的结构，同一个起点，但 是不同的邻域结构会得到不同的计算结果；同样的，同一邻域结构，不同的初始点会得到不 同的计算结果。也就是，初始解的好坏对搜索的性能影响很大。可以用启发式方法或其他方 法找出一个可行解作为初始解。 ( 4 ) 移动与邻域移动 移动是从当前解产生新解的途径，适当的移动规则的设计，是产生高效的搜索算法的关 键。邻域移动就是从当前解进行所有移动构成的邻域。 两南大学硕十学伊论文 第4 章t s 和i a 的算法研究 ( 5 ) 禁忌表 禁忌表是禁忌搜索算法的核心，功能类似丁人类的短期记忆，是用来防i 卜搜索过程中出 现循环，陷入局部最优。可以理解为一个表格，用来记忆最近一段时间邻域解的选择情况， 让这些情况在一定的次数之内禁止再次被访问；过了一定此时之后，这些移动从禁忌表中退 出，就又可以重新被访问。 i 禁忌对象 所谓禁忌对象就是在禁忌表中的元素，禁忌对象可以是最近防问过的点、状态、状态的 变化以及目标值等。 以状态本身和状态的变化作为禁忌对象是最简单、最容易理解的途径。具体而言，如 果将状态s j 变化到状态妇，则状态妇就成为禁忌对象，这样妇就存入了禁忌表中，在没有 被解禁的情况下，妇是不会再出现。采用这种方法使得禁忌的范围比较小，只有当和指定的 完全相同的状态才会被禁忌，搜索空间很大。而存储禁忌对象所占的空间和所用的时间比较 多。 以状态分量或者状态分量的变化作为禁忌对象，对于一些维数很大的问题，每一次移 动可能都有很多状态分量发生变化。如果只取其中一个分量或者少数几个分量作为