旅行商问题

摘要： 近年来,深度学习为求解组合优化问题提供了新的视角。但目前已有的方法在训练时基本都存在收敛速度慢的问题,学习到的策略性能不够高。针对该问题,以经典组合优化问题中的旅行商问题(Travelling salesman problem,TSP)为例,基于Transformer的模型结构,在编码器中屏蔽已访问的城市,解码器在每一步解码时都先对整个输入节点序列重新编码,并且使用新的编码输出得到的聚合嵌入向量和上一步访问的城市对应于编码输出中的节点嵌入向量构造新的上下文向量,结合强化学习的训练方法,提出了一种新的求解旅行商问题的深度学习模型,在随机标准均匀分布数据集上较现有的主流模型有更好的表现。

摘要： 针对物流仓库的拣货-复核路径规划问题,首先利用货格所在行列的奇偶性,根据曼哈顿距离公式,建立了仓库内任意两拣货点(含复核台)之间的距离计算公式。然后将整个拣货-复核作业过程映射为一个旅行商问题,构建了0-1规划模型。最后选用小生境遗传算法进行求解,在变异策略中引入小生境技术,保证了种群的多样性,较好地克服了标准遗传算法中种群早熟和易陷入局部最优的缺点。实验仿真选取1个复核台和有15,30,45,60个拣货点的4种情形,与标准遗传算法相比,该算法求得的最优路径长度可以明显缩短,且收敛速度更快、稳定性更好,尤其拣货点数越多时路径优化效果越明显。

摘要： 虽然遗传算法相较于其他算法能够更好地求解旅行商问题,但这种算法在使用的过程中容易陷入局部最优的问题,进而导致问题求解遭遇困境。文章在简要介绍旅行商问题的基础上,介绍了遗传算法求解旅行商问题的思路和方法,并明确算法应用中存在的不足。在此基础上提出基于指针网络改进遗传算法求解旅行商问题的新思路,为弥补遗传算法的缺陷提供相应的原理支持。

摘要： 麻雀搜索算法(SSA)作为一种新颖的群体智能优化算法,已被证明具有较好的寻优性能。但由于SSA在某些情况下迭代中后期搜索性减小,种群多样性降低,导致算法存在收敛速度慢、求解精度低、易陷入局部最优解等不足。针对SSA存在的缺陷,融合萤火虫算法(FA)迭代策略,提出了一种加入萤火虫搜索扰动的麻雀搜索优化算法(FSSA)。首先,在麻雀搜索后,利用萤火虫扰动策略对种群中所有个体进行位置更新,使得算法在解空间搜索更加充分,有效避免陷入局部最优,进而提升算法的收敛速度以及收敛精度。其次,通过6个基准测试函数对改进算法与粒子群优化算法(PSO)、鲸鱼优化算法(WOA)、原始的SSA算法进行对比,仿真结果表明该算法能够克服SSA易陷入局部最优的不足,在寻优精度、收敛速度以及鲁棒性等方面均获提升。最后,将FSSA应用于具有14座城市的旅行商问题(TSP)求解,仿真实验对比原始的SSA算法,该算法具有更好的结果,进一步验证了FSSA的寻优能力。

摘要： 旅行商问题是一个经典的路径规划问题,传统TSP假设客户位置和客户之间旅行时间是固定不变的,而在现实生活中交通状况和客户要求可能会随着时间而改变,为了找到最经济的路线,可在业务员完成对每个客户的服务后做出实时决策。遗传算法具有全局搜索的性能,成为处理组合优化问题的常用方法。在此运用遗传算法,并借助MATLAB在实例中进行分析验证,结果证明利用遗传算法对求解小规模TSP问题可以得到较好的优化结果。

摘要： 目前战争形式发生变化,装备结构变得复杂,在作战环境多变、维修时间紧迫、维修资源有限等情况下,维修任务的合理分配显得越发重要。因此本文对多中心维修任务分配的研究现状进行了综述,总结现存的任务分配方法,以促进其进一步发展。本文首先对多中心维修任务分配问题进行了描述;然后,对基本概念进行了说明,对问题进行了分析;之后,对优先级排序、任务分配及路径规划常采用的模型与算法等进行了概述;最后,总结了当前研究的不足,并展望了未来发展的方向。

