A Self-adaptive Hybrid Search Technique with Its Application to the Quadratic Semi-assignment and Berth Allocation Problems
Publication Name
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Abstract
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 × 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.
Open Access Status
This publication is not available as open access
Volume
13557 LNCS
First Page
16
Last Page
30