A variable neighborhood search for flying sidekick traveling salesman problem

The efficiency and dynamism of unmanned aerial vehicles, or drones, have presented substantial application opportunities in several industries in the last years. Notably, logistic companies have given close attention to these vehicles to reduce delivery time and operational cost. A variant of the traveling salesman problem (TSP), called the flying sidekick traveling salesman problem, was introduced involving drone‐assisted parcel delivery. The drone launches from the truck, proceeds to deliver parcels to a customer, and then is recovered by the truck at a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic where the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the general variable neighborhood search is employed to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve significantly delivery time. Furthermore, we provide a new set of instances based on the well‐known traveling salesman problem library instances.     

改进的遗传算法求解旅行商问题

提出一种解决旅行商问题的改进遗传算法.在传统遗传算法的基础上,引入贪婪算法进行种群初始化;从遗传进化代数和个体适应函数值两个方面实现遗传参数自适应调节,在加快寻优速度的同时防止寻优陷入局部最优;采用基于贪婪方法的启发式交叉算子优化交叉结果;对交叉前后的种群分别实施精英个体保留策略,保证最优基因结构得以延续.实验结果分析表明,改进的遗传算法可以在种群规模较小的情况下具有更可靠的寻优能力.     

基于改进离散粒子群算法的炼钢连铸最优浇次计划

提出了浇次数未知的最优浇次计划模型. 在分析该模型求解困难的基础上, 提出了用伪旅行商表示该模型的方法. 针对离散粒子群优化具有收敛速度、精度低, 但能充分利用各粒子的局部最优值和全局最优值信息的特点,而序列倒置算子具有收敛速度和精度较高, 但学习具有盲目性的特点, 结合二者优点, 提出了一种基于序列倒置的改进离散粒子群优化算法. 实验研究表明, 该算法与普通离散粒子群优化算法相比, 不论是收敛速度和还是求解精度都有了较大提高. 基于该改进算法求解最优浇次计划模型的研究表明: 所提伪旅行商问题模型非常适合用于组浇模型描述. 应用实际生产数据的计算表明该模型及其求解方法均非常有效.     

Parallelized neural network system for solving Euclidean traveling salesman problem

We investigate a parallelized divide-and-conquer approach based on a self-organizing map (SOM) in order to solve the Euclidean traveling salesman problem (TSP). Our approach consists of dividing cities into municipalities, evolving the most appropriate solution from each municipality so as to find the best overall solution and, finally, joining neighborhood municipalities by using a blend operator to identify the final solution. We evaluate performance of parallelized approach over standard TSP test problems (TSPLIB) to show that our approach gives a better answer in terms of quality and time rather than the sequential evolutionary SOM.     

Runtime Analysis of an Ant Colony Optimization Algorithm for TSP Instances

Ant colony optimization (ACO) is a relatively new random heuristic approach for solving optimization problems. The main application of the ACO algorithm lies in the field of combinatorial optimization, and the traveling salesman problem (TSP) is the first benchmark problem to which the ACO algorithm has been applied. However, relatively few results on the runtime analysis of the ACO on the TSP are available. This paper presents the first rigorous analysis of a simple ACO algorithm called (1 + 1) MMAA (Max-Min ant algorithm) on the TSP. The expected runtime bounds for (1 + 1) MMAA on two TSP instances of complete and non-complete graphs are obtained. The influence of the parameters controlling the relative importance of pheromone trail versus visibility is also analyzed, and their choice is shown to have an impact on the expected runtime.     

An Algorithm for the One Commodity Pickup and Delivery Traveling Salesman Problem with Restricted Depot

In this paper we study the one commodity pickup-and-delivery traveling salesman problem with restricted depot (1-PDTSP-RD), which is a generalization of the classical traveling salesman problem (TSP). We first introduce a polynomial size integer programming formulation for the problem and then study the feasibility issue which is shown to be \(\mathcal {NP}\)-complete by itself. In particular, we prove sufficient conditions for the feasibility of the problem and provide a polynomial algorithm to find a feasible solution. We also develop a bound on the cost of the 1-PDTSP-RD solution in terms of the cost of the TSP solution. Based on this bound, we provide a heuristic algorithm to solve the 1PDTSP-RD. Extensive numerical experiments are performed to evaluate the efficiency of both the exact and approximation algorithms.     

