带冲突图的着色旅行商问题模型与算法

着色旅行商问题是多旅行商问题的一个重要变种,它被广泛地应用于带有重叠区域的多机工程系统。现有的着色旅行商问题难以有效应对带冲突的场景,这种冲突通常表现为两个城市不允许被同一旅行商访问。受带冲突图的组合优化问题的启发,提出了带冲突图的着色旅行商问题,且给出了其形式化的表达。带冲突图的着色旅行商问题是一个NP难问题,精确算法求解器CPLEX仅能在小规模问题实例上获得问题的最优解。为了求解更大规模的实例,提出了一个有效的模因算法。该模因算法采用了自适应大规模邻域搜索算子。对比模因算法和精确算法,模因算法在20个小规模实例中的9个结果更好,在18个实例上展现了其远超精确算法的求解速度。而比较模因算法和其他启发式算法,模因算法在全部14个中等规模实例上均取得了更好结果。此外,消融实验结果验证了模因算法中自适应大规模领域搜索算子的有效性。

基于图卷积和注意力神经网络的旅行商问题新解法

旅行商问题是一个经典的组合优化问题。为快速求解旅行商问题,设计了由图嵌入网络、图卷积神经网络、注意力神经网络和多层感知机组合而成的深度学习模型的学习分支规则,通过改进传统的分支定界算法提高算法性能。对15个城市的旅行商问题实例进行监督训练,并在SCIP求解器上分别测试10,15,20,25和30个城市的旅行商问题实例。发现:基于学习分支规则的分支定界算法的求解时间比基于传统分支规则的分支定界算法的求解时间分别快-0.0022 s,0.0178 s,1.7643 s,2.3074 s和2.0538 s。因此,基于图神经网络的分支变量选择对传统分支规则的改进是有效的,可以较好地泛化到训练规模更大的旅行商问题实例中。

利用改进匈牙利算法求解旅行商问题

针对传统的匈牙利算法在求解旅行商问题(travelling salesman problem,TSP)时会导致多回路闭合的问题,提出了破环机制,设计了破环匈牙利算法。通过采用分配问题的描述方法对旅行商问题进行建模,并建立二者之间的转换关系,论证了TSP可行解的充分必要条件是对应分配问题的可行解与辅助边结合后仅包含一个环路,对6个标准旅行商进行测试和对比分析,验证算法的有效性。实验结果表明:在不同的数据集中,改进匈牙利算法能有效求出TSP问题的解。

双渠道下基于在线旅行商拍卖销售的酒店定价决策

在酒店与在线旅行商(OTA)组成的旅游供应链系统中,考虑OTA对客房采用拍卖销售的情况下,构建了酒店与OTA的集中式决策和以酒店为主导、OTA为追随者的分散式决策,并采用逆向归纳法给出了酒店与OTA的最优定价决策.研究结果表明,OTA的拍卖数量会随着销售价格和佣金的增加而增加;最优佣金与最优拍卖数量会随着OTA平台用户基础数量和拍卖时长的增加而增加;相比分散式决策,集中式决策下旅游供应链系统有更多的客房拍卖数量和更高的销售单价.基于此,酒店与OTA应以利益共同体的理念开展合作,实现整体利益最大化,促进双方高质量发展.

一种应用于旅行商问题的莱维飞行转移规则蚁群优化算法

针对旅行商问题(TSP)提出了一种基于莱维飞行转移规则的蚁群优化算法。该算法结合了基于莱维飞行和蚁群系统算法(ant colony system,ACS)的转移规则,形成了一种动态权重的混合转移规则,该策略能够有效地帮助算法跳出局部最优,增强全局搜索能力。此外,随机多路径优化3-opt策略通过随机抽取部分路径与当前最优路径组合,增加算法的多样性。当算法陷入停滞时,采用信息素平均随机重置策略重置路径上的信息素浓度,有助于算法跳出局部最优。实验结果显示,所提算法在处理多个不同规模的TSP实例时,与最优解的误差保持在3%以内,证明了该算法在TSP中具备出色的收敛性和避免陷入局部最优解的能力。

基于量子近似优化算法的旅行商问题研究

用量子近似优化方法对旅行商问题的一个变种进行算法设计和实现,并在模拟器上进行了仿真。结果表明,在量子比特足够的情况下,该算法能在量子计算机上以多项式时间进行旅行商问题变种的求解,并达到近似比1.5之内的近似程度,为利用量子计算机求解NP难问题提供了一种思路。

旅行商问题的综述教学研究

旅行商问题是数学上的组合优化问题,是一个经典的NP完全问题。该问题在工程上有很强的实用背景;对该问题的研究一直受到众多学者的重视,对其的求解亦提出了各种不同算法;同时就该问题还提出了各种推广形式,但就该问题的教学研究却很少有人涉及。针对这些情况,本文就该问题的综述与教学做几方面的研究,以提高对该问题的教学质量、增强学生的学习积极性。

基于优化旅行商算法的旅游自驾路径设计

