Efficient Benders decomposition algorithms for the robust multiple allocation incomplete hub location problem with service time requirements

Many transportation systems for routing flows between several origin-destination pairs of demand nodes have been widely designed as hub-and-spoke networks. To improve the provided service level of these networks, service time requirements are here considered during modeling, giving rise to a multiple allocation incomplete hub location problem with service time requirements. The problem consists of designing a hub and spoke network by locating hubs, establishing inter-hub arcs, and routing origin-destination demand flows at minimal cost while meeting some service time requirements. As travel times are usually uncertain for most real cases, the problem is approached via a binary linear programming robust optimization model, which is solved by two specialized Benders decomposition algorithms. The devised Benders decomposition framework outperforms a general purpose optimization solver on solving benchmark instances of the hub location literature. The achieved results also show how the probability of violating the travel time requirements decreases with the prescribed protection level, at the expense of the higher costs of the optimal solution for the robust optimization model.