Solving the uncapacitated single allocation p-hub Median problem on GPU

DOI10.1007/978-3-319-95104-1_2zbMATH Open1444.90096OpenAlexW2609586893MaRDI QIDQ5111122FDOQ5111122

Authors: Abdelhamid Benaini, A. Berrajaa, Jaouad Boukachour 

Publication date: 26 May 2020

Published in: Bioinspired Heuristics for Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1704.06258

Recommendations

• Two genetic algorithms for solving the uncapacitated single allocation \(p\)-hub median problem
• An efficient genetic algorithm for the uncapacitated multiple allocation \(p\)-hub median problem
• SOLVING THE UNCAPACITATED MULTIPLE ALLOCATION p-HUB CENTER PROBLEM BY GENETIC ALGORITHM
• Solving the uncapacitated hub location problem using genetic algorithms
• An efficient genetic algorithm for the uncapacitated \(r\)-allocation \(p\)-hub maximal covering problem

zbMATH Keywords

genetic algorithmsingle allocation p-hub median problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• A 2-phase algorithm for solving the single allocation \(p\)-hub center problem
• A branch and cut algorithm for hub location problems with single assignment
• A general variable neighborhood search for solving the uncapacitated single allocation \(p\)-hub median problem
• A genetic algorithm for the uncapacitated single allocation planar hub location problem
• A hybrid heuristic for the uncapacitated hub location problem
• A quadratic integer program for the location of interacting hub facilities
• Efficient algorithms for the uncapacitated single allocation p-hub median problem
• Efficient solution procedure and reduced size formulations for \(p\)-hub location problems
• Exact and heuristic algorithms for the uncapacitated multiple allocation \(p\)-hub median problem
• GPU Computing for Parallel Local Search Metaheuristic Algorithms
• Genetic algorithm for solving uncapacitated multiple allocation hub location problem
• Hub arc location problems: I. Introduction and results
• Integer programming formulations of discrete hub location problems
• Lower bounding procedures for the single allocation hub location problem
• Memetic algorithm for solving the multilevel uncapacitated facility location problem
• New simple and efficient heuristics for the uncapacitated single allocation hub location problem
• Solving the uncapacitated hub location problem using genetic algorithms
• Stochastic uncapacitated hub location
• The topology optimization design for cracked structures

Cited In (1)

• Adaptive large neighborhood search on the graphics processing unit

This page was built for publication: Solving the uncapacitated single allocation p-hub Median problem on GPU

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111122)