论文-禁忌搜索算法

《论文-禁忌搜索算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

4、题在本文中为使得问题易于理解，将该问题描述为：有一定数量的客户，各自有不同数量的货物需求，且每个客户的位置和需求量一定，一个物流中心提供这些货物，并有一个车队负责分送货物，每台配送车辆的载重量一定，这里假设车辆的型号一致，即最大载重量和最远行驶里程数相同，要求合理安排车辆配送路线，使配送总路程最短，同时得满足一定的约束条件，即每条路线总需求量之和不得超过配送车辆的载重量、每条路线行驶的里程数不得超过配送车辆的最远里程数、每一客户需求必须满足且仅由一台车辆配送。1.2禁忌搜索算法描述禁忌搜索算法思想最早由Glover在1986年提出的，是一种全局逐

5、步寻优算法。其求解的过程是先求得一初始解，然后在邻域中搜索较佳解或是移动到较差的区域搜索该区域最佳解，并且记录曾经搜寻的路径，作为下次搜索的依据，以避免陷入局部最优解中。它引入了一个禁忌表记录下已经搜索过的局部最优点，在下一次搜索中利用禁忌表中的信息不再或者有选择地搜索这些点，以此来跳出局部最优点,从而实现全局优化。将禁忌搜索的思想条理化，可描述如下图2.2所示：图2.2禁忌搜索算法框架3车辆路径问题的禁忌搜索算法实现3.1算法思路本文先用插入式启发算法得到车辆路径问题的初始可行解，再利用禁忌搜索算法对初始解进行改造。具体步骤如下：（1）构造初始

6、解时，先用客户直接排列的解的表示方法，随机生成某一不重复的客户排列序列，然后按照车辆路径问题的约束条件，依次将解的元素（客户）划入各条配送路径中，由此产生车辆路径问题的初始解，计算出当前解的目标函数值，这里的目标函数值为各车辆配送路径的里程数总和。（2）通过随机交换两客户位置来生成当前解的邻域解，则有C2n=n*(n-1)/2个客户直接排列序列，然后按照车辆路径问题的约束条件,依次将解的元素（客户）划入各条配送路径中，由此计算出各邻域解的目标函数值。（3）根据藐视准则来评价当前解的邻域解，更新当前解与禁忌表。若候选解的目标值优于当前的最优目标值，

7、不管其禁忌属性如何，更新为当前最优解并更新禁忌表，否则判别该方案的两个客户交换是否被禁忌：若被禁忌，选取次优解后继续该步骤；若未被禁忌，更新该解为当前解并更新禁忌表。（4）若所有的候选对象均被禁忌，则根据队列FIFO原则，对禁忌表中队头元素取消其禁忌属性；禁忌表的更新为将其中所有的禁忌对象的禁忌长度减1，禁忌长度为0的对象取消其禁忌属性。（5）重复迭代指定步长的（2）～（4），输出车辆配送方案的最终结果。3.2程序设计简介算法中，无论是初始解的构造还是邻域内寻优，都涉及到对大量配送点进行的操作，如构造初始解时，针对车辆路径问题的约束条件将客户划分

8、到不同的路径中；更新禁忌表时的将禁忌对象放入表中以及满足藐视准则时的禁忌对象的解禁。程序中针对该问题，采用了队列的形式，通过改进的队列基