Heuristics for the capacitated modular hub location problem. (October 2017)

• Record Type: Journal Article
• Authors: Hoff, Arild; Peiró, Juanjo; Corberán, Ángel; Martí, Rafael
• Is Part Of: Computers & operations research. Volume 86(2017)
• Page Start: 94
• Page End: 109
• Publication Date: 2017-10
• Subjects: Hub location -- Modular links -- Heuristic algorithms -- Memory structures; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.05.004
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We have studied a hub location problem in which the capacity of the edges between hubs is increased in a modular way. Heuristic methods producing high-quality solutions in short computing times are proposed. A comparison among the proposed methods and existing heuristics on a set of benchmark instances is provided. Abstract: In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a modular way, as a factor of the number of flights. We propose heuristic methods to obtain high-quality solutions in short computing times. Specifically, we implement memory structures to create advanced search methods and compare them with previous heuristics on a set of benchmark instances. Memory structures have been widely implemented in the context of the tabu search methodology, usually embedded in local search algorithms. In this paper we explore an alternative design in which the constructive method is enhanced with frequency information and the local search is coupled with a path relinking post-processing. Statistical tests confirm the superiority of our proposal with respect to previous developments.