摘要： 随着旅行商问题规模的增长,完全图上最优解的搜索空间呈指数增长。为了减小最优解的搜索空间,提出一种针对旅行商问题的割边算法。推导出四边形最优圈内的最短路径包含一般边与最优哈密顿圈边的不同概率,采用一定数量的四边形最优圈内的最短路径计算边频率,根据所有边的平均边频率割边,基于建立的二项分布模型推导出最优哈密顿圈内边的保留概率。任给一个完全图,割边算法有4个步骤:1)随机选取包含每条边的若干个四边形;2)采用所选四边形最优圈内的最短路径计算各边的边频率;3)步删除5/6条最小边频率的边;4)对度数小于2的节点进行添边操作。计算实验表明:保留边数为完全图上边数量的1/6左右,采用精确算法求解割边后旅行商问题的计算时间也有所减少。

摘要： 针对旅行商问题求解精度较差、容易陷入局部最优等缺点,提出一种新的求解旅行商问题的信息传播算法。根据旅行商问题的特征,将线性方程嵌入信息传播算法方程中得到旅行商问题的势函数,进而将其转换为因子图,在因子图上利用信息传播算法的迭代方程进行迭代计算。在迭代过程中选择边际信念的最小值,从而得到旅行商问题的初始解,在算法达到设定的迭代次数后,引入局部搜索算法进行求解。在若干数据集上的实验结果表明,新算法能够有效求解旅行商问题。

摘要： 针对蚁群算法收敛速度慢,容易陷入局部最优解等问题,提出一种融合动态邻域搜索机制的蚁群系统(DNS-ACS)算法。首先,在蚁群系统算法的基础上,引入2-opt算子进行局部搜索,加快算法收敛速度;然后,动态调整邻域搜索范围和信息素更新规则,使其跳出局部最优,避免早熟现象;最后,利用本文提出的DNS-ACS算法对16个经典TSP算例进行仿真模拟,并与其他算法进行对比实验。实验结果表明,DNS-ACS算法的求解精度明显提高,证明了该算法的有效性。

摘要： 旅行商问题(TSP)是典型的NPC问题,目的是对所有城市遍历一遍求路径最短,旅行商问题易于描述、易于理解,但是求解极其困难。从确定性算法到智能优化算法该问题的求解有了很大的进步。海鸥算法是近年来提出的一种新型智能优化算法,该算法对于求解组合优化问题具有良好的效果,基于海鸥算法的基本原理,采用轮盘赌方法进行初始化,近邻矩阵限制搜索空间范围,利用交叉操作指导算法的搜索顺序,攻击过程中使用概率选择交换、逆序、插入等技术不断对海鸥的路径进行优化,并结合2-opt算子增强算法的局部搜索能力,提出了一种求解TSP问题的改进海鸥算法。最后,对提出的改进算法进行数值实验,将实验结果和近年的改进算法进行对比,实验结果表明,该算法有效且求解质量得到了很好的提高。

摘要： 不确定理论提供了一个新的工具来处理不确定旅行商问题.运用不确定理论的运算法则,给出了旅行商问题的不确定分布.通过运用不确定理论,提出了三种不确定网络下的旅行商问题模型:不确定期望旅行商模型,不确定α-旅行商模型,不确定最大机会旅行商模型.同时研究了不确定期望旅行商模型和不确定α-旅行商模型的求解方法.指出了不确定α-旅行商模型在不确定网络下和相关的确定环境下的旅行商模型存在相等的关系,这使人们找到了一种有效的算法,即Prufer编码遗传算法去求解不确定口-旅行商模型和不确定最大机会旅行商模型.简而言,这个算法可以分解成两部分:构造相应的确定性网络和运用Prufer编码遗传算法求解.

摘要： 旅行商问题(TSP)是组合优化领域中的一个典型的易于描述但难以求解的NP完全问题,具有重要的实际应用价值.在现实生活中,许多因素往往是不确定的,为此,本文主要讨论了不确定环境下的旅行商问题,基于花费的时间服从不确定分布,从旅行者的利益出发建立了带有风险约束的时间最小化模型.最后,通过给出数值例子验证了该模型的有效性.

