Implementation cost for a rollout of SaaS at 20 locations

If you have 20+ locations, this will significantly affect implementation costs due to travel and training, and those costs are highly variable -- so no, there is no general rule of thumb. There's also customization costs and other services that the annual fee may not cover.

I would look at the costs involved in deploying other systems or the costs of other similar projects within your organization to come up with an estimate. You could also ask to speak with reference customers for the vendors you are considering and get their input on projected costs.