Solving the Uncapacitated Single Allocation p-Hub Median Problem on GPU

April 14, 2017 · The Ethereal · 🏛 Bioinspired Heuristics for Optimization

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Abdelhamid Benaini, Achraf Berrajaa, Jaouad Boukachour, Mustapha Oudani arXiv ID 1704.06258 Category cs.DM: Discrete Mathematics Cross-listed cs.NE Citations 9 Venue Bioinspired Heuristics for Optimization Last Checked 2 months ago

Abstract

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.