How to eliminate the cross lines in routing problems?

In a vehicle routing problem (VRP), I have several points (the coordinates are known and provided as longtitude and latitude) and I DON'T want to see crosslines in my routing result.

For example, the figure below is a part of my routing results, you can see that in route 8-19-25-26-30-27-24-23-29-8, there exist a cross between 25-19 and 24-23, but I don't know how to deal with issue, my ideal routing reslut may like 8-19-24-27-30-26-25-23-29-8, (by simply exchange the 27-25-19, 26-24-23 to 27-24-19, 26-25-23)

[Karim]

Asumming you know the coordinates of all the points, you can evaluate for each line section the intersections.

For instance, on file exchange you can find: Curve intersections - File Exchange - MATLAB Central (mathworks.com)

[Wang Zhen]

Well, I also read the InterX, but my purpose is to avoid intersections not to find them (maybe we first find them and then we try to avoid), the sequence of the routing matters.

Answer 1

[Krishna]

Hey Wang Zhen,

To ensure that your vehicle routing problem (VRP) solution does not contain any crossing lines, you can apply a post-processing step known as route optimization or tour improvement. In the example you provided, you've intuitively found a way to eliminate the crossing by reordering the points.

The process you've described is like what is known as the 2-opt algorithm, a simple yet effective local search method used to improve the quality of a given tour. The basic idea of the 2-opt technique is to take a route that has two edges crossing and reorder it so that it does not cross. Here is the general procedure for the 2-opt algorithm:

1. Take a route that has crossings.
2. Look at every pair of edges in the route.
3. For each pair of edges (i, j) and (k, l), check if swapping them (to become (i, k) and (j, l)) would result in a shorter route and eliminate the crossing.
4. If a swap is found that improves the tour, make the swap.
5. Repeat this process until no further improvements can be found.

Also the the InterX method you're referring to is likely a procedure to detect intersections within a set of paths or routes. The idea is that once you identify these intersections (or crossings), you can then apply techniques to eliminate them, thereby optimizing the route.

You can go through this documentation to know more 2-opt algorithm,

https://en.wikipedia.org/wiki/2-opt#:~:text=The%202%2Dopt%20algorithm%20was,so%20that%20it%20does%20not.

Hope this helps.