Issue |
RAIRO-Oper. Res.
Volume 59, Number 1, January-February 2025
|
|
---|---|---|
Page(s) | 163 - 191 | |
DOI | https://doi.org/10.1051/ro/2024116 | |
Published online | 16 January 2025 |
Round-trip hub location problem
1
Laboratoire d’informatique d’Oran (LIO), Université Oran 1, BP 1524 EL Mnaouer Oran, Algeria
2
Département Réseaux et Télécommunications, Université d’Artois, F-62400 Béthune, France
* Corresponding author: Omke1941@hotmail.com; kemmar.omar@edu.univ-oran1.dz
Received:
6
March
2022
Accepted:
22
May
2024
In this paper, we introduce a novel network design for the Hub Location Problem, inspired by the round-trip structure commonly used by transport service providers. Our design integrates spoke nodes assigned to a central hub node, creating round-trips where the hub node serves as the starting point, visits all assigned spoke nodes, and returns to the hub. To enhance transportation services and provide additional redundancy, we introduce a new type of nodes called runaway nodes to the network. The motivation for this research arises from two real-life cases encountered during consultancy projects, underscoring the necessity for an optimized network design in transportation services. To address the proposed problem, we introduce a mixed-integer linear programming (MIP) mathematical model. However, due to the problem’s complexity, the feasibility of the MIP model is limited to small-scale instances. To tackle medium and large-scale instances, we introduce two hyper-heuristic approaches based on reinforcement learning. These hyper-heuristic approaches harness the power of reinforcement learning to guide the selection of low-level heuristics and improve solution quality. We conduct extensive computational experiments to evaluate the efficiency and effectiveness of the proposed approaches. The results of our experiments affirm the efficiency of the proposed hyper-heuristic approaches, showcasing their ability to discover high-quality solutions for the Hub Location Problem.
Mathematics Subject Classification: 68T20 / 90C59 / 90C27 / 90B80 / 90C35 / 90C05 / 90C11
Key words: Hub location problem / liner shipping / runaway node / branch-and-cut / hyper-heuristic / reinforcement learning / Q-learning / A-learning
© The authors. Published by EDP Sciences, ROADEF, SMAI 2025
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.