Love Maps Updates - Pointers on Optimization Options?

james_richards

I'm thrilled about the stuff I'm seeing in the tool and learning through the video tutorials since having my major set of clients upgrading to 9.0. We are not deployed yet, but it's been mostly self inflicted pain lol. So kudos to the AIM team for great work.

I have an application where I've used another api to create optimized routing for deliveries that is entirely based on driving distance. It doesn't take into consideration that the highway at 2pm is a great route and that that same highway at 3pm is a parking lot. It also can't deal with the fact that at 12:30pm this sales person has to meet a new client at a specific address.

Any pointers on how to achieve this as I see a way in the new "closest points" to make these decisions in real time, but my approach to overall route optimization needs more work.

triss

Having spent most of my life in the transportation business, I can tell you this is a non-trivial problem. Do a Google search on “traveling salesman problem algorithm” and you will find a treasure trove of approaches. Go for a “good enough” solution, as attempting perfection here is a computational nightmare that will ultimately buy you very little.

As to the appointment at 12:30 part of your question, every fixed appointment will divide your TSP into two TSPs on either side of the fixed appointment. It is generally best to also bifurcate your geography around this point (east/west or north/south or some polar grouping).

If you want to go for the least time, then define “shortest” in your TSP algorithm as the time between nodes and not distance. Since time is dynamic due to traffic, this will require reoptimization after every stop. GPS nav systems that attempt to do this in real time are notoriously bad at it, and tend to redirect the user between routes in ways that often become suboptimal.

Good luck with it.

Tom

BLOMASKY

I can not go into a lot of detail on my app, (Signed an NDA), but I have spent over a year in optimizing transporting handicapped kids to school. What makes this "interesting" is that I can start with any home, but have to end up at the school. Determining which location to start at is "fun". Also there are both time and capacity limitations which might require more than 1 vehicle. The "Traveling Salesperson" is easy to solve if there are very few stops. (3-5). but it gets exponentially harder (longer) as you add more nodes.

Determining the "outliers" (Stops with no nearby neighbors) can help optimizing the logic and knowing what angle the vehicle is traveling vs. the angle to the final destination (the school) can also be used to optimize.

What we do is unique, by computing the optimal routing EACH day, since on different days different students are attending school. A lot of the logic is in SQL Server stored procedures. An average day, with 300 students going to 90 different schools, takes about 1 minute to compute the routing. (Of course, the routing is only 1/2 of the problem. Now comes reusability. After dropping off the kids at the first school, can the same driver / van pick up kids for a different school.

Good luck, this will keep your brain working for a while. I found that I had to use a "peel the onion" approach. Start with simple rules, get that working then add additional logic.
Bruce