基于多起点和Mask策略的深度强化学习算法求解覆盖旅行商问题

覆盖旅行商问题(covering salesman problem, CSP)是旅行商问题的变体,在防灾规划、急救管理中有着广泛应用.由于传统方法求解问题实例耗时严重,近年来深度神经网络被提出用于解决该类组合优化问题,在求解速度和泛化性上有明显的优势.现有基于深度神经网络求解CSP的方法求解质量较低,特别在大规模实例上与传统的启发式方法相比存在较大差距.针对上述问题,提出一种新的基于深度强化学习求解CSP的方法,由编码器对输入特征进行编码,提出新的Mask策略对解码器使用自注意力机制构造解的过程进行约束,并提出多起点策略改善训练过程、提高求解质量.实验结果表明,所提方法对比现有基于深度神经网络的求解方法进一步缩小了最优间隙,同时有着更高的样本效率,在不同规模和不同覆盖类型的CSP中展现出更强的泛化能力,与启发式算法相比在求解速度上有10～40倍的提升.     

Memetic Algorithm based on Improved Inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem

In this study, an Improved Inver-over operator is proposed to solve the Euclidean traveling salesman problem (TSP) problem. The Improved Inver-over operator is tested on 14 different TSP examples selected from TSPLIB. The application of the Improved Inver-over operator gives much more effective results regarding to the best and average error values than the Basic Inver-over operator. Then an effective Memetic Algorithm based on Improved Inver-over operator and Lin-Kernighan local search is implemented. To speed up the convergence capability of the presented algorithm, a restart technique is employed. We evaluate the proposed algorithm based on standard TSP test problems and show that the proposed algorithm performs better than other Memetic Algorithm in terms of solution quality and computational effort.     

牛奶配送问题的两阶段平衡TSP优化算法研究

牛奶配送问题中包含访问次数不同的节点,该问题可以当做两阶段旅行商问题进行求解。为有效地求解节点个数处于平衡条件下的牛奶配送问题的两阶段旅行商问题,提出了一种启发式优化求解方法,有助提高目标问题的求解效率和性能。针对节点数量平衡性和节点访问次数不同的特点,提出一种基于节点划分的动态规划优化。通过对实例进行计算和比较,结果验证了所提方法的有效性和优越性。     

应用改进的遗传算法求解TSP问题

旅行商问题,也称货郎担问题,属于完全NP问题,而遗传算法在解决组合排列问题方面占有很重要的地位.针对TSP问题,提出了一种改进的遗传算法.利用交换启发交叉算子和可变交叉概率实现局部搜索,加快算法的收敛速度,利用变换变异算子和可变变异概率维持群体的多样性防止算法早熟收敛.Java仿真实验结果表明,改进后的算法明显优于传统的遗传算法,说明该算法具有良好的有效性和可行性.     

The salesman and the tree: the importance of search in CP

The traveling salesman problem (TSP) is a challenging optimization problem for CP and OR that has many industrial applications. Its generalization to the degree constrained minimum spanning tree problem (DCMSTP) is being intensively studied by the OR community. In particular, classical solution techniques for the TSP are being progressively generalized to the DCMSTP. Recent work on cost-based relaxations has improved CP models for the TSP. However, CP search strategies have not yet been widely investigated for these problems. The contributions of this paper are twofold. We first introduce a natural generalization of the weighted cycle constraint (WCC) to the DCMSTP. We then provide an extensive empirical evaluation of various search strategies. In particular, we show that significant improvement can be achieved via our graph interpretation of the state-of-the-art Last Conflict heuristic.     

A theoretical investigation into the performance of the Hopfieldmodel

