I want to include google maps API into my ASP.NET page and allow users to input the locations (few places) they are going to visit.
When the user inputs the location, the google maps API will mark these locations, it means in the maps it will shows bubbles on the marked places.
After that, my application needs to know all the location information (eg, distances and the coordinates).
I want to use Travelling Salesman Problem (TSP) algorithm to figure out the shortest path and then list out the sequence of the places .
For example:
city A
city C
city B
city D.
When it gets the sequence f these city, I want google maps to link all these cities.
Anyone know how to do this ? Can help me ? I'm new to asp.net and C# .I will be using C# to write code behind for TSP solver. Anyone can help me ? you are welcome to give me any idea on how to implement this or you can just tell how to get the google maps API integrated to my ASP.NET. I don't understand how google maps API really works.
Any related information I'm willing to know.
Waiting for reply . thank you very much.
Google maps API compute shortest path using TSP
Page 1 of 110 Replies  6588 Views  Last Post: 25 July 2013  11:33 AM
Replies To: Google maps API compute shortest path using TSP
#2
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  03:03 AM
Quote
I'm new to asp.net and C# .I will be using C# to write code behind for TSP solver
Wait. Hold on. you are new at C# and yet you want to tackle this problem.
Don't take this as offence, but i think you should start with something little less complicated.
First, do you know what Travelling salesman problem is?
#3
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  03:12 AM
HeldKarp is the most efficient algorithm. It starts by evaluating the vertices, selecting the one whose two lowest cost edges have the smallest sum. Those are the basis of the spanning tree. A Prim MST is then created on the graph, limiting vertex degrees to 2 on the tree. Finally, the circuit is closed on the two remaining vertices of degree 1.
As for the Google Maps API, have you checked the docs?
As for the Google Maps API, have you checked the docs?
#4
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  03:27 AM
Michael26, on 25 July 2013  03:03 AM, said:
First, do you know what Travelling salesman problem is?
hi, thanks for your info. yes. i have learned TSP before using C language.
Now i decided to use c# simply because i want to include google maps into my asp.net page. and i would like to figure out the shortest path between those city. After that i want to come out with the sequence of city. May i know is it possible to be done? i'm now doing research on google api.
#5
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  03:37 AM
If you've studied the TSP, you should know the answer to that. It's an NPHard problem. You can brute force it for only a few vertices. HeldKarp scales better but it is still O(2^n *n^2).
#6
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  03:55 AM
Do you have a specific starting city and ending city? In TSP they are the same. If they are different, then A* is a better algorithm to use though it seems overkill for a 4 city problem (as does a full TSP solution). What's the maximum number of cities?
#7
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  09:55 AM
starting city and ending city are different. TSP can select which 1 to be the ending node right? not necessary to be the same? my maximum cities will be 45 cities.
this is the link about google maps API
https://developers.g...ion/directions/
in this, there is one part it talks about " USING WAYPOINTS IN ROUTES."
it said:
"By default, the Directions service calculates a route through the provided waypoints in their given order. Optionally, you may pass optimize:true as the first argument within thewaypoints parameter to allow the Directions service to optimize the provided route by rearranging the waypoints in a more efficient order. (This optimization is an application of the Travelling Salesman Problem.) "
Does it means when we insert "optimize:true" then it will automatically generate a sequence of waypoints that we have inserted? OR i have to write the TSP solver myself to accomplish the result i want?
if yes, how to do it?
We can decide which algorithm to use as you mention A*? How we are going to write it in order to make it works?
Waiting for reply. Hope you can assist me to solve this problem.
this is the link about google maps API
https://developers.g...ion/directions/
in this, there is one part it talks about " USING WAYPOINTS IN ROUTES."
it said:
"By default, the Directions service calculates a route through the provided waypoints in their given order. Optionally, you may pass optimize:true as the first argument within thewaypoints parameter to allow the Directions service to optimize the provided route by rearranging the waypoints in a more efficient order. (This optimization is an application of the Travelling Salesman Problem.) "
Does it means when we insert "optimize:true" then it will automatically generate a sequence of waypoints that we have inserted? OR i have to write the TSP solver myself to accomplish the result i want?
if yes, how to do it?
We can decide which algorithm to use as you mention A*? How we are going to write it in order to make it works?
Waiting for reply. Hope you can assist me to solve this problem.
#8
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  10:23 AM
"Route optimization. Have many places to go but no preference as to the order you visit them in? We can now reorder the waypoints of your route to minimize the distance and time you must travel. Very useful for traveling salesman I hear."
http://googlegeodeve...travelon.html
http://googlegeodeve...travelon.html
#9
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  10:46 AM
The TSP is for finding optimal Hamiltonian circuits, which implies that the starting and ending points are the same. It sounds like you are dealing with path finding, which is different. Serious question though are you actually investing time and effort into studying the relevant graph algorithms or are you waiting for someone to write this code for you?
#10
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  11:20 AM
I seriously want to study this graph algorithm and write this code by myself. Yes, i want to do something related to path finding which can actually plan the path for travelers to visit those cities.
I found some information from internet which we can actually write some code to work with Google maps. (such as dijkstra algorithm to find shortest path.)
I never thought that Google maps API has such features called "Route Optimization", until i found the link i posted. Therefore, i am wondering is the "Route Optimization" already implement TSP and i just have to learn how to implement it and integrate to my ASP.NET project instead of writing the code by myself.
Thanks in advance and please forgive my poor English.
I found some information from internet which we can actually write some code to work with Google maps. (such as dijkstra algorithm to find shortest path.)
I never thought that Google maps API has such features called "Route Optimization", until i found the link i posted. Therefore, i am wondering is the "Route Optimization" already implement TSP and i just have to learn how to implement it and integrate to my ASP.NET project instead of writing the code by myself.
Thanks in advance and please forgive my poor English.
#11
Re: Google maps API compute shortest path using TSP
Posted 25 July 2013  11:33 AM
Quote
Therefore, i am wondering is the "Route Optimization" already implement TSP
The Traveling Salesman Problem is a circuit problem, not a pathfinding problem. Finding the optimal path is O(V log(E)), while finding the optimal Hamiltonian Circuit (the TSP solution) is O(2^{n} n^{2}).
Page 1 of 1
