All the np-hard routing problems I know are of the form, minimize some quantity while visiting the verticies in an unordered way.Are there problems which are still np-hard, if one has to visit the vertices in a given odering? The only problem I can think of which partially falls into this is the Vehicle routing problem with time windows problem where the time window kind of dictates an order.
Ordered routing problem which is NP-hard
cc.complexity theory;np hardness;tsp