A method and virtual private network (VPN) system for providing bandwidth guaranteed provisioning in network-based mobile VPN services. The method and system include identifying a set of VPN customers, at least one mobile access point (MAP) and at least one customer premise equipment (CPE) associated with each VPN customer, and at least one Internet Protocol (IP) service gateway (IPSG) for facilitating VPN tunneling between a MAP and a CPE, wherein each MAP is geographically remote from each IPSG. A subset of IPSGs is selected to maximize total profit resulting from provisioning a subset of VPN customers on the selected IPSGs. Total profit from all the customers includes the sum of profits from each customer, where for each customer, the customer profit equals weighted revenue less cost, wherein the cost per customer includes a total tunnel bandwidth cost from the MAP to the CPE, and a cost of provisioning an IPSG node.