This paper deals with the problem of deploying a PowerLine Communication (PLC) network over a medium voltage (MV) power grid. The PLC network is used to connect the end nodes (ENs) of the MV grid to the service provider by means of PLC network nodes enabled as access points. In particular, a network planning problem is faced wherein we require to define the PLC network topology by deciding which MV network nodes are to be enabled as access points. An optimization problem is then formulated, which minimizes the cost of enabling the access points and maximizes the reliability of PLC network paths in a multi-objective optimization fashion. This work also considers resiliency (i.e., it guarantees the PLC network connectivity even in case of link faults) and capacity constraints (i.e., it checks that there are enough resources to transmit the estimated amount of traffic over the PLC network paths). As a byproduct, the optimization algorithm also returns the optimal routing. Simulations based on realistic MV network topologies validate the proposed approach. © 2010-2012 IEEE.