The capacitated directed cycle hub location and routing problem under congestion

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.