NSGAII for Travelling Thief Problem with Dropping Rate
Rani Kumari, Kamal Kumar Srivastava · 2023
Most of the real life optimization problems often involve simpler problems which may be interwoven together. One such problem introduced recently is the travelling thief problem (TTP) which combines the classical Travelling salesman problem and the knapsack problem. This paper addresses one of the variants of TTP namely TTP2 which has not been studied so far. In TTP2 a thief has to visit a number of cities exactly once. Each of these cities have certain items with some profit and weight associated to each of the items. The thief has to pick items from the cities, while satisfying knapsack capacity constraint. Further, with the increase in the weight of knapsack, the velocity of thief reduces while profit associated with an item decreases by a factor (dropping rate) which depends on its duration in the knapsack. The objective of the thief is to minimize total time while total profit of the item is to be maximized. This research study has designed and implemented a population based evolutionary algorithm, NSGAII to tackle TTP2. Further, this research study proposes three construction heuristics and problem specific crossover and mutation operators for NSGAII. Experiments are conducted on a test set containing 20 benchmark instances to test the performance of the metaheuristic even though competitive testing is not done as no previous work for TTP2 is available in the literature.