Random idea, but here (Italy) it is common enough for hunters to have dogs fitted with a GPS locator when they go in the woods hunting, those are often costly, but there are simpler/cheaper versions intended for use where there is good coverage of cellular networks.

I wonder why - since this service is so innovating/high tech - they don't simply provide their pet walkers with a number of such devices, I believe they cost (at end-user level) in the 50-80 Euro range, maybe 100 for more professional versions.