A Self-adaptive Hybrid Search Technique with Its Application to the Quadratic Semi-assignment and Berth Allocation Problems

Both the quadratic semi-assignment problem and the berth allocation problem are about assigning items (vessels) to sets (berths) and have various applications from floor layout planning to schedule synchronization in public transit networks and maritime logistics. In this paper, a hybrid, modular solution strategy, in which an adaptive improvement technique is embedded into a genetic algorithm, is proposed and has been applied to both problems. For the purpose of self-adaptivity, all important parameters of the procedure are embedded in the employed genomes and evolve while the procedure is executed. In addition to the hybrid strategy, a simple branch and bound brute force method is implemented to find the optimal solution for small instances. Computational experiments show that the presented procedure finds the optimal solution for randomly generated 20 x 5 instances in less than a millisecond. These instances are the largest QSAP instances for which we could find optimal solutions within several hours' time.

Automated summary

This paper proposes a hybrid, modular solution strategy that embeds an adaptive improvement technique into a genetic algorithm and applies it to both the quadratic semi-assignment problem and the berth allocation problem. By embedding important parameters in the employed genomes, the strategy achieves self-adaptivity. Computational experiments demonstrate that the presented procedure can find optimal solutions in most cases and can find them very quickly for small instances.