The Travelling Salesman problem

I have asked variations on this question before. I have not received a satisfactory answer. I think there may not be an answer.

The traveling salesman problem is basically this. Given a fixed number of locations to visit, starting from a know point, what are the OPTIMUM driving directions to travel the minimum distance and visit all points?

More specifically, my problem is I have a customer in a service business. He schedules appointments with customers every day. He want's to know the best travel plan, starting from this office, to visit all customers & return to the office.

We are using Google Maps to help in the scheduling to try to "cluster" the appointments for a specific day together, to minimize the distance between appointments.

ALL customer addresses have been geocoded using Google Maps; so the lat / long pair is known for every customer.

I am almost POSITIVE I located (some time ago) a Google MAPS API Method that would take up to 20 pairs of addresses and calculate the optimum directions. I think the "inbetween" addresses were called "way points". I CAN'T fin that reference now.

General Google searches indicate that the traveling salesman problem HAS NOT been solved.

Is there a way to do what I want using the Google MAPS Api (either php or JavaScript)?

It seems to me that I could construct an "optimizing" method by going through the possible routes via "brute force" (consider all possibilities), but I suspect the time required might be prohibitive
Richard KortsAsked:
Who is Participating?
Richard KortsAuthor Commented:
This is great.

The Google MAPS directionsService object seems to be EXACTLY what I need. I think I found this before.

Richard KortsAuthor Commented:
to owner66:

There seems to be a limit of 8 waypoints. Please look for my new question regarding this.

I hope there is a way around this.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.