An example method involves for a first virtual private network (VPN) installed on a candidate hub router, selecting a first spoke-to-hub assignment solution having a first least memory utilization cost to assign the candidate hub router a quantity of first virtual private edge (VPE) routers serving the first VPN; for a second VPN installed on the candidate hub router, selecting a second spoke-to-hub assignment solution having a second least memory utilization cost to assign the candidate hub router a quantity of second VPE routers serving the second VPN; determining third least memory utilization costs to assign the candidate hub router to a quantity of the first VPE routers, and fourth least memory utilization costs to assign the candidate hub router to a quantity of the second VPE routers; and selecting the first or second spoke-to-hub assignment solution for the candidate hub router based on the least memory utilization costs.