An analysis is made of the behavior of the Hopfield model as a content-addressable memory (CAM) and as a method of solving the traveling salesman problem (TSP). The analysis is based on the geometry of the subspace set up by the degenerate eigenvalues of the connection matrix. The dynamic equation is shown to be equivalent to a projection of the input vector onto this subspace. In the case of content-addressable memory, it is shown that spurious fixed points can occur at any corner of the hypercube that is on or near the subspace spanned by the memory vectors. Analysed is why the network can frequently converge to an invalid solution when applied to the traveling salesman problem energy function. With these expressions, the network can be made robust and can reliably solve the traveling salesman problem with tour sizes of 50 cities or more.     

Particle swarm optimization-based algorithms for TSP and generalized TSP

A novel particle swarm optimization (PSO)-based algorithm for the traveling salesman problem (TSP) is presented. An uncertain searching strategy and a crossover eliminated technique are used to accelerate the convergence speed. Compared with the existing algorithms for solving TSP using swarm intelligence, it has been shown that the size of the solved problems could be increased by using the proposed algorithm.Another PSO-based algorithm is proposed and applied to solve the generalized traveling salesman problem by employing the generalized chromosome. Two local search techniques are used to speed up the convergence. Numerical results show the effectiveness of the proposed algorithms.     

蚁群算法在求解旅行商问题中的应用综述

旅行商问题作为组合优化研究中最具挑战的问题之一, 自被提出以来就引起了学术界的广泛关注并提出了大量的方法来解决它. 蚁群算法是求解复杂组合优化问题的一种启发式仿生进化算法, 是求解旅行商问题的有效手段. 本文分别介绍蚁群算法中几个有代表性的算法, 综述了蚁群算法的改进、融合和应用的文献研究进展, 以评价近年来不同版本的蚁群算法为解决旅行商问题的发展和研究成果, 并针对改进蚁群算法结构框架、算法参数的设置及优化、信息素优化和混合算法等方面, 对现被提出的改进算法进行了分类综述. 对蚁群算法在未来对旅行商问题及其他不同领域的研究内容和研究热点的进一步发展提供了展望和依据.     

基于自适应继承策略的帝国竞争算法求解旅行商问题

针对帝国竞争算法在求解旅行商问题时局部搜索能力不强和容易陷入局部最优的缺陷,提出一种基于自适应继承策略的帝国竞争算法.该算法采用自适应继承策略的启发式交叉算子、单点局部插入策略和固定邻域的2-opt算子来增强算法的局部优化能力,并加入帝国精英解集以保持种群的多样性.通过标准实例测试,验证了所提出的改进策略的优越性,与基于启发式交叉算子和帝国主义算法为框架的其他算法进行对比,实验结果表明,该算法求解中小规模的解旅行商问题具有较高的求解精度和较快的收敛速度.     

多蚁群分级优化的多目标求解方法*

为提高多目标优化方法的求解性能,在给出了蚁群算法优化函数类问题求解方法的基础上,提出了基于多蚁群分级优化多目标问题的求解方法。构建了子蚁群以自身启发式信息及以其他子群的启发式信息获得准Pareto解以及采用各子群的每一只蚂蚁获得的准Pareto解作支配判断,从而提高Pareto解的多样性;构建了父蚁群以准Pareto解作为空间节点构成TSP类似的组合优化问题,其求解结果以获得多目标优化问题的Pareto解的前沿,从而提高Pareto解的均匀分布性。通过优化实例验证,结果表明,多蚁群分级优化的多目标求解方法     

论遗传算法在旅行商问题中的应用

旅行商问题是算法应用中的基本问题,遗传算法具有通用性、智能性、鲁棒性、全局性和并行性的特点,正好适合于该问题的求解。但基本遗传算法在解决旅行商问题时效率不高,并且容易陷于局部最优解。为了解决这一问题,提出了一种改进的遗传算法。文章首先对旅行商问题进行了描述,对遗传算法进行了介绍,对其中的个体选择、交叉算法等重要因素做了一定地改进。最后,用一个简单的实例对基本遗传算法和改进的遗传算法进行了比较,发现改进的遗传算法在解决旅行商问题上的效率问题上有了一定的提高。     

