Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints
For researchers working on multi-component optimisation problems like the TTP, this work provides improved greedy heuristics for the packing subproblem, though it is an incremental contribution.
The paper introduces new reward functions for greedy heuristics in the packing while travelling problem (PWT), a subproblem of the travelling thief problem, and extends them to a hyper-heuristic framework. Experiments show that the tailored heuristics outperform standard heuristics under both deterministic and stochastic constraints.
The travelling thief problem (TTP) is a well-known multi-component optimisation problem that captures the interdependence between two components: the tour across cities and the packing of items. The packing while travelling problem (PWT) is an NP-hard subproblem of TTP where the packing of items should be optimised for a given fixed tour. In many solvers, the packing component is often addressed using greedy heuristics. Here, the use of suitable greedy functions is essential for the success of greedy algorithms. In this paper, we introduce new reward functions tailored to the PWT and extend them to a hyper-heuristic framework to achieve further advantage. Furthermore, we investigate the chance constrained PWT for greedy approaches and adopt the newly introduced reward functions for stochastic weights. The experimental results clearly demonstrate the benefit of the tailored heuristics over the standard heuristics in both deterministic and stochastic constraints.