Efficiently solving the thief orienteering problem with a max-min ant colony optimization approach
We tackle the Thief Orienteering Problem (ThOP), an academic multi-component problem that combines two classical combinatorial problems, namely the Knapsack Problem and the Orienteering Problem. In the ThOP, a thief has a time limit to steal items that distributed in a given set of cities. While traveling, the thief collects items by storing them in their knapsack, which in turn reduces the travel speed. The thief has as the objective to maximize the total profit of the stolen items. In this article, we present an approach that combines swarm-intelligence with a randomized packing heuristic. Our solution approach outperforms existing works on almost all the 432 benchmarking instances, with significant improvements.
Code (1)
Tasks
BenchmarkingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
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 …
BenchmarkingCombinatorial OptimizationA Benchmark for Multi-UAV Task Assignment of an Extended Team Orienteering Problem
A benchmark for multi-UAV task assignment is presented in order to evaluate different algorithms. An extended Team Orienteering Problem is modeled for a kind of multi-UAV task assignment problem. Three intelligent algori…
On Solving Close Enough Orienteering Problems with Overlapped Neighborhoods
Close Enough Traveling Salesman Problem (CETSP) is a well-known variant of TSP whereby the agent may complete its mission at any point within a target neighborhood. Heuristics based on overlapped neighborhoods, known as …
global-optimizationTraveling Salesman ProblemExact Approaches for the Travelling Thief Problem
Many evolutionary and constructive heuristic approaches have been introduced in order to solve the Traveling Thief Problem (TTP). However, the accuracy of such approaches is unknown due to their inability to find global …
Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation
The Travelling Thief Problem (TTP) is a challenging combinatorial optimization problem that attracts many scholars. The TTP interconnects two well-known NP-hard problems: the Travelling Salesman Problem (TSP) and the 0-1…
Combinatorial Optimization