Comparison of Heuristics for Packing While Travelling Problem with Dropping Rate

Many real-life optimization problems consist of multiple well known problems which are interconnected with each other. A recent example of such a problem is the Travelling Thief Problem (TTP) or Packing While Travelling Problem (PWTP), which combines the classical Travelling Salesman problem and the Knapsack problem. In this paper, heuristics for a variant of PWTP, namely the PWTP with dropping rate (PWTP_DR), are examined. In PWTP_DR, a vehicle with a fixed-capacity container visits several cities exactly once. These cities contain various items that have specific profits and weights assigned to them. The vehicle has to pick up the items from the cities while meeting the container capacity constraint. In the process, the vehicle's speed decreases as the weight of the container increases, while the profit associated with an item drops by a factor called dropping rate, which depends on the duration of the article in the container. The problem is to maximize the total profit while minimizing the tour time. So far, this problem has not received much attention, with the only exception of the well-known NSGAII based metaheuristic (NSGAII_PWTP_DR) that utilizes a construction heuristic to create a population of initial solutions, which then evolves through an iterative process. In this work, three heuristics tailored to the problem are designed, and their various combinations are investigated with an aim to achieve a well-diversified population. Comprehensive experiments supported by statistical tests provide the best combination of heuristics to generate a population of solutions as it yields results that are significantly better than those obtained by the previously proposed NSGAII_PWTP_DR.