In this paper a network planning problem aiming to enable underground Medium Voltage (MV) power grids to resilient PowerLine Communications (PLCs) is faced. The PLC network is used to connect PLC End Nodes (ENs) located into the secondary substations to the energy management system of the utility by means of PLC network nodes enabled as Access Points. An optimization problem is formulated, aiming to optimally allocate the Access Points to the substations and the repeaters to the MV feeders. A multi-objective optimization approach is used, in order to keep in balance the needs of minimizing the cost of equipment allocation and maximizing the reliability of PLC network paths. Resiliency and capacity constraints are properly modeled, in order to guarantee the communications even under faulted link conditions. As a byproduct, the optimization algorithm also returns the optimal routing. Simulations performed on a realistic underground MV distribution grid validate the proposed approach © 2012 IEEE.