Scholarlink

<p>This paper proposes the uncapacitated single allocation hub maximal covering problem with fixed costs (USAHMCP), focused on selecting the hubs to be opened and determining the allocation of each non-hub node to a single hub, assuming that the set of selected hubs is restricted by a budget for opening the hubs. Thus, the uncapacitated single allocation <i>p</i>-hub maximal covering problem (USApHMCP), aimed to open a predetermined number of hubs, is a particular case of this problem. This paper proposes a heuristic algorithm based on the General Variable Neighborhood Search (GVNS) metaheuristic, with two variants differing on the greedy allocations criterion. One variant, originally proposed in this paper, uses coverage potential-based allocation; the other variant uses a distance-based allocation strategy, the most used criterion in the literature. Computational experiments carried out using instances from the literature with up to 1000 nodes showed that, when the hub opening cost is higher for nodes with higher demands, USAHMCP tends to open more hubs than USApHMCP; for instances that do not make this distinction, the number of hubs tends to be the same, with possible differences in the set of opened hubs. The coverage potential-based allocation strategy found better solutions than the distance-based allocation strategy. Concerning USApHMCP, for instances with up to 200 nodes, the proposed heuristic obtained good solutions in better runtimes than the benchmarks and updated the best-known solutions for 1000-node URAND instances.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A GVNS algorithm applied to the uncapacitated single allocation hub maximal covering problem with fixed costs

  • 期刊论文

  • 发表日期：

    2026年3月16日

查看全文
  • Fernando Félix Oliveira e Silva,
  • Elisangela Martins de Sá,
  • Sérgio Ricardo de Souza

摘要

This paper proposes the uncapacitated single allocation hub maximal covering problem with fixed costs (USAHMCP), focused on selecting the hubs to be opened and determining the allocation of each non-hub node to a single hub, assuming that the set of selected hubs is restricted by a budget for opening the hubs. Thus, the uncapacitated single allocation p-hub maximal covering problem (USApHMCP), aimed to open a predetermined number of hubs, is a particular case of this problem. This paper proposes a heuristic algorithm based on the General Variable Neighborhood Search (GVNS) metaheuristic, with two variants differing on the greedy allocations criterion. One variant, originally proposed in this paper, uses coverage potential-based allocation; the other variant uses a distance-based allocation strategy, the most used criterion in the literature. Computational experiments carried out using instances from the literature with up to 1000 nodes showed that, when the hub opening cost is higher for nodes with higher demands, USAHMCP tends to open more hubs than USApHMCP; for instances that do not make this distinction, the number of hubs tends to be the same, with possible differences in the set of opened hubs. The coverage potential-based allocation strategy found better solutions than the distance-based allocation strategy. Concerning USApHMCP, for instances with up to 200 nodes, the proposed heuristic obtained good solutions in better runtimes than the benchmarks and updated the best-known solutions for 1000-node URAND instances.