We help IT Professionals succeed at work.

The Travelling Salesman problem

Richard Korts
on
Medium Priority
1,039 Views
Last Modified: 2012-05-11
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
Comment
Watch Question

Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
UNLOCK SOLUTION
Richard KortsBusiness Owner / Chief Developer

Author

Commented:
This is great.

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

Thanks!
Richard KortsBusiness Owner / Chief Developer

Author

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.
Unlock the solution to this question.
Thanks for using Experts Exchange.

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.