• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 861
  • Last Modified:

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 Korts
Richard Korts
  • 2
1 Solution
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.

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now