An efficient Genetic Algorithm for the Uncapacitated r-allocation p-hub Maximal Covering Problem

  • Olivera Janković teaching assistant at Faculty of Economics, University of Kragujevac

Abstract

This paper deals with the Uncapacitated r-allocation p-hub Maximal Covering Problem (UrApHMCP) with binary coverage criterion. This problem consists of choosing p-hub locations from a set of nodes so as to maximize the total demand covered under the r-allocation strategy. The general assumption is that transportation between non-hub nodes is possible only via hub nodes, while each non-hub node is assigned to at most r hubs. An integer linear programming formulation of the UrApHMCP is presented and tested within the framework of commercial CPLEX solver. In order to solve the problem on large-scale hub instances that cannot be handled by CPLEX, a Genetic Algorithm (GA) is proposed. The results of computational experiments on standard p-hub benchmark instances with up to 200 nodes demonstrate efficiency and effectiveness of the proposed GA method.

Published
2018-06-05
How to Cite
JANKOVIĆ, Olivera. An efficient Genetic Algorithm for the Uncapacitated r-allocation p-hub Maximal Covering Problem. Yugoslav Journal of Operations Research, [S.l.], v. 28, n. 2, p. 201–218, june 2018. ISSN 2334-6043. Available at: <https://yujor.fon.bg.ac.rs/index.php/yujor/article/view/105>. Date accessed: 03 apr. 2025.
Citation Formats
Issue
Vol 28 No 2 (2018)
Section
Articles
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.