Neurodynamic programming: a case study of the traveling salesman problem

The paper focuses on the study of solving the large-scale traveling salesman problem (TSP) based on neurodynamic programming. From this perspective, two methods, temporal difference learning and approximate Sarsa, are presented in detail. In essence, both of them try to learn an appropriate evaluation function on the basis of a finite amount of experience. To evaluate their performances, some computational experiments on both the Euclidean and asymmetric TSP instances are conducted. In contrast with the large size of the state space, only a few training sets have been used to obtain the initial results. Hence, the results are acceptable and encouraging in comparisons with some classical algorithms, and further study of this kind of methods, as well as applications in combinatorial optimization problems, is worth investigating.     

Embedded local search approaches for routing optimization

This paper presents a new class of heuristics which embed an exact algorithm within the framework of a local search heuristic. This approach was inspired by related heuristics which we developed for a practical problem arising in electronics manufacture. The basic idea of this heuristic is to break the original problem into small subproblems having similar properties to the original problem. These subproblems are then solved using time intensive heuristic approaches or exact algorithms and the solution is re-embedded into the original problem. The electronics manufacturing problem where we originally used the embedded local search approach, contains the Travelling Salesman Problem (TSP) as a major subproblem. In this paper we further develop our embedded search heuristic, HyperOpt, and investigate its performance for the TSP in comparison to other local search based approaches. We introduce an interesting hybrid of HyperOpt and 3-opt for asymmetric TSPs which proves more efficient than HyperOpt or 3-opt alone. Since pure local search seldom yields solutions of high quality we also investigate the performance of the approaches in an iterated local search framework. We examine iterated approaches of Large-Step Markov Chain and Variable Neighbourhood Search type and investigate their performance when used in combination with HyperOpt. We report extensive computational results to investigate the performance of our heuristic approaches for asymmetric and Euclidean Travelling Salesman Problems. While for the symmetric TSP our approaches yield solutions of comparable quality to 2-opt heuristic, the hybrid methods proposed for asymmetric problems seem capable of compensating for the time intensive embedded heuristic by finding tours of better average quality than iterated 3-opt in many less iterations and providing the best heuristic solutions known, for some instance classes.     

混合算法求解多目标平衡旅行商问题

平衡旅行商问题(balanced traveling salesman problem, BTSP)是旅行商问题(traveling salesman problem, TSP)的变化模型,是另一种组合优化问题,可在汽轮机(gas turbine engines, GTE)等的优化问题中得到应用,但BTSP模型只能对含单个旅行商一个任务的优化问题建模,不能同时对含多个旅行商多任务的问题进行建模和优化.基于此,首次提出了一种多目标平衡旅行商问题(multi-objective balanced traveling salesman problem, MBTSP)模型,可建模含多个旅行商多任务的优化问题,具体可应用在含多个目标或个体的实际问题,例如含多个GTE的优化.相关文献的研究已证实,伊藤算法和遗传算法(genetic algorithm, GA)在求解组合优化问题中具有较好的性能,因此,应用混合伊藤算法(hybrid ITO algorithm, HITO)和混合遗传算法来求解MBTSP问题.HITO通过蚁群算法(ant colony optimization, ACO)来产生基于图的概率生成模型,再用伊藤算法的漂移和波动算子对该图模型进行更新,从而得到MBTSP的最优解.对于混合遗传算法,第一个用贪心法对遗传算法进行改进,命名为贪心法遗传算法(genetic algorithm with greedy initialization, GAG),第二个用爬山算法优化遗传算法,称之为爬山法遗传算法(genetic algorithm by hill-climbing, GAHC),最后一个为模拟退火遗传算法(genetic algorithm with simulated annealing, GASA).为了有效验证该算法,使用小尺度到大尺度的不同规模MBTSP问题的数据进行实验,结果表明：混合算法在求解MBTSP问题是有效的,并表现出不同的特点.