动态搜索算法求解时间依赖型旅行商问题研究

时间依赖型旅行商问题(TDTSP)是旅行商问题(TSP)的延伸.在该问题中,任意两节点间的旅行时间(成本)不仅取决于节点间的距离,还依赖于一天中具体时段或节点在哈密顿圈中所处的具体位置.对基于节点所处哈密顿圈中具体位置的TDTSP问题建立相应的数学模型,并提出求解该问题的动态搜索算法.通过实验仿真,验证了动态搜索算法优于目前在邻域搜索领域求解该问题最有效的动态规划启发式算法.

基于PSO-GA混合算法时间优化的旅行商问题研究

为了给游客提供更好的路径推送服务,针对经典的TSP进行了延伸研究,提出了一种时间优化的旅行商问题(time optimal TSP,TOTSP),旨在寻找一条旅行时间最短的游览路径推送给游客来节省游客的旅行时间。通过混合粒子群遗传算法(PSO-GA)对提出的问题进行仿真实验,并将旅行时间作为PSO-GA的目标函数,其中的旅行时间包括游客在景点之间行走的时间、游客在每个景点排队等待的时间以及游客在每个景点游玩需要的时间三个部分。仿真实验对比了PSO-GA求出的最短旅行时间和所需的CPU执行时间与遗传算法(GA)、蚁群算法(ACO)求出的结果。仿真实验表明,PSO-GA在解决TOTSP上有较好的性能。

有时间约束旅行商问题的启发式遗传算法

有时间约束的旅行商问题作为旅行商问题的拓展 ,是一个重要的NP难题 ,深入研究这一问题具有重要的理论和实践意义。将时间窗约束转化为目标约束 ,采用序列编码设计了基于启发式规则的可同时处理软、硬时间约束的遗传算法——— 2 交换变异的遗传算法和 3 交换变异的遗传算法。实验表明HGA1优于简单遗传算法(SGA) ,HGA2优于HGA1。

基于GA的最小旅行时间的多旅行商问题研究

以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对最小完成时间的多旅行商一类问题研究得相对较少。针对所有旅行商最小完成时间的多旅行商一类问题,用遗传算法进行优化,且提出了矩阵解码方法。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较,适于距离对称和非对称的多旅行商问题求解。

基于SFLA-GA混合算法求解时间最优的旅行商问题

该文以经典的对称旅行商问题(Symmetric Traveling Salesman Problem,STSP)为基础,求解时间最优的旅行商问题(Time Optimal TSP,TOTSP),将拟合函数引入到混合蛙跳遗传算法(SFLA-GA)的适应度函数来反映景点客流量随时间的变化,旨在旅游旺季为游客提供一条游览时间最短的路径推送服务。实验结果表明:相对于随机游览路径,SFLA-GA混合算法得到的游览路径明显节省了游览时间;与SFLA和混合粒子群遗传算法(PSO-GA)相比较,SFLA-GA混合算法具有计算量少、收敛速度快、对初始种群依赖性低以及全局性更好等优点,在求解TOTSP上搜索性能更强、时间更优。

基于HGA的最小旅行时间多旅行商问题研究

为了解决最小化旅行时间的多旅行商一类问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子,操作简单,并且解码方法适于求解距离矩阵对称和距离矩阵非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化最小化完成时间的多旅行商问题。

时间多项式进化算法在旅行商问题中的研究

提出了一种模拟生物遗传的进化算法，并将该算法应用于旅行商问题得到了较好的结果.根据达尔文进化论的优化过程，结合自然选择原则提出了启发式算法，该算法的时间复杂性与快速排序策略相当.在文中利用该算法求解中国旅行商问题得到目前的最佳结果.

带软时间窗的旅行商问题的双种群遗传算法

论文运用双种群遗传算法求解带软时间窗的旅行商问题,通过加入带有时间窗约束条件的惩罚函数,初始化两个种群,分别选择不同的交叉、变异概率。每次迭代后,交换种群间的优势个体所携带的遗传信息,以打破种群内的平衡状态,跳出局部最优解。双种群遗传算法比标准遗传算法显著提高了全局收敛性能。实验结果比较显示,该算法行之有效,具有较好的性能。

