Ants can orienteer a thief in their robbery

The Thief Orienteering Problem (ThOP) is a multi-component problem that combines features of two classic combinatorial optimization problems: Orienteering Problem and Knapsack Problem. The ThOP is challenging due to the given time constraint and the interaction between its components. We propose an Ant Colony Optimization algorithm together with a new packing heuristic to deal individually and interactively with problem components. Our approach outperforms existing work on more than 90% of the benchmarking instances, with an average improvement of over 300%.

• Publication year

  2020

• Venue

  Operations Research Letters

• Publication date

  2020-04-15

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1016/j.orl.2020.08.011arXiv 2004.07017
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A fitness landscape analysis of the travelling thief problem

  2018influential reference
• Local Search in Combinatorial Optimization

  2018cited by this paper
• The Thief Orienteering Problem: Formulation and Heuristic Approaches

  2018influential reference
• Attractive orienteering problem with proximity and timing interactions

  2018cited by this paper
• A Fully Polynomial Time Approximation Scheme for Packing While Traveling

  2017cited by this paper
• Exact Approaches for the Travelling Thief Problem

  2017cited by this paper
• An orienteering-based approach to manage emergency situation

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

  2016cited by this paper
• Evolutionary computation for multicomponent problems: opportunities and future directions

  2016cited by this paper
• Population-based vs. Single-solution Heuristics for the Travelling Thief Problem

  2016cited by this paper
• Fast Heuristics for the Multiple Traveling Thieves Problem

  2016cited by this paper
• A case study of algorithm selection for the traveling thief problem

  2016cited by this paper
• A Periodic Traveling Politician Problem with Time-Dependent Rewards

  2016cited by this paper
• Stealing Items More Efficiently with Ants: A Swarm Intelligence Approach to the Travelling Thief Problem

  2016cited by this paper
• Orienteering Problem: A survey of recent variants, solution approaches and applications

  2016cited by this paper
• Time-dependent routing problems: A review

  2015cited by this paper
• Approximate Approaches to the Traveling Thief Problem

  2015influential reference
• Cosolver2B: An efficient local search heuristic for the Travelling Thief Problem

  2015cited by this paper
• Trip Recommendation with Multiple User Constraints by Integrating Point-of-Interests and Travel Packages

  2014cited by this paper
• A comprehensive benchmark set and heuristics for the traveling thief problem

  2014cited by this paper
• Packing While Traveling: Mixed Integer Programming for a Class of Nonlinear Knapsack Problems

  2014cited by this paper
• On investigation of interdependence between sub-problems of the Travelling Thief Problem

  2014influential reference
• The travelling thief problem: The first step in the transition from theoretical problems to realistic problems

  2013cited by this paper
• Biased random-key genetic algorithms for combinatorial optimization

  2011cited by this paper
• The orienteering problem: A survey

  2011cited by this paper
• Experimental Methods for the Analysis of Optimization Algorithms

  2010cited by this paper
• F-Race and Iterated F-Race: An Overview

  2010cited by this paper
• Routing problems with loading constraints

  2010cited by this paper
• Ant colony optimization theory: A survey

  2005cited by this paper
• Ant Colony Optimization

  2001influential reference
• Iterated Local Search

  2001cited by this paper
• MAX-MIN Ant System

  2000cited by this paper
• Ant colony optimization: a new meta-heuristic

  1999cited by this paper
• A fast and effective heuristic for the orienteering problem

  1996cited by this paper
• The Orienteering Problem

  1987cited by this paper

• Algorithms for the thief orienteering problem on directed acyclic graphs

  2024cites this paper
• The Thief Orienteering Problem on Series-Parallel Graphs

  2024cites this paper
• Genetic Programming for 5×5 Matrix Multiplication

  2024cites this paper
• Travelling thief problem: a survey of recent variants, solution approaches and future directions

  2024cites this paper
• Self-Adaptive Ant System with Hierarchical Clustering for the Thief Orienteering Problem

  2023influential citation
• Too Constrained for Genetic Algorithms too Hard for Evolutionary Computing the Traveling Tournament Problem

  2023cites this paper
• Modelling and optimization of run-of-mine stockpile recovery

  2021cites this paper
• Run-of-mine stockyard recovery scheduling and optimisation for multiple reclaimers

  2021cites this paper
• Efficiently solving the thief orienteering problem with a max–min ant colony optimization approach

  2021influential citation