论文-禁忌搜索算法

《论文-禁忌搜索算法》由会员分享，可在线阅读，更多相关《论文-禁忌搜索算法（6页珍藏版）》请在金锄头文库上搜索。

1、基于禁忌搜索算法的车辆路径选择摘要：本文从VRP的提出背景与求解方法出发，阐释了禁忌搜索算法的原理与影响算法性 能的关键因素，进而将禁忌搜索算法的思想运用于解决车辆路径问题，在VRP问题初始解 的基础上，用禁忌搜索算法优化车辆配送路线，设计出直观且策略易于理解的客户直接排列 的解的表示方法，最后将该算法用C语言实现并用于求解VRP问题，测试结果表明该算法 可行且解的质量较高。关键词：车辆路径问题；禁忌搜索；邻域；禁忌表1. 引言 物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径， 使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行 驶里

2、程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车 辆路径问题正是基于这一需求而产生的。求解车辆路径问题（Vehicle Routing Problem简记 VRP）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间 复杂度呈指数增长，且VRP问题属于NP-hard问题，求解比较困难，因此启发式算法成为 求解VRP问题的主要方法。禁忌搜索算法是启发式算法的一种，为求解VRP提供了新的工 具。本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌 搜索算法。因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车

3、辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。2. 车辆路径问题的禁忌搜索算法2.1 车辆路径问题的描述车辆路径问题的研究目标是对一系列送货点或取货点，确定适当的配送车辆行驶路线， 使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量交发货时间、车辆 容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时 间尽量少、使用车辆尽量少等）。参见下图2.1所示：其中0表示配送中心，18表示客户 编号。图 2.1 车辆路径问题在本文中为使得问题易于理解，将该问题描述为：有一定数量的客户，各自有不同数量 的货物需求，且每个

4、客户的位置和需求量一定，一个物流中心提供这些货物，并有一个车队 负责分送货物，每台配送车辆的载重量一定，这里假设车辆的型号一致，即最大载重量和最 远行驶里程数相同，要求合理安排车辆配送路线，使配送总路程最短，同时得满足一定的约 束条件，即每条路线总需求量之和不得超过配送车辆的载重量、每条路线行驶的里程数不得 超过配送车辆的最远里程数、每一客户需求必须满足且仅由一台车辆配送。禁忌搜索算法描述禁忌搜索算法思想最早由Glover在1986年提出的，是一种全局逐步寻优算法。其求解 的过程是先求得一初始解，然后在邻域中搜索较佳解或是移动到较差的区域搜索该区域最佳 解，并且记录曾经搜寻的路径，作为下次搜索

5、的依据，以避免陷入局部最优解中。它引入了 一个禁忌表记录下已经搜索过的局部最优点，在下一次搜索中利用禁忌表中的信息不再或者 有选择地搜索这些点，以此来跳出局部最优点,从而实现全局优化。将禁忌搜索的思想条理 化，可描述如下图2.2 所示：开始图 2.2 禁忌搜索算法框架3 车辆路径问题的禁忌搜索算法实现3.1 算法思路本文先用插入式启发算法得到车辆路径问题的初始可行解，再利用禁忌搜索算法对初始 解进行改造。具体步骤如下：(1) 构造初始解时，先用客户直接排列的解的表示方法，随机生成某一不重复的客户排列 序列，然后按照车辆路径问题的约束条件，依次将解的元素(客户)划入各条配送路径中 由此产生车辆路

6、径问题的初始解，计算出当前解的目标函数值，这里的目标函数值为各车辆 配送路径的里程数总和。(2) 通过随机交换两客户位置来生成当前解的邻域解，则有C2n=n*(n-1)/2个客户直接排列序列，然后按照车辆路径问题的约束条件,依次将解的元素(客户)划入各条配送路径中， 由此计算出各邻域解的目标函数值。(3) 根据藐视准则来评价当前解的邻域解，更新当前解与禁忌表。若候选解的目标值优于 当前的最优目标值，不管其禁忌属性如何，更新为当前最优解并更新禁忌表，否则判别该方 案的两个客户交换是否被禁忌：若被禁忌，选取次优解后继续该步骤；若未被禁忌，更新该 解为当前解并更新禁忌表。(4) 若所有的候选对象均被

7、禁忌，则根据队列 FIFO 原则，对禁忌表中队头元素取消其禁 忌属性；禁忌表的更新为将其中所有的禁忌对象的禁忌长度减1，禁忌长度为0 的对象取消 其禁忌属性。(5) 重复迭代指定步长的(2)(4),输出车辆配送方案的最终结果。3.2 程序设计简介算法中，无论是初始解的构造还是邻域内寻优，都涉及到对大量配送点进行的操作，如 构造初始解时，针对车辆路径问题的约束条件将客户划分到不同的路径中；更新禁忌表时的 将禁忌对象放入表中以及满足藐视准则时的禁忌对象的解禁。程序中针对该问题，采用了队 列的形式，通过改进的队列基本操作来实现路径的分配与禁忌表的更新问题。下面给出定义int Flag;/设置禁忌对象

8、曲 JQNode,*QueuePtr;typedeF struct定义禁忌表的存储结构QueuePtr front;QueuePtr rear; LinkQueue;typedeF struct QNode定义禁忌对象的存储结构 int的几个结构体：struct CPoint该结构体用于定义坐标点 int x;int y;typedef structLinkQueue;定义每个邻域辭的路径存储方案结构typedeF structint *base;定义当前解的邻域解的目标函数值的存储结构int front;double s用于记录各方案的里程数int rear;bool flag;用于标记该方

