Here’s what I’m working on: I want to build routes that maximize my custom metrics. I don’t want to share the exact details of these metrics, but for every candidate route I calculate N metrics and I’m looking for the route that performs best across all of them.
Under the hood, I use routing engines (Valhalla / GraphHopper / OSRM) on top of OpenStreetMap to build actual paths from A to B. However, it seems too complex to integrate my metrics directly into the routing engine (it would require rewriting a lot of core logic).
So instead, I built a solution using a graph from OSM + Simulated Annealing + routing:
I start with a random initial route and ask the routing engine to construct a valid path.
Then I run N iterations of Simulated Annealing, with two mutation types:
- Mutation 1: Choose a random sub-route (up to 50% of the route at first), find its midpoint, create a perpendicular, and select a nearby vertex in the graph as a detour point. Then remove the sub-route and reconnect using the routing engine through that detour. Conceptually: “Let’s try this road instead of the current one.” Usually this makes the route longer (which can be fine if metrics improve).
- Mutation 2: Choose a random sub-route, remove it entirely, and reconnect its start and end directly with the routing engine. Conceptually: “Let’s skip this part and just connect the ends.” Usually this shortens the route.
As in standard Simulated Annealing, after each mutation I recalculate metrics and decide whether to accept the change. I repeat this many times, restarting the process as needed.
This kind of works, but the results are poor because most mutations are useless. They tend to make random, odd changes and lead to weird routes.
When I look at examples online (like Simulated Annealing for TSP), mutations are simple: e.g. swap two random vertices. That works because in TSP the graph is fully connected. But in my case, I’m using a real road network graph, so I can’t just “swap nodes” — I need meaningful mutations.
For example: if a route goes from A to B along road C, and there’s a parallel road D, I’d like the mutation to try “use D instead of C.” Right now my approach (random sub-route → random perpendicular → random vertex nearby) is too random and inefficient, giving poor results.
My question: How can I design more effective mutations for this kind of real-road routing problem?