随着自驾旅游的日益普及,如何设计出既满足游客需求又尽可能减少行驶距离的旅游路线变得尤为重要。文章将旅行商算法作为规划路径的基本算法,为需要规划的自驾路径添加了约束条件与限界函数,对基本算法进行了优化。

求旅行商问题的幂律变换优化蚁群算法

为解决旅行商问题,依据蚁群系统在蚁群算法中的优化,提出一种基于幂律变换的优化蚁群算法。首先,利用幂律变换优化蚁群算法以改善信息素局部更新公式;然后,在状态转移中使用幂律变换种群走过每条路径的次数,并通过归一化处理来分析信息素局部更新所造成的影响,以加快模型收敛速度;最后,随机加入莱维飞行对全局信息素进行扰乱,防止模型过早陷入局部最优。经过TSPLAB数据库提供的大量实例验证,幂律变换优化蚁群算法在保持较快收敛速度的基础上,能有效避免模型过早陷入局部最优。

基于量子蚁群算法的旅行商问题求解及算法评估

量子蚁群算法是一种将量子理论与传统蚁群算法结合的高效生物进化算法,主要应用于故障诊断、路径规划、图像分割等问题的优化.基于传统蚁群算法的流程,介绍量子蚁群算法中的量子理论基础以及量子理论如何应用于蚁群算法.通过若干旅行商问题实例分析量子蚁群算法较传统蚁群算法的优势.针对目前研究多以离散指标来评估不同算法、难以直观显示不同算法综合差别的问题,提出一种综合评估算法搜索效率的方法,成功应用于量子蚁群算法和传统蚁群算法的对比,具有一定的实践意义.

基于带容量约束的着色旅行商问题的多机器人调度

电商仓储的高速发展对多拣选机器人的任务调度分配问题提出了更高的要求,着色旅行商问题在城市任务上的定性描述已经逐渐无法满足实际问题中的定量分析的需求。为了降低综合成本,提高拣选效率,拟在着色旅行商问题的基础上结合有容量限制的车辆路径问题,提出一种带容量约束的着色旅行商问题,来更好地构建以总路径成本最小为目标的多拣选机器人的调度模型,并设计相应的变邻域搜索算法对模型进行求解。实验结果表明,相较于基于遗传算法及其改进算法,变邻域搜索算法在求解带容量约束的着色旅行商问题上更具优越性,该模型及其求解算法具有一定实用价值。

基于改进的指针网络深度强化学习算法求解旅行商问题

旅行商问题是组合优化问题中的经典问题,而深度强化学习的发展为该类问题的求解提供了新思路。在基于指针网络的深度强化学习算法求解旅行商问题中,策略网络和价值网络的编码器都采用了复杂的长短期记忆网络结构,这在求解大规模旅行商问题时会造成训练时间过长的现象。鉴于输入节点间位置顺序的无关性,本文对指针网络中编码器的循环神经网络进行了修改,将策略网络和价值网络编码器中的长短期记忆网络都替换为一维卷积神经网络,最终提出了一种改进的基于指针网络的深度强化学习算法,其在相同求解问题规模上所需要的训练时间比原模型减少12%~15%,实验结果充分验证了本文改进算法的有效性。

面向多起点均衡多旅行商问题的进化算法

为解决多起点均衡多旅行商问题,分析问题的特点,从优化旅行商的起点、最小化所有旅行商总路程和维持各旅行商路径均衡的角度出发,提出一种基于改进交叉、变异操作的遗传算法。根据均衡多旅行商问题的优化目标,构建新型评价函数,设计双染色体编码方式。在此基础上,引入改进的三交换启发式交叉操作并设计双变异策略。在经典旅行商问题的测试集TSPLIB上,与其它求解多旅行商问题的进化算法进行对比,验证算法的有效性。

酒店与在线旅行商的冲突是什么?——一个归纳式质性研究

在线旅行商(online travel agency,OTA)已经成为酒店业最重要的分销渠道,且与酒店产生广泛的冲突。然而,这种冲突本身并未得到学术界的足够关注。通过归纳式质性研究设计,文章对酒店与OTA冲突的领域及特征进行了探索。研究发现,酒店与OTA的冲突主要发生在价格、房源、客源及渠道限制等4个直接关系到双方利益得失的领域;OTA拥有的信息优势和权力不对称带来的在线显示度、动态性问题以及行业差异带来的沟通问题是酒店与OTA冲突的主要特征。基于上述发现,文章提出了一个概念性分析框架。这一框架整合了前人关于酒店与OTA冲突领域及特征的研究发现,提出了在线显示度、动态性等新构念,揭示了不对称权力和信息优势对冲突的影响,并指出应放弃分销渠道与酒店在信息、权力等方面保持不变的隐含假定。上述发现有利于学术界和业界加深对酒店与OTA渠道冲突乃至对双方关系的理解和认识,从而将动态视角引入研究、管理和规制工作中。

基于改进的乌鸦搜索算法求解旅行商问题

