Hello,

Triangular inequality holds between 3 points, A, B, C on a planar network. Namely, |AB| + |BC| >= |AC|. If you create the distance network from the euclidean distances of the coordinates of points, every rounding in the distance calculations will probably violate the triangular inequality. it is easy to prove this fact.

There are some simple algorithms to fix the violations on simmetric networks. I think those algorithms will probably work for the asymetric networks as well, with one advantage that you do not need to keep simmetric distance in asymetric networks.

Best regards.

Hello,

The issue of rounding may be the source of your problem.

If it is not, as you have asymmetric distances, you need both AB + BC >= CA

and

CB +BA >= CA, if I understand well.

In both cases, in real life it may happen that triangular inequality does not hold. In these cases, you need to find the shortest path routes between each pair of points and construct the matrix of shortest paths. Use these shortest paths as your distances for your ACVRP, as they satisfy the triangular inequality. 

For example, if CB + BA is not >= CA, instead of using the path CA to return, you will be using the path CB + BA, and the triangle inequality will be satisfied with an equality.

Hope it answers your question!

Vlad

 Dear Iago Augusto,

Thank's for the answer. If triangular inequality do not hold asymmetric distance, can I igonore it in heuristic algorithm (parametric CW saving algorithm) to solve ACVRP?

Dear Baris Kecece,

I'm already searching for algorithm to fix triangular violation in symmetric distance but I got no idea to implement in asymmetric distance cause my lack knowledge.

Dear Vladimir Marianov,

Thank's for the suggestion. I got the idea for the shortest path.