The double traveling salesman problem with multiple stacks: A variable neighborhood search approach

The double traveling salesman problem with multiple stacks (DTSPMS) is a vehicle routing problem that consists on finding the minimum total length tours in two separated networks, one for pickups and one for deliveries. A set of orders is given, each one consisting of a pickup location and a delivery location, and it is required to send an item from the former location to the latter one. Repacking is not allowed, but collected items can be packed in several rows in such a way that each row must obey the LIFO principle. In this paper, a variable neighborhood search approach using four new neighborhood structures is presented to solve the problem.     

Variable neighborhood search for multi-objective resource allocation problems

The Resource Allocation Problem (RAP) is a classical problem in the field of operations management that has been broadly applied to real problems such as product allocation, project budgeting, resource distribution, and weapon-target assignment. In addition to focusing on a single objective, the RAP may seek to simultaneously optimize several expected but conflicting goals under conditions of resources scarcity. Thus, the single-objective RAP can be intuitively extended to become a Multi-Objective Resource Allocation Problem (MORAP) that also falls in the category of NP-Hard. Due to the complexity of the problem, metaheuristics have been proposed as a practical alternative in the selection of techniques for finding a solution. This study uses Variable Neighborhood Search (VNS) algorithms, one of the extensively used metaheuristic approaches, to solve the MORAP with two important but conflicting objectives—minimization of cost and maximization of efficiency. VNS searches the solution space by systematically changing the neighborhoods. Therefore, proper design of neighborhood structures, base solution selection strategy, and perturbation operators are used to help build a well-balanced set of non-dominated solutions. Two test instances from the literature are used to compare the performance of the competing algorithms including a hybrid genetic algorithm and an ant colony optimization algorithm. Moreover, two large instances are generated to further verify the performance of the proposed VNS algorithms. The approximated Pareto front obtained from the competing algorithms is compared with a reference Pareto front by the exhaustive search method. Three measures are considered to evaluate algorithm performance: D1_R, the Accuracy Ratio, and the number of non-dominated solutions. The results demonstrate the practicability and promise of VNS for solving multi-objective resource allocation problems.     

Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing – tabu search algorithm to solve the symmetrical traveling salesman problem

This paper applies a hybrid simulated annealing – tabu search algorithm to solve the Traveling Salesman Problem (TSP). Fully considering the characteristics of the hybrid algorithm, we develop a dynamic neighborhood structure for the hybrid algorithm to improve search efficiency by reducing the randomness of the conventional 2-opt neighborhood. A circle-directed mutation is developed to achieve this dynamic neighborhood structure. Furthermore, we propose adaptive parameters that can be automatically adjusted by the algorithm based on context specific examples. This negates the need to frequently readjust algorithm parameters. We employ benchmarks obtained from TSPLIB (a library of sample instances for the TSP) to test our algorithm, and find that the proposed algorithm can obtain satisfactory solutions within a reasonable amount of time. The experimental results demonstrate that the proposed hybrid algorithm can overcome the disadvantages of traditional simulated annealing and tabu search methods. The results also show that the dynamic neighborhood structure is more efficient and accurate than the classical 2-opt. Also, adaptive parameters are appropriate for almost all of the numerical examples tested in this paper. Finally, the experimental results are compared with those of other algorithms, to demonstrate the improved accuracy and efficiency of the proposed algorithm.     

基于邻域搜索的改进最大最小蚁群算法

针对蚁群算法求解旅行商问题时易陷入局部最优的问题,提出一个改进的混合最大最小蚁群算法,并应用于求解旅行商问题.上述算法设计了一种新的信息素更新模型,单个蚂蚁每走一步就进行信息素局部更新,在所有的蚂蚁搜索一周后,最优路径蚂蚁进行全局信息素更新.提出一种新的邻域搜索模型,将邻域大小设置为原来的一半,提高了计算的效率.在每个蚂蚁的一个周期循环后,使用邻域搜索算法优化最优解的路径长度.仿真结果表明,改进算法具有较高的求解精度和收敛速度.     

一种求解TSP问题的ACO&SS算法设计

提出一种求解旅行商(TSP)问题的新型分散搜索算法.将蚁群算法(ACO)的构解方法引入分散搜索(SS)算法,在搜索过程中既考虑解的质量,又考虑解的分散性.采用一种将蚁群算法的信息素更新技术与分散搜索的组合机制相结合的新型子集组合成新解的构解机制,同时采用动态更新参考集与临界准则策略来加快收敛速度.实验结果表明,该算法优于其他现有的方法,获得了较好的结果.     

AnO(logk)-approximation algorithm for thek minimum spanning tree problem in the plane

Givenn points in the Euclidean plane, we consider the problem of finding the minimum tree spanning anyk points. The problem isNP-hard and we give anO(logk)-approximation algorithm.     

一种结合局部搜索策略的求解TSP的演化算法

