Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
This paper deals with the Uncapacitated r-allocation p-hub Maximal Covering Problem (UrApHMCP) with a 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. | Yugoslav Journal of Operations Research 28 (2018), Number 2, 201–218 DOI: https://doi.org/10.2298/YJOR170120011J AN EFFICIENT GENETIC ALGORITHM FOR THE UNCAPACITATED R-ALLOCATION P-HUB MAXIMAL COVERING PROBLEM ´ Olivera JANKOVIC Faculty of Mathematics, University of Belgrade, Belgrade,Serbia Faculty of Economics, University of Kragujevac, Kragujevac, Serbia jankovic.olivera@gmail.com Received: January 2017 / Accepted: February 2018 Abstract: This paper deals with the Uncapacitated r-allocation p-hub Maximal Covering Problem (UrApHMCP) with a 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 the transportation between the nonhub 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 a commercial CPLEX solver. In order to solve the problem on large scale hub instances that cannot be handled by the 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. Keywords: p-hub Maximal Covering Problem, Binary Coverage, Heuristic, Genetic Algorithm. MSC: 90B80, 90B10, 68T20. 1. INTRODUCTION The hub covering problem is one of the fundamental and most studied problem in facility location theory. It is widely used within the design of supply chains, airline transportation networks, DHL services, postal delivery networks, computer and communication systems, etc. The hub covering problem was first 202 O. Jankovi´c / GA for the UrApHMCP introduced by Campbell [7]. Let N = {1, 2, ., n} be a set of nodes in the network, each of them with a certain demand assigned, and let H ⊂ N be a set of potential hub nodes. The goal of the hub
