Solving the Uncapacitated Single Allocation p-Hub Median Problem on GPU
This work addresses a combinatorial optimization problem in logistics and network design, offering incremental improvements in computational efficiency for researchers and practitioners.
The paper tackles the Uncapacitated Single Allocation p-Hub Median problem by proposing a parallel genetic algorithm implemented on GPU clusters, which outperforms most well-known heuristics in solution quality and execution time, solving instances up to 6000 nodes and outperforming benchmarks on up to 1000 nodes.
A parallel genetic algorithm (GA) implemented on GPU clusters is proposed to solve the Uncapacitated Single Allocation p-Hub Median problem. The GA uses binary and integer encoding and genetic operators adapted to this problem. Our GA is improved by generated initial solution with hubs located at middle nodes. The obtained experimental results are compared with the best known solutions on all benchmarks on instances up to 1000 nodes. Furthermore, we solve our own randomly generated instances up to 6000 nodes. Our approach outperforms most well-known heuristics in terms of solution quality and time execution and it allows hitherto unsolved problems to be solved.