曲面上旅行商问题的多项式时间近似方案

欧氏旅行商问题(TSP)的多项式时间近似方案(PTAS)结合了递归剖分、动态规划两种方法.相似的技术已成功用于构造多个欧氏组合优化问题的PTAS.为进一步拓展该方法的适用范围,研究曲面上的TSP.观察到球面不像平面那样可以递归正则剖分,对于可被开半球完全覆盖的小尺度球面TSP,采用的策略为将其逆球心射影到一个球内接正方形上,扰动其顶点并构造剖分网格,接着将该网格射影到球面,然后如同平面TSP的PTAS一样进行动态规划等操作.该策略被拓展到非小尺度球面TSP及更一般的一类曲面TSP.需注意的是由于球面、平面之间射影变形的不规则性,无法将球面TSP直接PTAS归约为平面TSP.

基于蚁群算法的带有时间约束旅行商问题求解

为了实现物流行业的快速、有效配送,可以将问题转化为含时间约束的旅行商问题(TSP)。通过对物流配送环节的研究,构建了一种带有时间约束的TSP模型,并提出一种利用改进的MapReduce蚁群算法求解该模型。利用MapReduce的并行机制,对蚁群算法进行并行处理,使其运行在分布式环境中,增强了求解大规模问题的能力,提高了运行速度。试验证明,在用户预约了送货时间段的情况下,该方法能较好地解决数据运算规模大、算法运算时间长的问题,合理规划物流配送路径。

旅行商问题基于参考点的相邻插入法及其改进

旅行商问题(Traveling Salesman Prblem,TSP)是典型的 NP-hard 问题。通过对已有以最近插入法为代表的构造性算法的分析,提出了一种具有多项式时间性能的基于参考点的相邻插入法及其改进策略,其时间复杂度分别为O(n2)和O(n3),同时基于典型算例的仿真研究验证所提出算法的有效性和高效性。

一种多染色体遗传算法解决多旅行商问题

建立带时间窗口的多旅行商问题模型,设计旅行商数量和旅行时间总和主次两个目标函数,设计一种多染色体编码的编码方式,开发复杂突变算子树进化操作,克服了传统遗传算法搜索空间大的问题。仿真比较了算法的性能,仿真结果表明带复杂突变树的多染色体遗传算法均衡了旅行商数量与旅行时间总和两个目标函数,提高了算法的运行速度,减少旅行时间总和15.8%。

用Memetic算法求解有时间约束的TSP问题

设计了一种基于双重局部搜索策略的Memetic算法用于求解带有时间约束的旅行商问题.在基本遗传操作中,分别采用顺序交叉算子和交换变异算子,同时在每次交叉和变异后均通过随机数来决定是采用贪婪倒位变异算子还是采用递归弧插入算子进行局部搜索优化.实例仿真分析表明该算法快速高效,并且具有很好的鲁棒性.

有路径均衡和时间窗约束的MTSP问题研究

基于最少旅行商数,旅行商间的路径平衡,遍历城市的时间窗等约束条件,建立数学模型,用改进的模拟退火算法,优化多旅行商遍历路径,该算法增加了记忆因子,记住最小的局部最优点,防止程序跳过全局最优点后跳不回来。通过仿真实例验证了该算法的可行性,且符合实时性的要求。

考虑客户满意度的实时取送货路径优化问题

针对即时配送订单出现的动态性、服务客户的满意度、末端配送路网的非对称性,在配送订单的时间窗限制下,建立实时取送货路径优化模型。通过定义并调整非对称网络系数,构建非对称配送网络,提出滚动时域忽略策略(Ignore策略)和滚动时域实时判断策略(Real-time策略)。Ignore策略要求配送员一旦出发,返回配送起点前忽略所有新出现的订单,Real-time策略要求配送途中实时判断当新订单出现时,是否返回起点取货,重新规划配送路线。使用数值仿真软件,在不同非对称系数、客户时间窗、订单数量等的情形下分析策略适用性。数值算例分析表明,Real-time策略适用于网络较大的情形,而网络较小且订单数量较少时,Ignore策略更适用。研究结果可为城市末端合单配送和路径优化策略提供新的思路和参考。