摘要： 旅行商问题(TSP)作为经典的组合优化问题,广泛应用与各个领域.本文基于禁忌搜索算法在求解该问题时对初始解较强的依赖性,提出了一种改进的禁忌搜索算法,即首先采用最近邻点法产生较好的初始解,再以此为基础进行禁忌搜索,并用该算法求解了TSP的经典案例,经实验对比分析,算法具有良好的性能.

摘要： 从大型水切割机床的调度问题出发,提炼出一类新型的访问域部分重叠的多旅行商问题,建立其0-1数学规划模型,以及提出基于遗传算法的优化求解方法.遗传算法采用改进的城市和商人双染色体编码方案,设计合适的交叉和变异算子.研究结果表明:算法优化效果和收敛性好,适用于求解访问域部分重叠的多旅行商问题.

摘要： 旅行商问题是一类经典的组合优化NP难题.在分析旅行商问题的顺序编码、随机键编码等现有编码方式的基础上,提出了一种新的编码方式,称为压缩的顺序编码.给出了编码算法、解码算法,以及编码的改变对解的影响,并与现有编码方式进行了对比.这种编码方式各基因位之间相互独立,合法性易于维持,不需要合法性修复,这体现出这种编码方式的优越性,并为开发高效的智能优化方法提供了一条新的思路.压缩的顺序编码不仅可以应用于旅行商问题，而且可以应用于车辆路径问题、车间调度问题等旅行商问题的各种扩展与变形，这为以后开发更为高效的智能优化方法提供了一条新的思路。

摘要： 旅行商问题(Traveling Salesman Problem,TSP)是组合优化领域著名的NP问题,具有较为广泛的工程应用和现实生活背景.遗传算法是一种基于自然选择和基因遗传学原理的随机搜索算法,是一种寻求全局最优解而不需要任何初始化信息的高效优化方法.该算法具有全局寻优能力、适应性强、解决非线性问题具有较强的鲁棒性、对问题没有特定限制、计算过程简单、对搜索空间没有特殊要求、易于与其他算法结合等特点,在求解NP完全问题方面是一种较为有效的全局方法.然而遗传算法是一种概率搜索算法,其性能受种群规模、杂交和变异概率等控制参数的影响,而且有时会有收敛到局部最优解的现象.由于算法需要较大的种群规模,种群进化则需要不断的进行适应度函数计算,计算量相当大,因此,本文使用Compute Unified Device Architecture(CUDA)技术在Graphics Processing Unit(GPU)上并行实现遗传算法的所有操作并用于求解TSP旅行商问题.实验证明,该方法相对于串行遗传算法具有更强全局寻优能力以及耗费更少的操作时间.

摘要： 杂草优化算法IWO是一种非常新颖而高效的全局优化算法,该算法模拟杂草克隆、占地生长与繁殖的自然行为,具有鲁棒性、适应性和随机性等特点.本文根据组合优化问题的特点,提出一种离散混合杂草优化算法来解决旅行商问题,通过对算法中正态分布于父代周围的子代进行离散化分析,并引入遗传操作中的单点顺序交叉法和对换变异法,从而有效的防止了算法的早熟收敛,计算机仿真结果表明,离散混合杂草优化算法相对于基本粒子群算法具有很好的性能.

摘要： 针对遗传算法中传统交叉算子交叉效率低下等缺点,提出改进型全干扰量子交叉遗传算法。与基于位置信息的经典量子全干扰交叉模型不同,改进型交叉算子通过距离比较,能够获取质量更高的候选解。通过对旅行商问题(TSP)求解的对比实验表明,改进量子交叉遗传算法能有效平衡全局搜索和局部探索,具有更强的稳定性和寻优能力。

摘要： 本文根据TSP问题在遗传算法问题的特殊表示形式，采用直观且易于操作的边缘重组交叉算子改进遗传算法中进化的步骤，并用比赛选择机制对每代种群进行选择。该算法快速提高了进化速度，并收敛于最优解。通过仿真实验，验证了算法的有效性，并随着问题规模的增加显示出了更大的优越性。

