Problem definition: We study the problem of designing large-scale resilient relay logistics hub networks. We propose a model of k-Shortest Path Network Design, which aims to improve a network’s efficiency and resilience through its topological configuration, by locating relay logistics hubs to connect each origin-destination pair with k paths of minimum lengths, weighted by their forecasted demand share. Methodology: We formulate this problem as a path-based mixed-integer program with an exponential number of variables and constraints, and leverage its structure to design two scalable solution approaches based on tailored implementations of Benders decomposition and branch-and-price, respectively. In the first approach, we analytically characterize the optimal dual solutions of the exponential-sized Benders subproblem and generate feedback cuts in pseudo-polynomial time using single- and multiple-shortest path subroutines. In the second approach, we show using complementary slackness that the pricing subproblem employed within branch-and-price can also be solved in pseudo-polynomial time by computing multiple shortest paths in a carefully defined graph. Results: We apply our methodology to design large-scale resilient relay networks for a China-based parcel delivery partner. Our computational experiments demonstrate that our developed approaches can obtain optimal solutions for practically relevant instances. The resulting logistics networks showcase a significant improvement in capabilities to sustain hub disruptions with marginal compromise on nominal efficiency, in comparison with relay networks designed to only optimize nominal efficiency. Managerial implications: This work offers valuable insights for logistics service providers aiming to design resilient relay networks with limited information regarding future demand and disruption risks. Our analysis provides decision-makers with recommendations on adjusting the topology of network designs to achieve a desired tradeoff between nominal efficiency and performance under disruptions.