多禁止时间窗约束的路径恢复问题研究

突发灾难的应急物资的配送有时受多禁止时间约束,为此,针对多禁止时间窗约束的应急物资运输路径优化问题,考虑多禁止时间窗的约束,建立了以总配送时间最小为目标、多禁止时间窗约束的应急物资运输路径优化模型。鉴于该模型为混合整数规划模型,采用GUROBI求解,并与建立的对应的多时间窗约束的路径优化模型对比。最后通过算例分析验证了该模型的高效性和算法的有效性。结果表明,多禁止时间窗约束的应急物资运输路径优化模型求解效率更高;此外评估救灾点对配送时间的影响以及分析多禁止时间窗对应急物资配送规划的影响,结果表明部分救灾点显著影响总配送时间,禁止时间窗的开始时间以及宽度影响总配送路线、时间以及到达各救灾点的时间,因此考虑时间约束特点可为应急物资运输决策提供实用价值。

改进遗传算法在含调整时间调度中的应用

在求解含调整时间的工件调度最小化最大完工时间时,由于其内在的复杂性,很难用经典方法求出最优解,只能通过简化手段来求取次优解,因而精度不高。针对这一缺陷,将调度问题转化为经典的旅行商问题,并采用基于优先级的比例选择、实数两点交叉及模式变异算子的改进遗传算法对其求解。仿真实验表明,此方法在满足最小化最大完工时间前提下,既能求解规模更大的调度,又能进一步提高调度完工时间的精度。

基于粘贴系统求解TSP问题

旅行商问题,简称为TSP问题,是困难的NP完全问题,在工程实践中具有广泛的应用。利用常规的计算方法求解这个问题,计算所需的时间是随着问题规模的增大以指数形式增加的,因而无法有效的解决此类问题。DNA计算是一种新兴的计算方式,粘贴系统模型是其中基于粘贴运算的一种DNA计算的抽象模型。通过将旅行商问题转化为求赋权图中权值最小的Hamilton圈,利用粘贴系统模型的巨大并行性,可以有效的求解旅行商问题。

神经网络TSP问题仿真分析

描述了 Hopfield神经网络和自组织特征映射神经网络解决 TSP问题时的求解过程和仿真算法 .通过对两种算法的仿真比较 ,得出以下结论 :对于较大规模的 TSP问题 ,SOFM模型的寻优结果要优于 HNN模型寻优结果 ;HNN对网络模型参数和初始条件具有很强的依赖性且调整参数组合非常困难 ,而 SOFM的参数设置和调整相对要简单得多 ;SOFM算法对待解决问题的拓扑分布不敏感 ,而 HNN算法的收敛性对待求解问题的自身分布有很强的依赖性 ;当待求解问题的数目增大时 ,SOFM算法的运算时间增加缓慢 ,而 HNN算法的运算时间增加较快 .因此 ,在解决 TSP问题时 ,自组织特征映射神经网络比 Hopfield神经网络的效率高 ,随着问题规模的增大 。

基于磁场描述的TSPTW问题模型及其蚁群优化算法

针对带有时间窗限制的旅行商问题(travelling salesman problem with time windows,TSPTW)提出了一种基于磁场模型的蚁群变异算法(MFM-ACOMF).它通过修正传统蚁群算法的启发函数,满足用户的时间需求,并降低算法陷入局部最优的可能性;在得到最终解后,通过变异策略对未达到时间窗标准的顾客节点进行优化.仿真实验结果表明:MFM-ACOMF算法与传统ACOM算法相比,在最优解质量和顾客满意率方面都有一定程度的提高.