How to eliminate the cross lines in routing problems?
5 views (last 30 days)
Show older comments
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)
2 Comments
Karim
on 20 Jun 2022
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)
Answers (1)
Krishna
on 31 Dec 2023
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:
- Take a route that has crossings.
- Look at every pair of edges in the route.
- 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.
- If a swap is found that improves the tour, make the swap.
- 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,
Hope this helps.
0 Comments
See Also
Categories
Find more on Linear Algebra in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!