Breakout local search for the traveling salesman problem with job-times

The traveling salesman problem with job-times combines two classic NP-hard combinatorial optimization problems: the traveling salesman problem and the scheduling problem. In this problem, a traveler visits sequentially n locations with given travel-times between locations and assigns, to each visited location, one of n jobs with location-dependent job-times. When a job is assigned to a specific location, the job starts to run at that location for its given duration. The goal of the problem is to find a job assignment to minimize the maximum completion time of the n jobs. This work presents an effective heuristic algorithm for the problem based on the breakout local search method. The algorithm employs a local search procedure to find high-quality local optimal solutions and a dedicated perturbation procedure to escape local optimum traps. The local search procedure is based on the 2-opt and j-swap moves adapted to the problem, while the perturbation procedure combines both informed and random 2-opt and j-swap operations. To speed up the search, we introduce a dedicated strategy to identify promising neighboring solutions. We evaluate the algorithm on the 310 benchmark instances in the literature. Computational results show that the proposed algorithm outperforms the previous methods, by reporting improved best results (new upper bounds) for 291 instances and equal best results for 16 other instances. The main search components of the algorithm are investigated to shed light on their contributions to the performance of the algorithm.

• Publication year

  2023

• Venue

  Expert systems with applications

• Publication date

  2023-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.2139/ssrn.4274379
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Memetic search for the minmax multiple traveling salesman problem with single and multiple depots

  2022cited by this paper
• Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems

  2022cited by this paper
• A fast tri-individual memetic search approach for the distance-based critical node problem

  2022cited by this paper
• Grouping memetic search for the colored traveling salesmen problem

  2021cited by this paper
• A combinatorial evolutionary algorithm for unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, limited worker resources and learning effect

  2021cited by this paper
• The Traveling Salesman Problem with Job-times (TSPJ)

  2021influential reference
• Iterated local search with tabu search for the weighted vertex coloring problem

  2021cited by this paper
• General swap-based multiple neighborhood adaptive search for the maximum balanced biclique problem

  2020cited by this paper
• A bi-objective model of preventive maintenance planning in distributed systems considering vehicle routing problem

  2018cited by this paper
• An iterated local search for the Traveling Salesman Problem with release dates and completion time minimization

  2018cited by this paper
• Breakout Local Search for the Travelling Salesman Problem

  2018cited by this paper
• A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem

  2017cited by this paper
• Memetic Search for Identifying Critical Nodes in Sparse Graphs

  2017cited by this paper
• Service agent-transport agent task planning incorporating robust scheduling techniques

  2017cited by this paper
• Frequency-driven tabu search for the maximum s-plex problem

  2017cited by this paper
• The irace package: Iterated racing for automatic algorithm configuration

  2016cited by this paper
• Memetic search for the quadratic assignment problem

  2015cited by this paper
• A breakout local search (BLS) method for solving the assembly sequence planning problem

  2015cited by this paper
• Breakout local search for the Steiner tree problem with revenue, budget and hop constraints

  2014cited by this paper
• Breakout Local Search for maximum clique problems

  2013cited by this paper
• Breakout local search for the quadratic assignment problem

  2013influential reference
• A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows

  2013cited by this paper
• Breakout Local Search for the Max-Cutproblem

  2013cited by this paper
• Scheduling contractors' farm-to-farm crop harvesting operations

  2006cited by this paper
• Stochastic Local Search: Foundations & Applications

  2004cited by this paper
• An interactive approach for hierarchical analysis of helicopter logistics in disaster relief operations

  2002cited by this paper
• Iterated Local Search

  2001cited by this paper
• Selection of routes in a flexible manufacturing facility

  1997cited by this paper
• Tabu Search

  1997influential reference
• Robust taboo search for the quadratic assignment problem

  1991cited by this paper
• TSPLIB - A Traveling Salesman Problem Library

  1991cited by this paper
• Computer solutions of the traveling salesman problem

  1965cited by this paper

• nLKH-ACS: A Niching Lin-Kernighan–Helsgaun-Based Ant Colony System for Multisolution Traveling Salesman Problems

  2025cites this paper
• An adaptive variable neighborhood search for the traveling salesman problem with job-times

  2025cites this paper
• How emissions trading system affects liner ship disruption recovery

  2025cites this paper
• Branch-and-cut algorithms for the traveling salesman problem with job times

  2025cites this paper