GA inspired heuristic for uncapacitated single allocation hub location problem

Abstract

In this article, the results achieved by applying GA-inspired heuristic on Uncapacitated Single Allocation Hub Location Problem (USAHLP) are discussed. Encoding scheme with two parts is implemented, with appropriate objective functions and modified genetic operators. The article presents several computational tests which have been conducted with ORLIB instances. Procedures described in related work round distance matrix elements to few digits, so rounding error is significant. Due to this fact, we developed exact total enumeration method for solving subproblem with fixed hubs, named Hub Median Single Allocation Problem (HMSAP). Computational tests demonstrate that GA-inspired heuristic reach all best solutions for USAHLP that are previously obtained and verified branch-and-bound method for HMSAP. Proposed heuristic successfully solved some instances that were unsolved before. © Springer-Verlag Berlin Heidelberg 2009.