I’ll try to keep this short but I gotta explain a few things first for it to make sense.
Bike Tiles
As a hobby, I ride my bike. I like to visit places I haven’t been to and to complete my “map”. What map? It looks like this:
There’s this web app called Veloviewer which, amongst other things, puts this grid on the world and highlights in which parts of the grid you have been before (Assuming you track your workouts).
There’s an itch to complete this map and I often find myself planning tours that visit multiple of these tiles in the shortest way possible. Such a tour might look like this:
(Ignore the GPS glitch)
I also wondered if I could write a program to do that for me.
Details
It’s a Set Travelling Salesman Problem. More on that in this post: Set TSP in jsprit? - #2 by Gregws
As long as the route intersects with the tile, it counts. Even if it’s just an inch.
The Idea
If I could add one virtual node per tile that has edges to all actual nodes in that tile, I could reduce the Set TSP to a regular TSP that would just visit those virtual tile nodes. I could also add virtual nodes along the tile’s border.
My problem is: QueryGraphs don’t seem to support this use case and I can’t modify the graph once it’s loaded. So, how would I go about this? Do I subclass the code that is responsible for loading the graph in the first place? Sounds like a bad idea. Do I create a new Graph and add all the information from the original graph + my new nodes and edges? Or do I implement another specialised QueryGraph that wraps the original Graph and provides the functionality I require? To me the latter sounds like the most promising solution.
Is there a better way? Thanks!