Re: Yes! Someone's remembered TrackMeNot
>Need to do a bit more work on it to cycle between random locations anywhere in the world
No .. that just gives the game away.
Take a look at the Firefox (possibly Chromium family as well) addon/extension 'Location Guard' - you want a more sophisticated (mobile) version of that.
You want to be able to pick a set of likely fixed locations somewhere, a set of routes between each and, to an ever so slightly randomised schedule, move between them as if you were leaving home to go to work, underway in the car/train, disappear for the length of a tube/metro journey, reappear again at the right spot, whatever your journey type is.
If it can grab live updates on traffic/transport and make yourself appear to be stuck in traffic/inconvenienced by a cancelled train/whatever, so much the better.
Weekends, you could go to appropriate places - to see family, take the kids to some activity, whatever fits your lifestyle or the lifestyle you wish to present as yours.
So, you could pretend you lived and worked in Rome and simply relocate yourself according to your daily schedule and transport/traffic conditions Monday to Friday.
Weekends, you could drop your twelve-year-old daughter off for her ballet lesson at 9am on Saturday morning, trundle around the market stalls shopping, go to your favourite cafe for an hour, collect her at noon, go to the swimming baths until 4pm, go home, stay home.
Once a month, you might take a trip to Milan to visit the grandparents - it's up to you how sophisticated you want it to be but, obviously, the more you work on your cover story, the more realistic your movements will be. A bit of randomisation (perhaps you visit the shops in a different order each/some time/s, don't always visit some of them) will add to the realism.
Basically, it's a fake diary/calendar app that interacts with your GPS reporting to the system.
Okay, so, so far so fun but probably overkill for anyone not actually leading a double life.
But random locations isn't really a good idea unless they're plausible - so a series within a locality for instance, or still plausible if far apart (you don't go from Rome to Milan and back in an hour three times on the same day).
If all you want to do is obfuscate then a fixed location is sufficient: if you're going for multiple locations then you're telling a story - in which case it had better be believable otherwise you'll just end up drawing attention to yourself, which defeats the object of the exercise.
Now for the bad news.
A mobile device that isn't mobile gives the game away and anyone interested in tracking you will immediately look for alternative methods - and if they're someone you genuinely need to be concerned about they're probably already able to dispense with your fake GPS coordinates as a means to locate you anyway.
Also, no matter how sophisticated the story you tell, much, if not most, location tracking isn't done by GPS but by phone mast and/or WiFi connection - it doesn't matter what GPS coordinates your report to the system, any app with permission can locate you in the real world by communicating with the phone network or querying your IP; and anyone trying to track you can do the same, if they've got the kind of access necessary for you to need to worry about them in the first place. Incoming/Outgoing call records will give the game away as will your phone notifying the nearest mast/tower/whatever that it's switched to its stronger signal as you travel around.
So, state actors aren't going to be fooled no matter what you do and parents or a spouse spying on you will have managed to plant something on your phone that you need to be fooling with a story, not a fixed/random location/s or they'll get suspicious - which, depending upon why they're spying on you, could be even more dangerous than their knowing your real whereabouts.
So, bearing that all in mind, have fun making it and I'll be interested to hear how you do - if it works well enough, I might even be interested in using it myself.
But rest assured that random locations aren't the answer - fixed and/or 'story mode' are what you want to look at.