旅行商问题(TSP)是一个典型的NP难问题,广泛应用于工程应用中,作为一种新的群体智能优化算法,采用乌鸦搜索算法(CSA)来解决TSP问题,具有易于理解和简单实现的优点。但是,乌鸦算法也存在一些问题:算法收敛速度慢、易于陷入局部最优、优化精度不够等问题。为了有效解决TSP问题,文章提出了一种改进的乌鸦优化算法,以提高算法的收敛性,同时对TSPLIB中10个标准数据集进行分析,结果表明,改进的乌鸦优化算法在收敛速度和精度方面表现优于其他解决方案。

求解旅行商问题的探索—开发—跳跃策略单亲遗传算法

针对遗传算法求解旅行商问题(TSP)时容易早熟、收敛速度慢等问题,提出一种基于探索—开发—跳跃策略的单亲遗传算法(EDJS-PGA)。该算法将基因移位、倒序、交换三种算子组合构成探索策略,用于扩展解的搜索空间,增强算法全局搜索能力;再将logistic混沌映射和改良圈操作融合为一种混沌映射改良圈算子,用于增强算法的局部搜索能力,构成开发策略;最后针对种群中的同优个体设计了近邻变异算子,构成跳跃策略,增强了算法跳出局部最优解的能力,使其兼具个体变异、局部优化、防止早熟等多重作用。通过对18个TSP实例进行仿真实验,结果表明EDJS-PGA相较于传统单亲遗传算法具有更高的求解精度和收敛速度,且最优解偏差率和平均误差率均处于较低水平;与其他文献对比,EDJS-PGA具有更强的鲁棒性和求解效率。

基于混合人工蜂群算法和A^(*)算法的求解旅行商问题算法

针对旅行商问题(travel salesman problem,TSP),基于群智能优化算法的人工蜂群算法(artificial bee colony,ABC)可以较为有效地解决并规划出一条合理的路线。ABC算法的优点在于将优化求解的过程转化为模仿蜂群采蜜的仿生行为,容易求得可行解。但是该算法依然存在着种群数量过多、速度较慢的缺点。分析了ABC算法的模型并对更新策略进行了改进,在ABC算法得到初始解的路径点后再使用A-star算法进行优化,通过将两种算法组合的方式进行改进。实验证明在解决TSP的路径规划中,整体的路径表现更优,且减少了冗杂的迭代更新,提升了算法的效果。

混合算法求解着色瓶颈旅行商问题

基于着色旅行商问题(colored traveling salesman problem,CTSP),给出了一种适用性更加宽泛的组合优化问题模型:着色瓶颈旅行商问题(colored bottleneck traveling salesman problem,CBTSP).CBTSP可建模含有部分重合工作区域的规划问题,譬如有合作任务和单独任务的人员与车辆的路线规划,此类问题由于目标函数与旅行商问题不一样,因此不能够用CTSP模型来建模.由于CBTSP属于NP难问题,对于规模大的此类问题,自然启发式算法是个合适的选择.基于此,提出了一种自然启发式算法求解CBTSP,该算法是基于伊藤过程的粒子群算法(particle swarm optimization,PSO)、模拟退火算法(simulated annealing,SA)和遗传算法(genetic algorithm,GA)的混合算法(PSGA).PSGA首先用二重染色体编码来构建问题的解,然后运用遗传算法的交叉操作进行更新,其中交叉长度由伊藤过程的活动强度来控制,而活动强度由粒子半径和环境温度来决定.为了充分验证算法的有效性,使用小尺度到大尺度不同规模的数据进行实验,通过广泛的实验与分析表明:PSGA求解CBTSP问题的求解质量要优于对比算法.

改进蜂群算法求解大规模着色瓶颈旅行商问题

在智能交通、多任务协作等领域,用着色瓶颈旅行商问题(CBTSP,colored bottleneck traveling salesman problem)所构建模型尺度易趋向于大规模,因此有必要研究大规模CBTSP及其求解算法。本文将一种改进蜂群算法(IABC,improved artificial bee colony algorithm)应用于求解大规模CBTSP。IABC首先运用m-tour编码方法生成问题的解,然后使用产生邻近解(GNS,generate neighboring solution)优化蜂群算法求解该问题,GNS通过采用删除和重插入操作来产生新的解,并在该过程中实现对已有解的优化。实验表明IABC求解大规模CBTSP问题的求解质量优于其他对比算法。

基于基因库求解旅行商问题的遗传算法

针对传统遗传算法(genetic algorithm,GA)求解旅行商问题(traveling salesman problem,TSP)存在寻优效率低、实验结果缺乏一致性等问题,提出了一种基于基因库的遗传算法(genetic algorithm based on genes pool,GPGA)。GPGA从种群中搜索减小哈密顿圈长度的边,并当做优良基因构成基因库。父代哈密顿圈在基因库引导下产生更优的子代哈密顿圈,基因库也随着种群的不断进化而同步更新,引导种群个体逐步向最优解靠近。算例结果表明在同样条件下,GPGA比传统遗传算法和几种改进遗传算法的性能更优。