Learning-guided iterated local search for the minmax multiple traveling salesman problem

• URL: http://arxiv.org/abs/2403.12389v1
• Date: Tue, 19 Mar 2024 02:57:10 GMT
• Title: Learning-guided iterated local search for the minmax multiple traveling salesman problem
• Authors: Pengfei He, Jin-Kao Hao, Jinhui Xia,
• Abstract summary: We propose a leaning-driven iterated local search approach to the minmax multiple traveling salesman problem. We show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances.
• Score: 13.924692115320553
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The minmax multiple traveling salesman problem involves minimizing the longest tour among a set of tours. The problem is of great practical interest because it can be used to formulate several real-life applications. To solve this computationally challenging problem, we propose a leaning-driven iterated local search approach that combines an aggressive local search procedure with a probabilistic acceptance criterion to find high-quality local optimal solutions and a multi-armed bandit algorithm to select various removal and insertion operators to escape local optimal traps. Extensive experiments on 77 commonly used benchmark instances show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances. Additional experiments shed light on the understanding of the composing elements of the algorithm.

Related papers

• A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem [0.9790236766474201]
  This paper proposes a hybrid genetic algorithm for solving the Multiple Traveling Salesman Problem (mTSP) A novel crossover operator is designed to combine similar tours from two parents and offers great diversity for the population. Our algorithm outperforms all existing algorithms on average, with similar cutoff time thresholds, when tested against benchmark sets.
  arXiv  Detail & Related papers  (2023-07-14T01:57:10Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  This work proposes new characterizations of linear programming (ILP) with the concept of boundary solutions. We develop a new local search algorithm Local-ILP, which is efficient for solving general ILP validated on a large heterogeneous problem dataset. Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems.
  arXiv  Detail & Related papers  (2023-04-29T07:22:07Z)
• An Adaptive Repeated-Intersection-Reduction Local Search for the Maximum Independent Set Problem [5.459881847627117]
  The independent set (MIS) problem is a classical NP-hard problem with extensive applications in various areas. We propose an efficient local search algorithm for MIS called ARIR. Compared with four state-of-the-art algorithms, ARIR offers the best accuracy on 89 instances and obtains competitive results on the three remaining instances.
  arXiv  Detail & Related papers  (2022-08-16T14:39:38Z)
• Learning to Control Local Search for Combinatorial Optimization [4.243592852049962]
  A zoo of generic as well as problem-specific variants of local search is commonly used to compute approximate solutions. In this paper we identify three independent algorithmic aspects of such local search algorithms and formalize their sequential selection over an optimization process. We show that NeuroLS is able to outperform both, well-known general purpose local search controllers from Operations Research as well as latest machine learning-based approaches.
  arXiv  Detail & Related papers  (2022-06-27T10:48:56Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• An effective hybrid search algorithm for the multiple traveling repairman problem with profits [34.74325448504831]
  We propose an effective hybrid search algorithm based on the memetic algorithm framework. It integrates two distinguished features: a dedicated arc-based crossover to generate high-quality offspring solutions and a fast evaluation technique to reduce the complexity of exploring the classical neighborhoods.
  arXiv  Detail & Related papers  (2021-11-09T09:27:49Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.