Solving Geometric Knapsack Problems using Tabu Search Heuristics

摘要

An instance of the geometric knapsack problem occurs in air lift loading where aset of cargo must be chosen to pack in a given fleet of aircraft. This paper demonstrates a new heuristic to solve this problem in a reasonable amount of time with a higher quality solution then previously reported in literature. We also report a new tabu search heuristic to solve geometric knapsack problems. We then employ our novel heuristics in a Master and slave relationship, where the knapsack heuristic selects a set of cargo and the packing heuristic determines if that set is feasible. The search incorporates learning mechanisms that react to cycles and thus is robust over a large set of problem sizes. The new knapsack and packing heuristics compare favorably with the best reported efforts in the literature. Additionally, we show the JAVA language to be an effective language for implementing the heuristics. The search is then used in a real world problem of determining how much cargo can be packed with a given fleet of aircraft.