How do I unit test a heuristic algorithm?

Say we have our route finding algorithm:

def myHeuristicTSP(graph):
    /*implementation*/
    return route

Now we want to unit test this:

class TestMyHeuristicTSP:
    def testNullGraphRaiseValueError(self):
        self.assertRaises(ValueError, myHueristicTSP(None))

    def testSimpleTwoNodeGraphReturnsRoute:
        self.assertEquals(expectedResult, myHeuristicTSP(input))

The question is, for a non-heuristic TSP algorithm, we can give a variety of graphs and check that they always return absolutely the shortest route.

But because a heurtistic algorithm, while is still deterministic, is less predictable, are simply meant to understand how the algorithm is meant to be working, and find those edge cases?