基于禁忌搜索算法的车辆路径选择摘要：本文从VRP的提出背景与求解方法出发，阐释了禁忌搜索算法的原理与影响算法性能的关键因素，进而将禁忌搜索算法的思想运用于解决车辆路径问题，在VRP问题初始解的基础上，用禁忌搜索算法优化车辆配送路线，设计出直观且策略易于理解的客户直接排列的解的表示方法，最后将该算法用C语言实现并用于求解VRP问题，测试结果表明该算法可行且解的质量较高。
关键词：车辆路径问题；禁忌搜索；邻域；禁忌表1.引言物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。
求解车辆路径问题（Vehicle Routing Problem简记VRP）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且VRP问题属于NP-hard问题，求解比较困难，因此启发式算法成为求解VRP问题的主要方法。
禁忌搜索算法是启发式算法的一种，为求解VRP提供了新的工具。
本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。
因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。
2.车辆路径问题的禁忌搜索算法2.1 车辆路径问题的描述车辆路径问题的研究目标是对一系列送货点或取货点，确定适当的配送车辆行驶路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。
参见下图2.1所示：其中0表示配送中心，1～８表示客户编号。
图2.1 车辆路径问题在本文中为使得问题易于理解，将该问题描述为：有一定数量的客户，各自有不同数量的货物需求，且每个客户的位置和需求量一定，一个物流中心提供这些货物，并有一个车队负责分送货物，每台配送车辆的载重量一定，这里假设车辆的型号一致，即最大载重量和最远行驶里程数相同，要求合理安排车辆配送路线，使配送总路程最短，同时得满足一定的约束条件，即每条路线总需求量之和不得超过配送车辆的载重量、每条路线行驶的里程数不得超过配送车辆的最远里程数、每一客户需求必须满足且仅由一台车辆配送。
禁忌搜索算法描述禁忌搜索算法思想最早由Glover在1986年提出的，是一种全局逐步寻优算法。
其求解的过程是先求得一初始解，然后在邻域中搜索较佳解或是移动到较差的区域搜索该区域最佳解，并且记录曾经搜寻的路径，作为下次搜索的依据，以避免陷入局部最优解中。
它引入了一个禁忌表记录下已经搜索过的局部最优点，在下一次搜索中利用禁忌表中的信息不再或者有选择地搜索这些点，以此来跳出局部最优点,从而实现全局优化。
将禁忌搜索的思想条理化，可描述如下图2.2所示：图2.2 禁忌搜索算法框架3车辆路径问题的禁忌搜索算法实现3.1算法思路本文先用插入式启发算法得到车辆路径问题的初始可行解，再利用禁忌搜索算法对初始解进行改造。
具体步骤如下：（1）构造初始解时，先用客户直接排列的解的表示方法，随机生成某一不重复的客户排列序列，然后按照车辆路径问题的约束条件，依次将解的元素（客户）划入各条配送路径中，由此产生车辆路径问题的初始解，计算出当前解的目标函数值，这里的目标函数值为各车辆配送路径的里程数总和。
（2）通过随机交换两客户位置来生成当前解的邻域解，则有C2n=n*(n-1)/2个客户直接排列序列，然后按照车辆路径问题的约束条件,依次将解的元素（客户）划入各条配送路径中，由此计算出各邻域解的目标函数值。
（3）根据藐视准则来评价当前解的邻域解，更新当前解与禁忌表。
若候选解的目标值优于当前的最优目标值，不管其禁忌属性如何，更新为当前最优解并更新禁忌表，否则判别该方案的两个客户交换是否被禁忌：若被禁忌，选取次优解后继续该步骤；若未被禁忌，更新该解为当前解并更新禁忌表。
（4）若所有的候选对象均被禁忌，则根据队列FIFO原则，对禁忌表中队头元素取消其禁忌属性；禁忌表的更新为将其中所有的禁忌对象的禁忌长度减1，禁忌长度为0的对象取消其禁忌属性。
（5）重复迭代指定步长的（2）～（4），输出车辆配送方案的最终结果。
3.2 程序设计简介算法中，无论是初始解的构造还是邻域内寻优，都涉及到对大量配送点进行的操作，如构造初始解时，针对车辆路径问题的约束条件将客户划分到不同的路径中；更新禁忌表时的将禁忌对象放入表中以及满足藐视准则时的禁忌对象的解禁。
程序中针对该问题，采用了队列的形式，通过改进的队列基本操作来实现路径的分配与禁忌表的更新问题。
下面给出定义的几个结构体：（1）客户位置的无重复随机生成以及客户需求量的随机生成实际配送系统中的客户的地理位置相对独立，且彼此之间服从独立均匀分布，为简易起见，程序中对客户的地理位置分布与客户的需求量只简单地使用C语言中的rand()函数进行随机分配，其中物流中心的地理位置默认为（0，0），为了保证生成的客户位置没有重复，用c_location[j].x==c_location[i].x && c_location[j].y==c_location[i].y语句来判定，其中c_location数组采用CPoint结构体，用于存储客户的位置，demand数组用于存储客户需求量，这两个数组均被定义为全局变量。
（2）客户随机序列的生成算法中采用客户直接排列的解的表示方式，随机生成初始解，即无重复的客户随机排列序列数组A。
（3）初始解的车辆路径分配将客户随机序列数组A中的各个值赋值到i_now数组中，i_now数组用于记录当前的最优解，定义车辆的最大负载量vehicle_Max，这里假设物流中心车辆的型号一致并且不考虑车辆的最大行驶距离。
（4）当前解的邻域结构通过依次交换两客户位置来生成当前解的邻域解，则有C2n=n*(n-1)/2个客户直接排列序列。
i_now的邻域解，用数组exchange_solution记录。
用与初始分配方案相似的算法，可以求出exchange_solution数组中每一个车辆分配路线的车辆数以及车辆所行驶的总里程数，分别记录到数组N_num和s中。
（5）寻找当前解邻域结构的评价值最优方案先从数组s中寻找到车辆行驶里程数最短的方案，记其下标为ibest，判断该方案是由当前解的哪两个客户交换得到的，记作i_x和i_y。
根据禁忌准则对该局部最优解进行处理，可以替换为当前最优解的条件有二：(1)这两个元素的交换是可行的、未被禁忌的；(2)其解优于当前解，不管其是否禁忌均替换当前最优解，更新禁忌表，将禁忌表中各禁忌对象的禁忌步长减1，当禁忌步长为0时，取消禁忌对象的禁忌属性，而当替换方案中的所有对象均被禁忌后，根据FIFO原则，取消队头元素的禁忌属性。
4. 算例分析这里用Microsoft Visual C++对车辆路径问题的禁忌搜索算法进行编程，通过对相对独立的随机分布在（0，100]平方公里范围内的指定客户数、且客户的需求为的（0，指定的客户数]范围内的随机数的VRP实例进行求解，进行了实验计算。
设在某物流中心有10台配送车辆，车辆的最大载重量均为10单位，在不考虑车辆一次配送的最大行驶距离的情况下，需要向10个客户运送货物，作者利用计算机随机产生了范围在0～100内的10个客户的位置坐标（坐标无重复情况）以及客户的货物需求量，其中物流中心的坐标默认为（0，0），各个客户的坐标位置与需求量如下图2.3所示，要求合理安排配送车辆的行车路径，使配送的总里程数最短。
为简便起见，本文设各客户相互之间及物流中心与客户之间的距离均采用直线距离，该距离可根据客户和物流中心的坐标计算得到，如下图2.4所示。
图2.3 禁忌搜索算法相关信息图2.4 客户地理位置分布情况及车辆路径分配由算法的运行结果可知：初始解方案中所调派的车辆数为7、车辆所行驶的总里程数为731.46，车辆的配送方案为0-4-0、0-7-0、0-8-0、0-6-0、0-9-10-0、0-3-2-5-0、0-1-0，而用禁忌搜索算法对初始解进行改进后所得到的最终方案为：车辆数为6、车辆所行驶的总里程数为353.96，车辆的分配方案为0-1-7-0、0-4-0、0-6-0、0-8-0、0-10-3-2-0、0-5-9-0，车辆所行驶的总里程数得到很大程度的改善，且得到全局较优解所花费的时间仅为0.05s。
5总结本文基于车辆路径问题的简单描述，采用客户直接排列的解的表示方法，相比较现有研究成果将车辆路径问题描述为网络图问题的有向边排列方法，表示更加直观、算法策略更加简单并易于理解，而且算法在迭代过程中产生的解均为可行解，算法的收敛速度得到明显改善。
实验的计算结果表明，用禁忌搜索算法求解车辆路径问题能够跳出局部最优解，实现全局最优化，所得到的最终解决方案相比较初始方案质量更优，寻优性能良好。
参考文献：[1]李军，郭耀辉．车辆优化调度理论与方法[M]．北京：中国物资出版社，2001年．[2]郎茂祥，胡思继．车辆路径问题的禁忌搜索算法研究[J]．管理工程学报，2004，18（1）：81-84．[3]李松，李瑞彩，刘兴．基于改进禁忌搜索算法的车辆路径优化[J]．铁道运输与经济，2008，30（5）：91-94．[4]张强，荆刚，陈建岭．车辆路线问题研究现状及发展方向[J]．交通科技，2004，23（1）：60-62．[5]刘云忠，宣慧玉．车辆路径问题的模型及算法研究综述[J]．管理工程学报，2005，19（1）：124-130．。