Hub location problem in round-trip service applications

¹ Laboratoire d’informatique d’Oran (LIO), Université Oran 1, BP 1524 EL Mnaouer Oran, Algeria
² Département Réseaux et Télécommunications, Université d’Artois, F-62400 Béthune, France

^* Corresponding author: Omke1941@hotmail.com, omke1993@gmail.com

Received: 31 January 2020
Accepted: 31 October 2020

Abstract

In this paper, we introduce a new hub-and-spoke structure for service networks based on round-trips as practiced by some transport service providers. This problem is a variant of Uncapacitated Hub Location Problem wherein the spoke nodes allocated to a hub node form round-trips (cycles) starting from and ending to the hub node. This problem is motivated by two real-life practices in logistics wherein runaway nodes and runaway connections with their associated economies of scale were foreseen to increase redundancy in the network. We propose a mixed integer linear programming mathematical model with exponential number of constraints. In addition to the separation routines for separating from among exponential constraints, we propose a hyper-heuristic based on reinforcement learning and its comparable counterpart as a variable neighborhood search. Our extensive computational experiments confirm efficiency of the proposed approaches.