An Effective Iterated Two-stage Heuristic Algorithm for the Multiple Traveling Salesmen Problem

• URL: http://arxiv.org/abs/2201.09424v1
• Date: Mon, 24 Jan 2022 02:43:08 GMT
• Title: An Effective Iterated Two-stage Heuristic Algorithm for the Multiple Traveling Salesmen Problem
• Authors: Jiongzhi Zheng and Yawei Hong and Wenchang Xu and Wentao Li and Yongfu Chen
• Abstract summary: Multiple Traveling Salesmen Problem mTSP is a general extension of the famous NP-hard Traveling Salesmen Problem (TSP) In this paper, we address the mTSP with both of the minsum objective and the minmax objective, which aims at minimizing the total length of the m tours. We propose an iterated two-stage algorithm, denoted as ITSHA.
• Score: 2.5374893654938324
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The multiple Traveling Salesmen Problem mTSP is a general extension of the famous NP-hard Traveling Salesmen Problem (TSP), that there are m (m>1) salesmen to visit the cities. In this paper, we address the mTSP with both of the minsum objective and the minmax objective, which aims at minimizing the total length of the m tours and the length of the longest tour among all the m tours, respectively. We propose an iterated two-stage heuristic algorithm, denoted as ITSHA. Each iteration of ITSHA consists of an initialization stage and an improvement stage. The purpose of the initialization stage is to generate high-quality and diverse initial solutions. The improvement stage mainly applies the variable neighborhood search (VNS) approach based on our proposed local search neighborhoods to optimize the initial solution generated by the initialization stage. Moreover, some local optima escaping approaches are employed to enhance the search ability of the algorithm. Extensive experimental results on a wide range of public benchmark instances show that ITSHA significantly outperforms state-of-the-art heuristic algorithms in solving the mTSP on both the objectives.

Related papers

• Are Large-Language Models Graph Algorithmic Reasoners? [45.592341677933646]
  We introduce a benchmark designed to evaluate Large Language Models (LLMs) performance on classical algorithmic reasoning tasks on explicit graphs. Our benchmark encompasses five fundamental algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS) for connectivity, Dijkstra's algorithm and Floyd-Warshall algorithm for all nodes shortest path, and Prim's Minimum Spanning Tree (MST-Prim's) algorithm.
  arXiv  Detail & Related papers  (2024-10-29T23:28:37Z)
• iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning [8.747306544853961]
  The paper considers a Min-Max Multiple Traveling Salesman Problem (MTSP) The goal is to find a set of tours, one for each agent, to collectively visit all the cities while minimizing the length of the longest tour. We introduce a new self-supervised, bilevel, end-to-end learning framework, which we refer to as imperative MTSP (iMTSP)
  arXiv  Detail & Related papers  (2024-05-01T02:26:13Z)
• 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)
• Unsupervised Learning of Initialization in Deep Neural Networks via Maximum Mean Discrepancy [74.34895342081407]
  We propose an unsupervised algorithm to find good initialization for input data. We first notice that each parameter configuration in the parameter space corresponds to one particular downstream task of d-way classification. We then conjecture that the success of learning is directly related to how diverse downstream tasks are in the vicinity of the initial parameters.
  arXiv  Detail & Related papers  (2023-02-08T23:23:28Z)
• Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding [25.11387753357413]
  We study the multi-goal task assignment and path finding (MG-TAPF) problem from theoretical and algorithmic perspectives. Theoretically, we prove that the MG-TAPF problem is NP-hard to solve optimally. We present algorithms that build upon algorithmic techniques for the multi-agent path finding problem and solve the MG-TAPF problem optimally and bounded-suboptimally.
  arXiv  Detail & Related papers  (2022-08-02T03:17:29Z)
• 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)
• TaSPM: Targeted Sequential Pattern Mining [53.234101208024335]
  We propose a generic framework namely TaSPM, based on the fast CM-SPAM algorithm. We also propose several pruning strategies to reduce meaningless operations in mining processes. Experiments show that the novel targeted mining algorithm TaSPM can achieve faster running time and less memory consumption.
  arXiv  Detail & Related papers  (2022-02-26T17:49:47Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)
• Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
  We study the multi-armed bandit problem with subgaussian rewards. We show that a variant of the explore-then-commit (ETC) algorithm can achieve the optimality for multi-armed bandit problems.
  arXiv  Detail & Related papers  (2020-02-21T08:07:56Z)

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.