The Thief Orienteering Problem: Formulation and Heuristic Approaches
- 1 July 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-9
Abstract
This paper introduces the Thief Orienteering Problem (ThOP), a multi-component problem that combines two classic combinatorial problems: Orienteering Problem (OP) and Knapsack Problem (KP). In this problem, a person (called the thief) carries a capacitated knapsack and has a time limit to collect items distributed in a set of cities. The thief has fixed start and end points, begins his journey with the knapsack empty, and travels with speed inversely proportional to the knapsack weight. While there is time, the thief may visit the cities and collect items. The aim of the problem is to determine the thief's route and items to collect in order to maximize the knapsack profit. We formally describe the ThOP by a mixed integer non-linear programming formulation and present two heuristic approaches based on Iterated Local Search (ILS) and Biased Random-Key Genetic Algorithm (BRKGA) metaheuristics. Our results showed that BRKGA outperformed ILS for a large majority of instances.Keywords
This publication has 14 references indexed in Scilit:
- Hybrid method with CS and BRKGA applied to the minimization of tool switches problemComputers & Operations Research, 2016
- Approximate Approaches to the Traveling Thief Problem2015
- A comprehensive benchmark set and heuristics for the traveling thief problem2014
- BRKGA Algorithm for the Capacitated Arc Routing ProblemElectronic Notes in Theoretical Computer Science, 2011
- The orienteering problem: A surveyEuropean Journal of Operational Research, 2011
- Biased random-key genetic algorithms for combinatorial optimizationJournal of Heuristics, 2010
- Iterated Local Search: Framework and Applications2010
- The team orienteering problemEuropean Journal of Operational Research, 1996
- A fast and effective heuristic for the orienteering problemEuropean Journal of Operational Research, 1996
- Genetic Algorithms and Random Keys for Sequencing and OptimizationINFORMS Journal on Computing, 1994