介绍了一种结合局部搜索策略的求解流动旅行商问题（TSP）的演化算法。该算法的主要思想是将局部搜索策略在邻域内搜索的快速性与演化方法在全局搜索上的鲁棒性结合起来，从而跳离局部最优。将该算法用于TSPLIB中部分TSP实例上的试验结果表明：与传统的各种求解TSP的演化方法相比，该算法在获得全局最优解的精确度上有了一定的改善。     

The traveling purchaser problem with budget constraint

Let us consider a set of markets plus a depot and a set of products for each of which a positive demand is specified. Each product is made available in a subset of markets in each of which only a given quantity, less than or equal to the required one, can be purchased at a given unit price. The distance between each couple of markets and between each market and the depot is known. The Traveling Purchaser Problem with Budget constraint (TPP-B) looks for a simple cycle starting at and ending to the depot and visiting a subset of markets at a minimum traveling cost and such that the demand for each product is satisfied and the cost globally spent for purchasing the products does not exceed a defined budget threshold. As the TPP also this problem arises in several application domains, but while the former has been largely studied, very few contributions exist in the literature for the TPP-B. We propose and compare two solution algorithms, an enhanced local-search heuristic and a variable neighborhood search (VNS) approach also tested in a multi-start variant. The proposed algorithms have been used to solve both the capacitated and the uncapacitated version of the problem. Test problems have been obtained by adding a budget constraint to known benchmark instances for the TPP.     

Good triangulations yield good tours

Consider the following heuristic for planar Euclidean instances of the traveling salesman problem (TSP): select a subset of the edges which induces a planar graph, and solve either the TSP or its graphical relaxation on that graph. In this paper, we give several motivations for considering this heuristic, along with extensive computational results. It turns out that the Delaunay and greedy triangulations make effective choices for the induced planar graph. Indeed, our experiments show that the resulting tours are on average within 0.1% of optimality.     

Hybrid column generation and large neighborhood search for the dial-a-ride problem

Demographic change towards an ever aging population entails an increasing demand for specialized transportation systems to complement the traditional public means of transportation. Typically, users place transportation requests, specifying a pickup and a drop off location and a fleet of minibuses or taxis is used to serve these requests. The underlying optimization problem can be modeled as a dial-a-ride problem. In the dial-a-ride problem considered in this paper, total routing costs are minimized while respecting time window, maximum user ride time, maximum route duration, and vehicle capacity restrictions. We propose a hybrid column generation and large neighborhood search algorithm and compare different hybridization strategies on a set of benchmark instances from the literature.     

遗传算法的应用举例

遗传算法作为一种通用、高效的优化算法,已应用到工程计算的各个领域。该文首先简要阐述了遗传算法的基本原理和其操作步骤。同时为了验证其全局的寻优能力,采用MATLAB语言编制程序实现遗传算法对数值优化和旅行商问题的求解,需要说明的是这两类问题的程序编制和求解分别依赖于不同的已有遗传算法工具箱。为了便于说明遗传算法的优越性,分别将对数值优化和旅行商问题的计算结果与用局域搜索法和模拟退火得出的优化结果进行比较。比较结果表明,对于数值优化问题,遗传算法比局域搜索法具有更佳的寻优能力;对于旅行商问题的求解也能得到满意的结果。     

自适应动态邻域布谷鸟混合算法求解TSP问题

针对离散布谷鸟算法求解旅行商问题时邻域搜索效率低和易陷入局部最优解等问题,提出了一种自适应动态邻域布谷鸟混合算法（Adaptive Dynamic Neighborhood Hybrid Cuckoo Search algorithm,ADNHCS）。为了提升邻域搜索效率,设计了一种圆限定突变的动态邻域结构来降低经典算法的随机性;此外,提出了可根据迭代过程进行自适应参数调整的策略,并结合禁忌搜索算法来提升全局寻优的能力。使用MATLAB和标准TSPLIB数据库中的若干经典算例对算法性能进行了实验仿真,结果表明与其他基于布谷鸟算法、经典和新型群智能优化算法相比,ADNHCS算法在全局寻优能力以及稳定性方面表现更优。     

结合变邻域搜索的竞争Hopfield神经网络解决最大分散度问题

提出一种结合变邻域搜索的离散竞争Hopfield神经网络,用于求解最大分散度问题。为了克服神经网络易陷入局部最小值的问题,将变邻域搜索的思想引入到离散竞争Hopfield神经网络中,一旦网络陷入局部最小值,变邻域搜索能帮助神经网络动态改变搜索邻域,从而跳出局部最小值去搜寻更优的解。最后,针对最大分散度问题的实验结果表明,提出的算法具有良好的性能。     

A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants

This paper proposes a mathematical model, valid inequalities and polyhedral results for the minimum labeling Hamiltonian cycle problem. This problem is defined on an unweighted graph in which each edge has a label. The aim is to determine a Hamiltonian cycle with the least number of labels. We also define two variants of this problem by assigning weights to the edges and by considering the tour length either as an objective or as a constraint. A branch-and-cut algorithm for the three problems is developed, and computational results are reported on randomly generated instances and on modified instances from TSPLIB.