I have a scenario which I need to optimize the intermediate route stops, with the start and end points fixed, so that I can visit all the intermediate points on the best possible time/distance. The order of those intermediante points does't matter, I just need to visit them.
Is that possible? I'm kind of a hurry for this answer, because there's a contract that my company want to deal today, and that feature is a requirement to buy the mapsuite components.
The scenario you are describing is the "Traveling Salesman problem". We have a sample in the "How Do I " project, "Traveling Salesman Problem analysis". Please, check this sample out. I think this is going to respond to your needs. If it does not repond exactely to your needs, let us know and we will work on a solution more adapted to your case. Thank you.
Hi Val, the traveling salesman isn't exactly what I need. I checked it out.
In my case, let's suppose I want to go from A to D, passing through B and C.
Sometimes, the path A -> C -> B -> D is shorter than going A -> B -> C -> D (ie, in sequence), maybe because B is nearer from the route end than C. In this case, the route is optimized, because it takes less time than going through the points in sequence. Let's suppose A -> B -> C -> D is 130 miles and A -> C -> B -> D is 100 miles, then A -> C -> B -> D is better.
In other words, I want to start from A going to D, passing through B and C in an order that gives me the shortest route total distance.
I have not had the opportunity to talk to someone of the Routing team but I think that the puristic Traveling Salesman algorithm has not been implemented yet. Instead, we have a more aproximate method which accuracy depends on a factor called iteration. The higher you set the number, the more accurate the result is and the slower it takes. I played around with the "Traveling Salesman Problem" sample and I got pretty accurate using a high number for iterations, less accurate with lower number as you can see in the attached screen shots.
I don't have a date for the release of the real Traveling Salesman Problem but we have that in plan.
Ok Val, I understand your thoughts about the TSP. I know it's really a hard problem, computationally speaking.
Maybe I didn't make myself clear about my explanation.
What I tried to point out is that, in my case, the start and end points are fixed. In the TSP the objective is look for the shortest Hamiltonian cycle. In my case there isn't a Hamiltonian cycle, because there's not a connection between the start and end points. In the TSP the route starts and ends at one specified point (the green pin with a start symbol). In my case, the route starts in one point (route start) and goes to another point (route end) passing through two or more intermediate stops (that's why I call the start and end points fixed). What I'm trying to explain is that the order of the intermediate points order can change if this order yields a shorter path when compared to visiting the intermediate points in sequence, but the order of the start and end points can't change, after all, the last point in my route must be the end point, because I don't want to visit any other city after that.
Editing:
I finally found this approach on the net. In the wesite gebweb.net/optimap/ we can see that working in the "Calculate A-Z Trip" (not a roundtrip like the TSP example). As inputs, you can try San Francisco, CA (A); New York, NY (B); San Diego, CA (C); Washington D.C. (D). We can see that the route intermediate order changes. Instead of going A -> B-> C -> D it goes A -> C -> B -> D.
Ok. I understand that your case is slightly different from the case of our TSP example where the start and end points are the same creating the route as a loop basically. In your case, you have the start and the end points different. I don’t think it would be something too difficult to implement considering what we already have. I passed this issue to a programmer of the routing team so that he can work on a solution for that.
I would like to add as a comment that routing is notoriously difficult as a technology with many different algorithms. Each being more or less adapted depending on the type, size etc of the routable data and the TSP is maybe the most accute problem.
Thank you for your input with your idea. We will work on a solution for you and let you know the results.
Gustavo,
I will send you a solution later.
Johnny
Hi Johnny, that’s really good news.
We need to route up to 100 points, of course, the solution won’t be the best, it just need to be good enough.
We can balance and adjust the precision parameter depending on how many points we have.
Gustavo,
Thanks for your requirements. Please refer to the attached sample based on the updated routing package. You need to download the lasted packages with version 3.1.427.0 or later from helpdesk.thinkgeo.com .
Any question please let me know, Thanks.
Note: We are building the pacakges now, if the APIs used in sample are unavaliable in the downloaded package, please wait about half an hour, and then download it again.
Johnny
1904-TSPSolution.zip (11.6 KB)
Gustavo,
Any issue or question during your evalution please let us know, and we will try our best to help you.
Thanks,
Johnny
Gustavo,
Is all ok now?
Thanks,
Johnny
I let you know that we published the project Traveling Salesman Problem in the Code Community to make everyone aware of the new API where you can have distinct start and end points for calculating optimal route with intermediate points.
code.thinkgeo.com/projects/s...ngsalesman
Finally, I got the chance to implement the algorithm in my real app. It seems to be working nice so far.
I just need to know how the parameter interactions affects the result and the performance.
Also, I have an issue. In my app it’s possible to route among several points, optimized (using the TSP algorithm) or not (in sequence). And I build a complex and detailed route description based on the RouteSegments collection.
When I route the points in sequence I have to call GetRoute for each route point pair and I get a RouteSegments collection for each route path (between a start and a end point), which is great. But when I use the TSP I get just a big RouteSegments collection for the entire route, so that I don’t know in the route description when the route passes by the route points (which in my case are cities) exactly. The result of the algorithm could be a collection of RouteSegments (one for each start and end point pair) as I get when I route the points in sequence via GetRoute .
In my opinion, the ideal would be the GetRoute method be able to route among several points too, so that I don’t need to call it multiple times in a route with more than 2 points, and this method would return a collection of RouteSegments, one for each route between two points in the route points passed. And the GetRouteViaVisitStops would have a similar behavior.
I hope my explanation was clear enough to show my difficulty. How can I approach that?
Gustavo,
As far as I know, you want to get another RouteSegment collection including all the RouteResult between two points following the sequenced stops, right? In that case, I don’t think you need to use GetRoute again, it works with lower performance. The better way is that we can analyse the route result of GetRouteViaStops to find the RouteSegment collection between specified start and end points.
The attached is a sample about it. Please click “Find Route”, and then click “GetRouteCollections” to display RouteSegments marked with Railway style between two stops randomly.
Thanks,
Johnny
TravelingSalesmanProblem.zip (12.8 KB)
Your solution is good Johnny, but I think I need something more precise. The solution based on the box can raise some issues if the city is a little far away from the road segment. It would probably get more route segments than necessary. And it’s difficult to set a good value for the tolerance.
I thought something else, and I need to know if it’s correct.
If I get the closest feature for each route point, and then search for the occurrence of those feature IDs in the RouteSegments collection I can slice it to the various RouteSegments that I want. Is that a correct approach? It’s guaranteed that the ID of the closest feature for each route point will appear in the RouteSegments of the route?
Hi Gustavo,
You got what I’m thinking about. That’s a good idea that getting all the feature ids that are nearest to each route stops, and searching for the occurrence of them in the TSP RouteSegment collection, but one thing should be noted that the feature id for RouteSegment in the route collection are reassembled base on original feature id. Here is the instruction about new feature of RouteSegment:
For instance: Id is "8635::000|002", which means that current RouteSegment is just corresponding to the segment from vertex “0” to vertex “2” of Line Feature “8635”. This is very importance, please don’t use “=” to search the specified feature but use “Contains or BeginWith” for compare between two feature ids.
Thanks,
Johnny
Hi,
I got the idea Johnny. Can you answer just a few questions?
1. t’s guaranteed that the ID of the closest feature for each route point will appear in the RouteSegments of the route? I mean, should I search just for the closest feature from each route point? Or should I look for the occurrence of a set of the closest features? (which wouldn’t be so exact and can lead do some errors).
2. Do just the features close to the route points that get their line shape cut (as 8635::000|002 - if the lineshape has more than 3 vertexes)? The intermediate route segment lines are complete, right?
Thank you,
Gustavo
Hi Gustavo,
Here are the answers:
1. Sure, just as you guessed before, the finding route via Points are calculated by the features that are nearest to the points. So you just need to find the first of closet feature using “featureSource.GetFeaturesNearestTo”.
2. Yes, if the lineShape has more than 3 vertexes, the “8635::000|002” means the it has been cut. Here is one of the scenarios that the lineshape will be spited into several parts:
Shown on the left in figure, the Road A and Road B intersects at vertex 1, which is one of vertexes of both Road A and B. It means the vertex 1 is accessible from both Road A and B, so they can be disassembled into Road A, Road B and Road C like on the right in figure.
I’m sorry that I’m unable to get your words “The intermediate route segment lines are complete, right?”. Can you clarify it?
Thanks,
Johnny
I still have some doubt about the first question:
"It's guaranteed that the ID of the closest feature for each route point will appear in the RouteSegments of the route?".
I thought about an example that shows that it's not always the case. Here's the image:
The route goes from A to C, passing through B.
I'm having some though time parsing the RouteSegments collecton returned by the GetRouteViaVisitStops method the way I need - putting the cities (route points) exactly where they appear in the route description, like:
City A
Road 1 for 10km
Road 2 for 7km
Road 3 for 9km
City B
Road 4 for 40km
Road 4 for 60km
City C
I use the GetRouteViaVisitStops to optimize the route stops, so that I have 4 or more points in my route, that was just one simple example based on the image.
Thank you
Gustavo,
I’m sorry that I didn’t get you clearly. In the picture, you said the red line is the closest to Point B, but the A and B also cross the B, In the GetRouteViaVisiteStops, we also used the featureSource.GetFeatruresNearestTo to find 1 closest feature as the segment that the route need to pass. Just as you showed, the Stop like B is on the segments, it have the same distance “zero” to tree segments, it will return the first segment with lower feature id. So featureSource.GetNearestTo method always return the same one that we find in GetRouteViaVisitStops method.
Can you specify which road in picture is Road 1,2,3,4 and the meaning of the list?
City A
Road 1 for 10km
Road 2 for 7km
Road 3 for 9km
City B
Road 4 for 40km
Road 4 for 60km
City C
I use the GetRouteViaVisitStops to optimize the route stops, so that I have 4 or more points in my route, that was just one simple example based on the image.
Thanks,
Johnny