Skip to main content

Research Repository

Advanced Search

The capacitated directed cycle hub location and routing problem under congestion

B�t�n, Cihan; Petrovic, Sanja; Muyldermans, Luc

The capacitated directed cycle hub location and routing problem under congestion Thumbnail


Cihan B�t�n

Professor of Operational Research


This paper deals with hub-and-spoke network design in the liner shipping sector. It introduces a capacitated directed cycle hub location and cargo routing problem under congestion. The problem involves four decisions: location of hub ports; allocation of non-hub ports to hub ports; construction of a directed cyclic route at the hub port network level; and the routing of cargo between all origin-destination demand pairs in the network. The objective is to minimize the cost which includes fixed hub opening, feeder collection and distribution, inter-hub transportation, cargo handling, and non-linear hub port congestion costs. We present a mixed integer linear programming model in which the non-linear congestion costs at the hub ports are approximated through a (semi-continuous) piecewise linear function and use this model to calculate lower bounds on the objective function. We also develop a Tabu Search algorithm, which employs a hierarchical approach for the different decisions in the hub-and-spoke network design problem, with customized procedures for the generation of the initial solution and the selection of the search moves. The neighborhood search is diversified by randomly changing the locations of hubs based on their location frequency history in previous solutions. Computational experiments, using instances from the literature and problems based on real-world data, demonstrate that the algorithm finds high quality solutions in a reasonable time. The experiments show that the network design can be highly influenced by scale economies in mainline vs. feeder transportation costs, the port locations and hinterland flows, and congestion at the hub ports.

Journal Article Type Article
Acceptance Date Nov 12, 2020
Online Publication Date Nov 20, 2020
Publication Date Jul 16, 2021
Deposit Date Nov 23, 2020
Publicly Available Date Nov 21, 2022
Journal European Journal of Operational Research
Print ISSN 0377-2217
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 292
Issue 2
Pages 714-734
Keywords Location; Directed cycle hub location and routing problem; Network design under congestion; Tabu Search
Public URL
Publisher URL


You might also like

Downloadable Citations