The Yard Allocation Problem

The Yard Allocation Problem (YAP) is a real-life resource allocation problem faced by the Port of Singapore Authority (PSA). We first show that YAP is NP-Hard. As the problem is NP-Hard, we propose several heuristics, including Tabu Search methods with short and long term memory, a "Squeaky Wheel" Optimization (SWO) method, and a new hybrid which combines SWO with TS to solve the problem. Extensive experiments show very favorable results for our new hybrid method.