This problem has always fascinated me, but it leaves out very practical considerations. The simple fact is that some stops/customers demand higher priority than others, so the shortest distance isn't the right criterion for determining the route, but the customer demand.
Since shortest distance is so tough, how about dumping a sort of subjective criterion of "priority" into the question?