Greedy heuristics for the Travelling Thief Problem

摘要

Given a set of cities, each containing several items, or objects, with a specific profit and weight associated with each object, the Travelling Thief Problem (TTP) requires a thief with a knapsack of some finite capacity to tour all of these cities, visiting each city exactly once and possibly picking up some items there, and returning finally to the starting city. The knapsack carried by the thief has a renting rate associated with it, and the speed with which the thief travels depends on the total weight of the objects present in the knapsack; for instance, a heavier knapsack would increase tour time and also the rent of the knapsack. The objective of the TTP is to ensure that the total profit accrued in the knapsack ??? less the rent ??? is maximized, while also ensuring that the knapsack capacity is not exceeded. The TTP is essentially composed of two sub-problems, the Travelling Salesman Problem (TSP) and the Knapsack Problem (KP), both of which have been extensively studied in the literature. However, the interdependence of the two problems as formulated in the TTP makes it quite hard to solve. This paper proposes two greedy heuristics for the TTP that consistently outperform a well known recent heuristic both in terms solution quality and computation time. The performance of all the heuristics is compared on a wide range of TTP benchmark instances.