WAN Connection

I have 11 remote stores that need to connect to our corporate location full time for application data. I have been looking into Frame Relay but the costs are substantial. I have also looked into a VPN, but the dial up connections might not be sufficient enough. What other options are there??? Any suggestions would be appreciated.