A novel approach for solving travelling thief problem using enhanced simulated annealing

Area of Science:

• Operations Research
• Computer Science
• Artificial Intelligence

Background:

• Real-world optimization challenges are increasing due to interdependencies.
• Advanced techniques are crucial for solving complex optimization problems.
• The Traveling Thief Problem (TTP) integrates the NP-Hard 0/1 knapsack and traveling salesman problems.

Purpose of the Study:

• To propose an efficient technique for solving the Traveling Thief Problem (TTP).
• To optimize item selection and city traversal for maximum profit and minimum cost within a time limit.
• To enhance existing TTP solution methodologies.

Main Methods:

• A novel approach rearranging knapsack steps for TTP.
• Random initial picking strategy followed by Lin-Kernighan heuristic for traversal planning.
• Modified simulated annealing to refine traversal by removing detrimental cities.

Main Results:

• The proposed technique demonstrates promising performance compared to state-of-the-art algorithms.
• Outperformed existing methods on small and medium-sized TTP instances.
• Achieved competitive results on larger TTP instances.

Conclusions:

• The developed technique offers an efficient solution for the Traveling Thief Problem.
• The method effectively balances profit maximization and cost minimization in TTP.
• This approach provides a valuable contribution to solving complex combinatorial optimization problems.