.png){kind=icon}
.png){kind=icon}
Return
An approximation algorithm for multi-allocation hub location problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2025.107118.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The multi allocation p-hub median problem (MApHM), the multi allocation uncapacitated hub location problem (MAuHLP) and the multi allocation p-hub location problem (MApHLP) are common hub location problems with several practical applications. HLPs combine the task of constructing a network and solving a routing on that network. Specifically, a set of hubs must be chosen and each routing must be performed using one or two hubs as stopovers. The costs between two hubs are discounted by a parameter alpha. The objective is to minimize the total transportation cost in the MApHM and additionally to minimize the set-up costs for the hubs in the MAuHLP and MApHLP. In this paper, an approximation algorithm to solve these problems is developed, which improves the approximation bound for MAuHLP to 2.408. The proposed algorithm reduces the HLPs to Facility Location Problems (FLPs), incorporating the idea of preferring hubs in the direction of the destination. Depending on the HLP, different FLP approximation algorithms with approximation bound gamma are used. In cases where the discount factor satisfies 0<1/gamma or alpha >= 0.619, the resulting approximation bound still improves upon the current state of the art. The proposed algorithm is capable of solving much bigger instances than any exact algorithm in the literature. New benchmark instances have been created and published, such that HLP algorithms can be tested and compared on standardized huge instances. There, the proposed algorithm outperformed the previous best approximation algorithm in nearly all test instances.
Keywords:
Hub location problem
Approximation algorithm
Combinatorial optimization
Routing problems
Graph theory
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W