Virtual Private LAN Service (VPLS) is commonly used for secure multi-point communication across geographically scattered industrial sites, simulating a unified LAN broadcast domain for Industrial IoT (IIoT)-type devices. This configuration demands a fully-connected overlay network with encrypted Host Identity Protocol (HIP)/IPsec tunnels exhibiting quadratic scalability to the number of tunnels and a significant increase in forwarding table entries. Herein, we introduce Tunnel Relay Nodes (TRNs) as selected routers that maintain full-mesh connectivity. This approach allows non-TRN routers, or Provider Equipment (PEs) acting as spoke PEs, to connect via a TRN. We explore the challenges of using TRNs in secure HIP-based VPLS (HIPLS) networks, including (i) placing reliable TRNs within provider networks and (ii) scheduling TRNs to minimize their activation/deactivation costs as well as the connection cost among PEs. We then demonstrate how (i) can be addressed in polynomial time using a modified general median problem approach. Additionally, we formulate (ii) as a Mixed Integer Linear Programming (MILP) scheduling problem and prove its NP-completeness. Furthermore, we introduce an algorithm based on Lagrangian relaxation to address the intractability in large-scale deployments. This algorithm offers fast, near-optimal solutions while simultaneously balancing solution quality and execution time. Our simulations on three real-world network topologies with real network demands show a 92% average reduction in forwarding table entries on PE. Compared to existing solutions, our method reduces the number of tunnels established by up to 95%, at the expense of a 1.39-fold increase in tunnel path length.