P-hub center and routing network design problem and solution algorithms

The p-hub center and routing problem deals with finding the location of hub facilities and allocating the demand nodes to these hub facilities, and forming the routes of the vehicles so as to minimize the maximum distance/time between any origin-destination pair under the assumption that one vehicle is dedicated between each non-hub node and hub node. In this study, we relax this assumption and present a mathematical programming model and combinations of algorithms for solving this challenging problem, namely, the single allocation p-hub center and routing problem. In order to generate initial solutions, we propose random, greedy and efficient mat-heuristic algorithms. Our mat-heuristic algorithm is based on a decomposition scheme in which we divide this hierarchical problem into two parts as the location of the hubs and allocations of non-hub nodes to the hubs; also as the routing part. Furthermore, we combine these initial solution algorithms with Variable Neighborhood Search and Simulated Annealing Algorithms. The algorithms are tested on instances on the Turkish network (TR) and Australia Post (AP) datasets. The results show that our initial solution algorithms combined with the metaheuristic algorithms could provide good solutions for medium and large-size instances within reasonable computing times.