This paper introduces a new modeling approach that defines service availability measures and finds optimal locations on existing networks that are vulnerable to disruption. In a number of applications, provision of service mainly depends on the capacity of the network components to allow service delivery, ie to establish connectivity between facilities and customers. Service availability is measured as the capability of the network to establish connectivity so that service may be delivered. Examples are the location of emergency response facilities to intentional or natural disasters, servers on computer networks, critical information on social networks, or supply centers on supply chain networks. This paper focuses on the location of facilities on existing tree networks so that service availability to the customers is maximized, allowing the decision makers to consider the average and the worst performance of the network. An efficient algorithm for finding the non-dominated solution set is presented.