摘要： 本文根据TSP问题在遗传算法问题的特殊表示形式，采用直观且易于操作的边缘重组交叉算子改进遗传算法中进化的步骤，并用比赛选择机制对每代种群进行选择。该算法快速提高了进化速度，并收敛于最优解。通过仿真实验，验证了算法的有效性，并随着问题规模的增加显示出了更大的优越性。

摘要： 本发明涉一种基于改进和声搜索优化蚁群算法旅行商问题求解方法，包括以下步骤：(1)城市十进制编码，和声算法解向量设置，构建目标函数；(2)初始化蚁群参数；(3)初始化蚂蚁位置；(4)选择下一个城市，并进行局部信息素浓度更新；(5)重复执行步骤(4)直到当前蚂蚁访问完所有城市；(6)哨兵策略；(7)重复执行步骤(3)到步骤(6)直到所有蚂蚁完成访问所有城市；(8)记忆库更新、计算记忆库所有和声目标函数值的平均值LA和构建解向量库；(9)采用改进和声算法产生新和声记。

摘要： 本发明公开了一种基于伪旅行商问题的船舶引航排班方法与装置，涉及一种船舶引航排班问题模型与基于伪旅行商问题的求解方法。方法依次包括以下步骤：根据问题描述，确定问题约束条件，建立船舶引航排班数学模型；将船舶引航排班问题数学模型转化为伪旅行商问题模型；采用改进智能水滴算法求解该伪旅行商问题模型，找出最优引航排班计划。本发明针对智能水滴算法启发性不足，容易陷入局部最优等缺点，提出了基于最优候选结点子群的选择策略，提高了搜索效率和算法精度，采用改进智能水滴算法，求解引航员指派模型，有效提高了求解结果的精度。

摘要： 本发明公开了一种运用基于重用策略的智能群体算法优化动态旅行商问题的方法。传统的旅行商问题需要在一个静态的搜索空间中找到一条代价最小的哈密顿回路。但实际上，现实世界中一些可以以旅行商问题为模型的应用并不都是静态的。它们的问题模型中的城市集合和权重矩阵是动态变化的。在动态环境中，上一次环境中搜索结果可以被新环境下的群体重用并得以学习。这样可以缩小问题的搜索空间，从而让算法在更短的时间内搜索到更优的路径。本发明提出了一种更具现实意义的动态旅行商建模方法以及将一种对历史搜索结果重新利用的策略，在实验中，通过设定环境不同程度的改变来测试方法的动态性能，证明了本发明在不同的动态环境下均合理有效。

摘要： 本发明公开了一种解决多目标多旅行商问题的改进蚁群方法，通过改变禁忌表使蚁群每只蚂蚁可以独立构造一个可行解。相比于传统每次随机选择一只蚂蚁移动，多蚂蚁协作构造可行解而言有着效率和均匀度上的优越性。此外，改进蚁群方法添加的策略还包括信息素矩阵随机初始化、修改状态转移公式使蚂蚁在配送点间移动时有一定概率回到仓库中心和额外加入多轮以各个目标优化为导向的信息素更新等。算法步骤如下，对信息素矩阵进行随机初始化后，蚁群将利用改进的状态转移公式结合轮转选择算法逐次挑选下一步配送点直至构造出可行解。可行解加权打分后，以此打分作为信息素添加量的基准，结合子路径的多项特征进行多轮次不同量的信息素添加。

摘要： 本发明公开了一种基于覆盖旅行商问题求解的路径规划方法，属于人工智能的强化学习、深度学习和组合优化领域。所述方法通过利用深度神经网络自动挖掘实例特征的特点提出了新的模型来求解CSP问题，解决了传统方法需要过多的领域知识进行求解的缺点，并极大地提高了求解速度。针对现有深度神经网络求解质量低的问题，采用了数据增强的方式扩充样本数量，利用多起点技术多次求解减少了预测误差，并提出了针对CSP问题的Mask策略对解的构造进行约束。结合简单局部搜索算法进行改进，进一步地提高了求解质量。与现有的DNN求解方法相比显著缩小了最优间隙，与启发式算法相比取得了超过20倍的速度提升，更适合在实时性要求高的场景中使用。

