Wikipedia defines the “Traveling Salesman Problem” this way:
… given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
You can substitute “address” for “city”, making this an intra-urban travel problem. The OptiMap website solves this problem automatically for up to 24 locations (“nodes”). You can enter the nodes by clicking in a Google Maps interface:
You can also enter address nodes individually using the “Add Location By Address” box. Even better, you can add text lists of addresses or coordinates (latitude/longitude) by clicking on the “Bulk add by address or (lat, lng).” link, then copying and pasting the list into the text box that shows up. Latitude/longitude should be in decimal format, one set on each line, separated by commas and surrounded by parentheses, e.g. (35.333, –110.254). You can also specify only walking directions, and avoiding highways. The first node or address entered is always considered to be the starting point.
When you’re done entering nodes, click on “Calculate Fastest Roundtrip” to solve the problem for a round-trip that ends where you started:
You’ll also get a set of Google Maps driving directions for the trip shown in the solution map. By clicking on the “Toggle raw path output” button, you’ll also get a text list of latitude/longitude coordinates in sequence for this route that you could convert into a GPS route:
The “Calculate Fastest A-Z Trip” works in a similar fashion, but for a one-way trip, where the first address/node you entered is taken as the start “A”, and the last address/node is the destination “Z”.
The technical background and source code are available on the OptiMap website, as are instructions on how to use this on your own website.
