带多软时间窗VRP及其禁忌搜索算法

分析了带多软时间窗VRP实际应用背景和特点,以使用的车辆数、行驶费用和偏离时间窗的惩罚费用为优化目标,结合车辆载重、最大路长等限制,建立该问题的数学模型,并设计求解该问题的自适应禁忌搜索算法。为增强算法的全局寻优能力,设计了多邻域结构并在算法中嵌入一种有限地接受不可行解的自适应机制。分别用文献中的算例和以Solomon标准算例为基础构建的新算例测试该算法,并将结果与其他方法进行对比分析。对比结果表明,所提出的算法性能较好,能在可接受的时间内求出运输成本更少、满意度更高的解。     

可选时间窗VRP的禁忌搜索算法

车辆调度问题（VRP）是广泛应用于物流配送等领域的一类组合优化问题。对实际中广泛存在的可选时间窗的车辆调度问题（VRPATW）进行了研究,建立了VRPATW问题的数学模型,并利用PFIH算法和禁忌搜索的混合算法进行求解,最后通过实验说明此算法解决VRPATW问题的有效性和可行性。     

基于Sweep和主动禁忌的多时窗VRPPD设计

针对多时窗装卸车辆路线问题(vehicle routing problem with pickups and deliveries,VRPPD),提出了一种基于Sweep算法和主动禁忌算法的多时窗VRPPD问题求解方法.定义了多时窗VRPPD问题的数学模型;通过改进的Sweep算法获取初始解,设计了候选解结构、适应度函数、4种邻域操作以及邻城操作需满足的车辆容量约束和时间窗约束方程,采用主动禁忌算法自适应地修改禁忌长度以增强算法的全局寻优能力;定义了具体的多时窗VRPPD求解算法.实验结果表明,该方法能有效地解决多时间窗VRPPD问题;与其它方法相比,该方法具有全局搜索能力强和收敛速度快的优点.     

模糊时间窗VRP的动态规划和禁忌搜索混合算法

为优化具有模糊时间窗的车辆路径问题,以物流配送成本和顾客平均满意度为目标,建立了多目标数学规划模型。基于Pareto占优的理论给出了求解多目标优化问题的并行多目标禁忌搜索算法,算法中嵌入同时优化顾客满意度的动态规划方法,运用阶段划分,把原问题分解为关于紧路径的优化子问题。对模糊时间窗为线性分段函数形式和非线性凹函数形式的隶属度函数,分别提出了次梯度有限迭代算法和次梯度中值迭代算法来优化顾客的最优开始服务时间。通过Solomon的标准算例,与次梯度投影算法的比较验证了动态规划方法优化服务水平的有效性,与主流的NSGA-II算法的对比实验表明了该研究提出的多目标禁忌搜索算法的优越性。     

求解多目标带时间窗VRP问题的文化狼群算法

针对以最小化总距离和车辆数为目标的带时间窗车辆路径问题的求解,提出一种基于文化基因的狼群算法。根据客户近邻度矩阵构建初始狼群,提高狼群的优良性。结合问题特征与狼群算法的寻优思想,重新定义了群体的游走和突袭行为。提出头狼变异策略,增加了最优解的邻域搜索范围。受文化算法启发,将当前最优解的有利信息作为信仰空间的知识来指导狼群进化方向,提高搜索效率。仿真实验及与其他算法对比,表明文化狼群算法求解车辆数更少、总距离更短,且具有更好的稳定性。     

带时间窗车辆路径问题的差分进化混合算法

研究了带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),建立了数学模型,并设计了求解VRPTW的离散差分进化混合算法。算法采用随机车辆配载方法构造初始解,并通过构造新的变异和交叉算子进行改进。进一步,利用插入可行邻域和2-Opt可行邻域两种搜索可行解的邻域结构,引入禁忌搜索进一步进行局部搜索以提高算法的寻优能力。实验结果表明该算法是求解VRPTW的一种有效方法。     

基于Memetic算法的带时间窗车辆路径问题研究*

提出一种模拟文化进化的Memetic算法求解带时间窗的车辆路径问题。设计了一种实数编码方案,将离散的问题转为连续优化问题。采用邻域搜索帮助具备一定学习能力的个体提高寻优速度;采用禁忌搜索帮助部分个体跳出局部最优点,增强全局寻优性能。实验结果表明,该算法可以更有效地求出优化解,是带时间窗车辆路径问题的一种有效求解算法。     

求解带硬时间窗车辆路径问题的自适应蚁群算法

蚁群算法具有较强的鲁棒性和优良的分布式计算机制.研究重点是对现有的求解带硬时间窗的车辆路径问题VRP-H(Vehicle Routing Problem with Hard Time Windows)的蚁群算法作出更好的改进,使得算法的计算效率更高且得到的解更优,提出了蚁群算法的改进算法-改进的自适应蚁群算法.该算法先用自适应蚁群算法对VRP-H求得一个可行解,再利用多种改善方法对初始解进一步优化,从而得到最优解.测试时选用Solomon提出的题库,结果表明该算法能够有效地求解VRP-H.     