摘要： 本发明公开了一种求解广义旅行商问题的圈生成算法，包括以下步骤：S1、搜索所有服务节点之间的最短路，将GTSP转化为TSP；S2、构建初始费用矩阵；S3、构造指派问题并求解；S4、由指派问题的解获取联接了网路中所有元素的序列集合；S5、由序列生成圈、合成圈；S6、判断是否生成最终回路，如果是，输出结果；否则计算圈之间的费用并构造费用矩阵，返回S3进行构造指派问题生成圈,直到生成一个圈时结束算法。根据本发明，可以在多项式时间内求得一个NP难问题的近似最优解，避免了现有方法计算效率低下的问题。

摘要： 本发明公开一种基于深度强化学习的二次旅行商问题求解方法和系统，方法包括以下步骤：S1：定义二次旅行商问题，即在有向完全图中的某一顶点，访问剩余所有点集一次且仅一次后回到出发点所需的旅行成本；S2：构建求解二次旅行商问题的深度强化学习框架；S3：通过所述深度强化学习框架求解所述二次旅行商问题，得到访问点序列。本发明在极短时间内就能求得二次旅行商问题的近似解，避免了精确解方法求解时间过长，不能实时计算，实时响应，甚至对于问题规模的扩大，并不能得到有效解的问题；同时由于深度强化学习框架模型的拟合能力，避免了启发式算法对迭代计算框架的搭建以及设计者的专业知识的依赖。

摘要： 本发明涉及计算机人工智能技术领域，公开了一种基于改进的鲸鱼优化算法的旅行商问题求解方法，包括：设置算法参数；利用混沌映射初始化种群位置；计算个体适应度并记录当前最优解个体；进入迭代阶段，得到更新的概率p；通过判断概率p和系数向量A，选择一种方式更新鲸鱼位置；进入模拟退火阶段，计算新的种群适应度；依据贪婪规则判断位置是否进行更新，更新则输出全局最优鲸鱼位置和适应度，否则直接以模拟退火概率P接受新种群的位置，然后输出全局最优鲸鱼位置和适应度，选择适应度值最小的作为最优路径。与现有技术相比，本发明精度更高、收敛速度快、鲁棒性强和全局搜索范围广，能够跳出局部最优，具有突出的性能。

摘要： 本发明公开了一种基于BAS改进的粒子群优化算法求解旅行商问题的方法，其步骤为：S1、初始化相关参数，包括城市数量、粒子群数量以及最大迭代次数；S2、初始化城市坐标、每个粒子的位置和速度；S3、通过BAS算法产生随机速度，并根据适应度大小选择速度；S4、更新每个粒子的位置和速度；S5、分别保存个体最优和群体最优；S6、重复步骤S3、S4和S5，当迭代次数达到预设的上限后，停止迭代；S7、停止迭代后，输出当前群体最优对应的位置序列。本发明在传统的粒子群算法中引入了BAS算法，利用BAS算法更新粒子群的速度和位置，可以解决传统粒子群算法容易陷入局部最优的缺点，该方法提高了搜索速度，并且更加稳定，提高了解决旅行商问题的效率。

摘要： 本发明属于计算机人工智能技术领域，公开了一种基于改进鲸鱼优化算法的旅行商问题求解方法及系统，包括：对标准WOA算法的参数进行优化，设计和开发了新的搜索结构以及鲸鱼个体的位置更新方法，提出MnWOA算法；选用高维度非线性复杂目标函数集作为测试对象，对MnWOA进行寻优能力测试;同时，利用经典的旅行商问题测试集验证了MnWOA的实际性能。与现有技术相比，本发明提出的MnWOA算法能够有效地解决旅行商问题，展现出了搜索速度快，计算复杂度低，收敛精度高，全局搜索能力强的特点，并且该算法还具备进一步规避局部最优值的能力，具有很好的参考价值和研究意义。