10 Replies - 3550 Views - Last Post: 25 July 2013 - 11:33 AM Rate Topic: -----

#1 Mei Yi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 25-July 13

Google maps API compute shortest path using TSP

Posted 25 July 2013 - 01:16 AM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Google maps API compute shortest path using TSP

#2 Michael26  Icon User is online

  • DIC-head, major DIC-head
  • member icon

Reputation: 355
  • View blog
  • Posts: 1,521
  • Joined: 08-April 09

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?

Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10488
  • View blog
  • Posts: 38,868
  • Joined: 27-December 08

Re: Google maps API compute shortest path using TSP

Posted 25 July 2013 - 03:12 AM

Held-Karp 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?
Was This Post Helpful? 1
  • +
  • -

#4 Mei Yi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 25-July 13

Re: Google maps API compute shortest path using TSP

Posted 25 July 2013 - 03:27 AM

View PostMichael26, 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.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10488
  • View blog
  • Posts: 38,868
  • Joined: 27-December 08

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 NP-Hard problem. You can brute force it for only a few vertices. Held-Karp scales better but it is still O(2^n *n^2).
Was This Post Helpful? 1
  • +
  • -

#6 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1010
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

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?
Was This Post Helpful? 1
  • +
  • -

#7 Mei Yi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 25-July 13

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 4-5 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.
Was This Post Helpful? 0
  • +
  • -

#8 koeshkoesh  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 59
  • Joined: 27-December 08

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...-travel-on.html
Was This Post Helpful? 1
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10488
  • View blog
  • Posts: 38,868
  • Joined: 27-December 08

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?
Was This Post Helpful? 0
  • +
  • -

#10 Mei Yi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 25-July 13

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.
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10488
  • View blog
  • Posts: 38,868
  • Joined: 27-December 08

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 path-finding problem. Finding the optimal path is O(V log(E)), while finding the optimal Hamiltonian Circuit (the TSP solution) is O(2n n2).
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1