Sub optimal solution on simple probleme about vroom HOT 14 CLOSED

My guess is that it is because your matrix is "quite asymmetric".

The heuristic used to build the initial solution is not expected to be good on asymmetric problems as it targets symmetric (or near symmetric) instances.

For the record, the solutions on ATSP from TSPLIB may be poor for the most asymmetric instances, while being close to optimal for the instances that are "nearly symmetric", like those usually arising in a routing context.

Did your matrix occur in a real-life routing context ?

from vroom.

Yes. It's a sub part of a real example dataset. It's 3 points in a one way street, but vroom doesn't solve the problem in the one way order. It's loop around the block and pass many times in the street.

from vroom.

Ok. This is the most problematic kind of situation regarding the current approach, and it is not satisfying on your example as we cannot afford to raise solutions that are "obviously wrong".

The weak spot here is that the matrix used for most of the computations is actually this one:

0 2750 2795 2737
2750 0 461 493
2795 461 0 448
2737 493 448 0

This is a kind of "worst case" symmetric scenario. Use of a symmetric matrix is mandatory for the chosen heuristic and is not really a problem as long as the orientation doesn't matter too much (e.g. 2609 vs 2750). But in your example, interesting ways (13, 45, 58) that are much shorter are "forgotten".

The work-around would be to go back to the initial asymmetric matrix for the local search phase that aim at improving the initial solution.
The reason this was not done in the first place is that it would require a little more computing, but examples like yours show this might be worth it.

I shall definitely try to give it a go asap.

from vroom.

The above mentioned fix should now make things better for situations like your example.

It does raise computing time issues for bigger instances though, so more adjusting will be required before using it as the default behaviour.

from vroom.

Thank you. With your change it is significantly better.
Is no more obviously wrong on all run.
Nevertheless on some runs on my test data there is still loop around the block.

from vroom.

If you still get strange-looking solutions, the question is to know if it is a poor solution or a satisfying one that feels unnatural (something a human being wouldn't come up with). Feel free to post other examples, the previous one did help to improve things.

Have you noticed a significant change in computing times? (Might depend on the size of problems you are solving).

from vroom.

I build an subpart of my test data to isolate the issue.

NAME: vroom
TYPE: ATSP
DIMENSION: 7
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX
EDGE_WEIGHT_SECTION
0 2549 2538 2625 2571 2629 2759
2530 0 75 162 108 166 295
2835 431 0 86 32 90 220
2865 461 536 0 62 120 250
2802 398 474 560 0 58 187
2744 340 415 502 448 0 129
2615 210 286 372 318 377 0
EOF

The result is :

{"computing_times":{"matrix_loading":0,"route":{"heuristic":0,"local_search":0}},"tour":[1,4,5,7,2,3,6],"solution_cost":5993}

But with the same input data, but in other order, the result is better:

NAME: vroom
TYPE: ATSP
DIMENSION: 7
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX
EDGE_WEIGHT_SECTION
0 2625 2571 2759 2549 2538 2629
2865 0 62 250 461 536 120
2802 560 0 187 398 474 58
2615 372 318 0 210 286 377
2530 162 108 295 0 75 166
2835 86 32 220 431 0 90
2744 502 448 129 340 415 0
EOF

{"computing_times":{"matrix_loading":0,"route":{"heuristic":0,"local_search":0}},"tour":[1,5,6,2,3,7,4],"solution_cost":5574}

from vroom.

I have pushed an experimental adaptation of the approach. I expect it to be better on average on the kind of asymmetric problems occurring in a routing context, without raising the computing times. Any feedback welcome for performance on your datasets.

Nevertheless, it is very difficult to avoid getting "poor" sub-optimal solutions on some specific cases. All the more with the local search approach as it is for now, designed to be very fast.

from vroom.

I do not done stats. But I have the feeling that the result is now more stable (smaller standard deviation) but less close of optimal than previous and less worse result. It's depends on order of input in the matrix.

from vroom.

less close of optimal

On atsp from TSPLIB, version at 95ef1ff is better than previous (470c955) on 8 instances and worse on 10, but is significantly better on average cost. It is also much much faster (between 1.5 and 3 times faster on serious-sized instances).

We need to be careful however as most asymmetric TSPLIB instances are by far "too" asymmetric to be a representative benchmark for a routing context...

less worse result

This is the important point IMO: a little lowering in average quality is definitely acceptable to get a significant improvement for worst-cases solutions.

from vroom.

As for the solution depending on the input order, this is an expected behaviour as the order impacts the way improvements are performed during the local search phase.

from vroom.

The current approach is to find a local minimum very quick, only through solution improvements. It is very fast, but the drawback is that not allowing temporary degradations of the solution quality makes it sometimes impossible to deeply modify the current solution to get to a "simpler" one. This can result in unsatisfactory cases where a better "intuitive" solution exists.

Your specific situation with several places grouped around a neighbourhood with one-way streets needs extra thinking...

from vroom.

The latest additions in branch experiment_avoid_loops should improve pathological cases with loops in one-way streets like those arising in the above examples.

from vroom.

Not directly related to the initial problem, but rather to the question of solution quality dispersion that have been mentioned above: the latest changes in develop (as of commit 3467a6d) should bring a notable improvement in term of smaller standard deviation for solution cost.

from vroom.