Local Search Heuristics for the One Dimensional Bin Packing Problems

摘要

This resaerch implements three basic local search heuristics; hill climbing (i.e., random descent), simulated annealing and multi-start simulated annealing. The aim is to investigate the performance of these heuristics compared to the state of art literatures. To achieve this, researchers use a common software interface (the HyFlex framework) that are designed to enable the development, testing and comparison of iterative general-purpose heuristic search algorithms. To evaluate the performance of these heuristics researchers test on one dimensional bin packing instances using simple move operator. The results demonstrated that hill climbing heuristic outperforms other approaches in all tested instances. This indicates that simple local search is more effective in solving one dimensional bin packing problems when the searcher is allowed to run in a short time.