Prefer visiting tsp nodes while leaving the depot vs. returning to the depot.

[singhh23]

I'm running the start_ends example with the data model as below. I haven't changed any other code. The data has 4 repeated locations: 1, 2, 3, 6. The solution that I receive is 0 -> 6 -> 9 -> 7 -> 8 -> 1 -> 2 -> 3 -> 5 -> 4 -> 10. I don't quite understand why the repeated locations wouldn't occur sequentially (6 is visited separately from 1, 2, 3).

    const std::vector<std::vector<int64_t>> distance_matrix{
        {0, 919, 919, 919, 6053, 4354, 919, 3926, 3926, 8859, 0, },
        {919, 0, 0, 0, 6349, 4650, 0, 3007, 3007, 7939, 919, },
        {919, 0, 0, 0, 6349, 4650, 0, 3007, 3007, 7939, 919, },
        {919, 0, 0, 0, 6349, 4650, 0, 3007, 3007, 7939, 919, },
        {6053, 6349, 6349, 6349, 0, 1698, 6349, 9356, 9356, 14289, 6053, },
        {4354, 4650, 4650, 4650, 1698, 0, 4650, 7658, 7658, 12590, 4354, },
        {919, 0, 0, 0, 6349, 4650, 0, 3007, 3007, 7939, 919, },
        {3926, 3007, 3007, 3007, 9356, 7658, 3007, 0, 0, 4932, 3926, },
        {3926, 3007, 3007, 3007, 9356, 7658, 3007, 0, 0, 4932, 3926, },
        {8859, 7939, 7939, 7939, 14289, 12590, 7939, 4932, 4932, 0, 8859, },
        {0, 919, 919, 919, 6053, 4354, 919, 3926, 3926, 8859, 0, },
   };

    const int num_vehicles = 1;

    const std::vector<RoutingIndexManager::NodeIndex> starts{
        RoutingIndexManager::NodeIndex{0},
    };
    const std::vector<RoutingIndexManager::NodeIndex> ends{
        RoutingIndexManager::NodeIndex{10},
    };

[singhh23]

I suppose the issue is that when you're travelling through a location and returning through it in exactly the same way, it doesn't matter whether you complete it on the way there or on the way back. In the image below, you could do 1 -> 3 -> 2 -> 1, or 1 -> 2 -> 3 -> 1 which both have equivalent distance cost.

Is there a way to cause the vehicle to prefer visiting nodes on the way out instead of on the way back?

[Mizux]

IIRC it is a side effect of the heuristic, since when adding node one by one cost(1 -> 2) < cost(1 -> 3) so the solver if using PATH_CHEAPEST_ARC will select 1 -> 2 first...

[singhh23]

Hmm, I suppose it shouldn't matter if you do it on the way out or on the way back.

If node 2 is repeated however, there is some implicit cost in splitting the two up (cost of stopping). In order to account for that simply I added an if(from_node != to_node) { dist += 10; } to simulate that staying at the same node is cheaper than travelling between nodes. Does that seem like a valid approach, or would you recommend I just model it with another dimension/constraint?