9、棄是否可用SqQueue;Jdistance;(1) 客户位置的无重复随机生成以及客户需求量的随机生成 实际配送系统中的客户的地理位置相对独立，且彼此之间服从独立均匀分布，为简易起见，程序中对客户的地理位置分布与客户的需求量只简单地使用C语言中的rand()函数进行 随机分配，其中物流中心的地理位置默认为(0， 0)，为了保证生成的客户位置没有重复， 用 c_locationj.x=c_locationi.x & c_locationj.y=c_locationi.y 语句来判定，其中 c_location 数组采用 CPoint 结构体，用于存储客户的位置， demand 数组用于存储客户需

10、求 量，这两个数组均被定义为全局变量。(2) 客户随机序列的生成 算法中采用客户直接排列的解的表示方式，随机生成初始解，即无重复的客户随机排列序列数组 A。( 3)初始解的车辆路径分配将客户随机序列数组A中的各个值赋值到i_now数组中，i_now数组用于记录当前的最 优解，定义车辆的最大负载量vehicle_Max，这里假设物流中心车辆的型号一致并且不考虑 车辆的最大行驶距离。(4)当前解的邻域结构通过依次交换两客户位置来生成当前解的邻域解，则有C2n=n*(n-l)/2个客户直接排列 序列。i_now的邻域解，用数组exchange_solution记录。用与初始分配方案相似的算法，可 以

11、求出 exchange_solution 数组中每一个车辆分配路线的车辆数以及车辆所行驶的总里程数， 分别记录到数组N_num和s中。（5）寻找当前解邻域结构的评价值最优方案先从数组s中寻找到车辆行驶里程数最短的方案，记其下标为ibest,判断该方案是由当 前解的哪两个客户交换得到的，记作i_x和i_y。根据禁忌准则对该局部最优解进行处理， 可以替换为当前最优解的条件有二：（1）这两个元素的交换是可行的、未被禁忌的；（2）其解 优于当前解，不管其是否禁忌均替换当前最优解，更新禁忌表，将禁忌表中各禁忌对象的禁 忌步长减1，当禁忌步长为 0 时，取消禁忌对象的禁忌属性，而当替换方案中的所有对象均

12、被禁忌后，根据 FIFO 原则，取消队头元素的禁忌属性。4. 算例分析这里用Microsoft Visual C+对车辆路径问题的禁忌搜索算法进行编程，通过对相对独立 的随机分布在（0， 100平方公里范围内的指定客户数、且客户的需求为的（0，指定的客户 数范围内的随机数的 VRP 实例进行求解，进行了实验计算。设在某物流中心有10台配送车辆，车辆的最大载重量均为10单位，在不考虑车辆一次 配送的最大行驶距离的情况下，需要向10 个客户运送货物，作者利用计算机随机产生了范 围在0100内的10个客户的位置坐标（坐标无重复情况）以及客户的货物需求量，其中物 流中心的坐标默认为（0， 0），各个客

13、户的坐标位置与需求量如下图2.3 所示，要求合理安 排配送车辆的行车路径，使配送的总里程数最短。为简便起见，本文设各客户相互之间及物 流中心与客户之间的距离均采用直线距离，该距离可根据客户和物流中心的坐标计算得到，如下图2.4 所示。图 2.4 ?由算法的运行结果可知：初始 731.46，车辆的配送方案为0-4-0、.0- 禁忌搜索算法对初始解进行改进 数为353.96，车辆的分配方案为 所行驶的总里程数得到很大程度3(1现,31)2 (1(73)9/(27； 79)6(2血 31) 7(0t及车辆路径分配所调派的车辆数为7、车辆所行驶的总里程数为 -0、0-6-0、0-9-10-0、0-3-

14、2-5-0、0-1-0，而用 勺最终方案为：车辆数为6、车辆所行驶的总里程 -o、0-4.-00-6-0、0-8-0、0-10-3-2-0、0-5-9-0，车辆I局较优解所花费的时间仅为0.05s。客户编号12345678910横坐标X7101417202023232730纵坐标y2573542513131797928货物需求量22图2.3搜索算法相关信息610635 总结本文基于车辆路径问题的简单描述，采用客户直接排列的解的表示方法，相比较现有研 究成果将车辆路径问题描述为网络图问题的有向边排列方法，表示更加直观、算法策略更加 简单并易于理解，而且算法在迭代过程中产生的解均为可行解，算法的收

15、敛速度得到明显改 善。实验的计算结果表明，用禁忌搜索算法求解车辆路径问题能够跳出局部最优解，实现全 局最优化，所得到的最终解决方案相比较初始方案质量更优，寻优性能良好。参考文献：1 李军，郭耀辉车辆优化调度理论与方法M.北京：中国物资出版社，2001年.2 郎茂祥，胡思继.车辆路径问题的禁忌搜索算法研究J.管理工程学报，2004, 18 (1)： 81-84.3 李松，李瑞彩，刘兴.基于改进禁忌搜索算法的车辆路径优化J.铁道运输与经济， 2008， 30(5)： 91-94.4 张强，荆刚，陈建岭.车辆路线问题研究现状及发展方向J.交通科技，2004, 23 (1)： 60-62.刘云忠，宣慧玉.车辆路径问题的模型及算法研究综述J.管理工程学报，2005，19 (1)： 124-130.