The Thief Orienteering Problem: Formulation and Heuristic Approaches
| Autor: | Jonatas B. C. Chagas, Andre Gustavo dos Santos |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
021103 operations research Computer science Heuristic Iterated local search 0211 other engineering and technologies Orienteering 02 engineering and technology Evolutionary computation Knapsack problem Genetic algorithm 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Metaheuristic |
| Zdroj: | CEC |
| DOI: | 10.1109/cec.2018.8477853 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|