Capacitated Single Allocation P-Hub Covering Problem in Multi-modal Network Using Tabu Search


1 Institute for Operations Research, Karlsruhe Institute of Technology (KIT),

2 Industrial Engineering, University of Bojnord

3 Industrial Engineering, Shahed University


The goals of hub location problems are finding the location of hub facilities and determining the allocation of non-hub nodes to these located hubs. In this work, we discuss the multi-modal single allocation capacitated p-hub covering problem over fully interconnected hub networks. Therefore, we provide a formulation to this end. The purpose of our model is to find the location of hubs and the hub links between them at a selected combination of modes for each origin-destination. Furthermore, it determines the allocation of non-hub nodes to the located hubs at the best mode for each allocation such that the travel time between any origin–destination pair is not greater than a given time bound. In addition, the capacity of hub nodes is considered. Six valid inequalities are presented to tight the linear programming lower bound. We present a heuristic based on tabu search algorithm and test the performance of it on the Australian Post (AP) data set.