Start with the simplestIt is hard to picture an optimal roue that will not start by minimizing distance through real space. I will start with that fairly simple cost function, then look at fuel and delta-v profiles.
The problem of scaleMost of the graph problems I have dealt with so far have head a few dozen nodes, and so are susceptible to exhaustive depth first. With thousands of nodes, rapidly expanding to tens of thousands, that goes out the window. Not only do we have too many nodes for that, but they live in a database and should not be schlepped into memory without a good reasons. That means I am going to have to use some very directed heuristic like A* or something that takes more direct advantage of the nature of the map.
This should make for interesting problems in Object Relational Mapping, since convention database problems simply do not work this way.