1

I'm trying to do a simple route optimization without any fancy frameworks and insert-science-professor-name-here algorithms. I have a startDepot and 100k waypoints of which I want to find about 25 waypoints, which are reasonable to visit in a single route. The accuracy doesn't have to be perfect. Currently I'm searching for the nearest point to the start location, then search the nearest to the first point, then nearest to the previously found point etc, always excluding the previously found points. Now, the algorithm gives quite good results and even produces a reasonable route, but I really would like to include an endDepot also. Sometimes it may match the startDepot, sometimes not. Any ideas of how to find the next point that prefers the direction to the endDepot?

I'm using postgis but the question is more related to algorithm generation

  • Welcome to GIS SE. Plese, edit your question and specify software used and what you have been trying so far – aldo_tapia Feb 8 '18 at 15:21
0

A simple way to modify your current algorithm to "prefer the direction of the endDepot" would be to multiply the distances you are using to choose the next point by a scaling factor determined by the difference between the angle from the current point to the endDepot and the current point to each possible next point. So that if a possible next point is in the wrong direction entirely, it would be count as if it was, for example, twice as far away as it really is, while an another point more in the "right" direction would be only 1.2x as far as it is. Use a little trigonometry to determine the relative directions, and some experimentation to determine the best factor.

Unfortunately, your current greedy algorithm may work sometimes but can fail horribly in others, and this new approach will likely be even worse. If you can accept that this is a very hard problem and is worth standing on the shoulders of giants, have a look at GraphHopper's JSprit library:

https://github.com/graphhopper/jsprit

You feed it your graph and problem description and it selects the best algorithm and finds excellent results in a short time. Here is an example that will do what you want; you would just need to replace the cost matrix with your own (pulled out of postgis I assume), and set the vehicle's endLocation to your endDepot:

https://github.com/graphhopper/jsprit/blob/master/jsprit-examples/src/main/java/com/graphhopper/jsprit/examples/CostMatrixExample.java

  • Cool, thanks, really great idea.. I was Googling for open source solutions for my problem, found GraphHopper/jsprit and google-OR, but I could not figure out which were really free to use when self-hosted and if they would solve my current problem. Can jsprit handle about 200k locations? I'm asking because their paid plan limits the locations up to 10k – Matti Feb 8 '18 at 18:21
  • What are the 100-200k locations you are talking about? you say you are only visiting 25 waypoints - are these 25 defined in the problem or are you just picking the easiest/fastest 25 out of the 100-200k? Because that is a different problem than the typical routing problem, which your greedy algorithm probably does reasonably well at, and I think it could even be made to be optimal with some backtracking. – chodgson Feb 9 '18 at 19:35
0

Probably way too late for you now, but I've used software that does this. It's called TruckStops. You give it all the points that you want to have visited, and a number of "trucks" to do the work, and it loads the trucks up with an initial load algorithm, then optimises. The method it uses for the initial load is the reverse of what you're describing there, it actually picks the furthest point first, and loads that to the first truck, then picks a stop halfway between the first stop and home, then it keeps loading from there (not sure how it does that though). Ultimately it ends up with these loops. Then in the optimisation phase it swaps stops back and forth until it finds a local minimum in its graph.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.