多旅行商问题

摘要： 为解决物料配送时拖车的承包区规划问题,生成了降本增效的派送方案和杜绝停线的方案。在转运能力有限,固定存储位置的条件下,提出了合理的假设,模拟实例,对停线原因进行合理分析,在尽量减少停线的前提下,通过多模式优化和动态规划模型,规划物料仓储点最少的储存方案。在此基础上,通过蚁群算法和多旅行商问题模型优化停线问题,按照实际需求和可用拖车,在保证路径最短的同时,利用BFS自动生成成本最低的配送方案。相比于传统的蚁群算法,加入时间窗约束条件,引入软时间惩罚成本,增添了路径信息素不断更新的机制,在贴近实际的同时,杜绝停线现象发生。对最终模型进行验证,表明该方法较好地解决了流水线的配送问题。

摘要： 均衡多旅行商问题(Balanced Multiple Traveling Salesman Problem,BMTSP)被广泛应用在诸如多人协作、任务分担等情形中。针对该问题提出一种改进快速单亲遗传算法(Improved Fast Partheno-Genetic Algorithm,IFPGA)进行求解。首先,基于图论知识完善了BMTSP问题的数学模型;其次,强化和改进了单亲遗传变异策略,将四种常用变异算子“移位、倒序、左移、右移”与随机插入操作相结合,以此大幅增加种群多样性和迭代后期的局部寻优能力;经过精英策略优选后,基于最近邻点策略对种群每一个个体中路程最长的旅行商回路进行局部优化,增强了算法的全局寻优能力。实验结果表明,IFPGA算法设置的策略对算法的性能提升明显,求解算例时IFPGA算法的收敛速度和求解精度得到了很大的提高。

摘要： 多旅行商问题在实际生活中有着较为广泛的应用价值,该问题的求解受到越来越多学者的关注。信息传播算法是一类求解组合优化问题最为有效的方法,基于K-means聚类技术,给出了求解多起点多旅行商问题(multiple depots multiple traveling salesman problem, MMTSP)的信息传播算法,该算法采用K-means聚类算法将旅行商问题进行聚类,从而形成若干不同类,对每一个类采用信息传播算法进行旅行商搜索,将每一个类的搜索结果进行综合,得到MMTSP问题的解。通过对旅行商标准测试数据集中的多种实例进行测试,并与ABC、ACO、PSO、IWO、TWPS、AC-PGA、STASA_2OPT和STASA 8种算法进行试验对比分析。结果表明本文算法最优值小于其他算法和算法稳定的优点。

摘要： 为了满足多旅行商问题最小化总路程及任务均衡的目标,提出了一种簇内元素数量可控的K-means聚类算法,该算法既能将距离相近的元素聚为一类,也能控制簇内元素数量,基于可控K-means聚类算法,构建了任务均衡多旅行商问题求解方法。该方法不仅能通过并行计算提高计算效率,而且可应用于起点各异的多旅行商以及巡检问题求解。

摘要： 立方体表面的多旅行商问题在实际生活中具有较大应用前景。论文提出了一种邻域贪婪的Harris鹰优化算法(NGHHO),该算法在较新的HHO算法基础上通过使用k-mean聚类增强初始解的质量,利用邻域搜索提高算法在TSP问题中的寻优性能,采用贪婪策略提升算法的收敛速度。通过在TSP benchmark测试集和随机点集上与其他经典的群智能算法进行测试比较,实验结果显示NGHHO寻优效果更好,并且显著克服了Harris鹰优化算法的寻优精度低、易陷入到局部最优的缺点,有效地求解了在特殊表面上的MTSP问题,具有较好的实际应用前景。

摘要： 合理有效的巡逻任务规划对于提高街面"见警率"和巡逻力度、加强社会面动态防控工作具有重要意义,由于巡逻任务规划具有多任务、多约束、多目标等特点,极大增加了建立任务分配算法的难度.面向协同巡逻中任务分配和路径优化问题,提出了一种集成的仿真优化框架,采用基于仿真的方法,将进化算法与优化实验相结合进行协同优化.针对巡逻的人机协同以及选址问题,追求任务分配和路径优化综合代价最小建立二层优化模型,结合多智能体遗传算法和OptQuest优化实验构建巡逻方案,设计案例验证模型,同时实现规划结果的GIS可视化.仿真结果验证了模型和算法的有效性,该方法具有较强可扩展性,可解决多巡逻和多地址环境下的多目标优化调度问题.

摘要： 针对混合迭代算法执行时间长的问题,根据粒子群优化(PSO)算法和蚁群优化(ACO)算法的并行特点,结合其在GPU上并行化实现技术和编程优化技巧,提出一种基于CUDA的粒子群聚类蚁群的并行群智能混合方法GPSO-AC.该算法利用GPU的多个流处理器(SM)和单指令多线程(SIMT)的指令架构,将GP SO-A C算法在运行中的独立个体的搜索过程同时并行执行,在保证算法精度的基础上,加快混合迭代法的执行速度.考虑到实际场景中旅行商在每个路段上各项开销不同,可以抽象为每段路程区间上都有一个与之对应的代价,将路程代价考虑到MTSP问题中.采用TSPLIB库中6个测试数据集,将GPSO-AC与PSO-AC、TPHA、K-means-AC等算法进行比较,并进一步探讨了加入代价均衡约束后对加权MTSP问题最优解收敛性能的影响.使用chn31数据集上不同旅行商数时,GPSO-AC在不考虑代价均衡、代价均衡约束、加权代价均衡的情况下的代价标准差分别为1165.26、54.97、6.74.结果表明:在求解一般MTSP问题及其衍生加权、代价均衡MSTP问题上,GPSO-AC在执行速度和收敛精度上均优于CPU串行算法,且随着模型规模增加,其速度优势更加明显.

摘要： 针对钢铁企业的热轧批量计划编制问题,考虑了热轧生产工艺规程、同宽板坯连轧长度限制等约束,建立基于不确定旅行商数的多旅行商问题(MTSP)的热轧批量计划数学模型,把轧制单元计划数最小化和紧邻轧制板坯间轧制宽度、厚度、硬度差异而造成的总惩罚值最小化作为优化目标。结合模型的实际情况,采用基于两交换启发式的改进遗传算法对问题进行求解。最后,利用某钢厂的实际生产数据进行计算试验,同时对结合传统遗传算法和改进遗传算法的优化情况进行对比和结果分析,模型的正确性和算法的有效性得到了验证。

摘要： 车辆与员工的合理调度决定着共享汽车能否高效、有序的运行。针对共享汽车一天内的调度需求,以系统总成本最低及人员总成本最低为目标函数,建立带时间窗口的多旅行商问题双层模型。使用多染色体编码遗传算法,结合复杂突变算子树,对模型进行求解,从而得到满足订单约束的总调度成本最低时所需的车辆数和员工总数以及联合调度路径。

摘要： 研究了无人机协同任务规划中的航线规划与轨迹优化问题,建立了数学模型和求解方案.以攻击方无人机在雷达探测区域的总滞留时间为优化目标,提出了基于多旅行商问题(MTSP)的混合遗传算法.通过该算法产生初始航迹,在考虑到无人机生存率和轨迹合理性基础上进一步做航线平滑和轨迹优化处理,并比较了初始解和最终解.

摘要： 本发明涉一种基于改进和声搜索优化蚁群算法旅行商问题求解方法，包括以下步骤：(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算法能够有效地解决旅行商问题，展现出了搜索速度快，计算复杂度低，收敛精度高，全局搜索能力强的特点，并且该算法还具备进一步规避局部最优值的能力，具有很好的参考价值和研究意义。

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