The p-Cable Trench Problem is a telecommunications network design problem, which jointly considers cable and trench installation costs and addresses the optimal location of p facilities. In this work, a matheuristic approach based on the POPMUSIC (Partial Optimization Metaheuristic under Special Intensification Conditions) framework is developed. The inspected neighborhoods for building sub-problems include lexicographic as well as nearest neighbor measures. Using benchmark data available from literature it is shown that existing results can be outperformed.