Critical network infrastructures are vulnerable to intentional or unplanned disruptions, which may render some of their components (links and nodes) non-operational leading to deterioration of service due to path destruction and even disconnectedness (no operational paths) between nodes that provide service and nodes that receive it. This paper develops models for improving resilience to disruptions on critical infrastructures such as transportation and supply chain networks through locational decisions, i.e., by finding the best locations of service facilities so that resilience metrics are optimized. Network resilience is measured by the ratio of the delivered amount of service, when network disruption occurs, over the total requested service. Availability of service depends on the capability of the network to establish connectivity between service facilities and customers. Models are presented that consider criticality of service provided and average and worst network performance. Efficient procedures are introduced that avoid intractability of the traditional two-terminal reliability calculations needed to measure connectivity, based on closeness between service facilities and customers, that provide location, coverage and routing decisions.