This problem is a variation of the Travelling Thief Problem (TTP) with multiple agents. The TTP is a combination of Knapsack Problem with Traveling Salesman Problem, which is proved to be NP-Hard. In a nutshell, a group of thieves rented a truck and must do their job in a set of cities, focusing on have the optimal profit from the robbery.
The following procedures were implemented in this work:
- Greedy Randomized Adaptive Search Procedure (GRASP);
- Iterated Local Search (ILS);
- Variable Neighborhood Descent (VND).
The main objective here is to obtain near-optimal solutions for the problem in a reasonable time.
$ g++ main.cpp -O3 -o exec
$ ./execA set of N cities are disposed in a state, with distance d[i][j] between any two cities. Each item k positioned in a city i has value p[i][k] and weight w[i][k].
The global knapsack capacity limits the amount of items and a tax R is paid for each time unit. The velocity v of a thief depends on its carried items.
The multi-objective function is defined as follows:
This problem was one of the most challenging that the team encountered, due to its difficult multi-objetive function, considerably large instances and amount of information. It was very fun to discuss methods to solve this problem, and even funnier to implement them.
Considering the set of instances, results shown that the obtained ones overcome the literature results.
- Gabriel Felix
- Natan Garcias
[1] https://cs.adelaide.edu.au/~optlog/research/ttp/2016gecco-mttp.pdf