基于改进遗传算法的带时间窗VRP问题研究

带时间窗约束的VRP问题(VRPTW)属于NP-hard问题,采用改进遗传算法探索最优方案。首先分析了带时间窗VRP问题的一般数学模型,并采用罚函数的方法对时间窗约束进行处理;设计了带权重的适应度函数,并采用了基于基因库的跨世代精英选择算子、PMX交叉算子和局部爬山变异算子;最后通过仿真实验与传统遗传算法和自适应遗传算法进行了对比研究,仿真结果表明改进遗传算法在解决带时间窗VRP问题中具有较高收敛速度和全局搜索能力。     

带时间窗车辆路径问题的多目标文化基因算法

针对物流配送中带时间窗的车辆路径问题,以最小化车辆使用数和行驶距离为目标,建立了多目标数学模型,提出了一种求解该问题的多目标文化基因算法。种群搜索采用遗传算法的进化模式和Pareto排序的选择方式,局部搜索采用禁忌搜索机制和存储池的结构,协调两者得到的Pareto非占优解的关系。与不带局部搜索的多目标遗传算法和单目标文化基因算法的对比实验表明,本文算法的求解质量较高。     

遗传算法求解VRP问题

在分析了许多求解固定车辆路径问题的优化算法后,提出了一种新的求解固定车辆路径问题的遗传算法。该算法的核心在于构建一种新的染色体编码,并且将“Inver-0ver”遗传操作算子与禁忌搜索算法结合起来,利用种群的信息引导种群的进化。引入动态非法检测来淘汰不合法个体,扩展了解空间并加快了搜索速度。经过大量的实例测试,该遗传算法增强了群体演化的质量,提高了算法收敛速度,能够找到比较好的近似最优解。     

混合算法求解VRP问题

车辆路径问题（VRP）是典型的复杂组合优化问题,也是一个求解非常困难的NP难问题。对于大规模的VRP问题,一般采用近似算法来进行求解。通过采用一种基于遗传算法和禁忌搜索算法的混合算法,结合两者的优点,既克服了遗传算法爬山能力差的缺点,又克服了禁忌搜索算法的对初值的依赖性,使得算法能够更快更准的收敛到最优解。     

An Algorithm Based on Tabu Search for Satisfiability Problem

In this paper,a computationally effective algorithm based on tabu search for solving the satisfiability problem(TSSAT)is proposed.Some novel and efficient heuristic strategies for generating candidate neighborhood of the curred assignment and selecting varibables to be flipped are presented. Especially,the aspiration criterion and tabu list tructure of TSSAT are different from those of traditional tabu search.Computational experiments on a class of problem insteances show that,TSSAT,in a reasonable amount of computer time ,yields better results than Novelty which is currently among the fastest known.Therefore TSSAT is feasible and effective.     

基于双禁忌对象的并行禁忌搜索算法

禁忌搜索算法是解决组合优化问题的一种主要方法,是克服NP完全问题的一个有效途径。随着计算网格的发展,将禁忌搜索算法引入到这种分布式并行计算环境中,具有广泛的应用价值。提出了一个基于双禁忌对象的禁忌搜索算法,在此算法的基础上,利用并行化分散搜索策略来提高算法的求解精度。实验结果表明该并行禁忌搜索算法性能较高。     

基于遗传算法和禁忌搜索的混合优化策略

将禁忌搜索和遗传算法相结合,给出了一种求解优化问题的混合策略--禁忌遗传优化算法.该算法一方面为禁忌搜索找到了较好的初始点,减少了调用禁忌搜索的次数,另一方面也可以克服遗传算法爬山能力差的缺点,从而加快了收敛速度,提高了解的质量.通过实例验证了该优化算法的有效性和可靠性,并将其用于网络拥塞控制的研究中,为进一步实施网络拥塞控制提供了一种有效的途径.     

A tabu search heuristic for the single vehicle pickup and delivery problem with time windows

The single vehicle pickup and delivery problem with time windows is a generalization of the traveling salesman problem. In such a problem, a number of transportation requests have to be satisfied by one vehicle, each request having constraints to respect: a pickup at its origin and a delivery at its destination, and a time window at each location. The capacity of the vehicle has to be respected. The aim is to minimize the total distance traveled by the vehicle. A number of exact and approximate solution methods exists in the literature, but to the authors knowledge none of them make use of metaheuristics, still promising with other vehicle routing problems. In this paper we present tabu search and probabilistic tabu search. Results obtained on classical traveling salesman problems and a class of randomly generated instances indicate that our approach often produces optimal solutions in a relatively short execution time.