The Travelling Salesman problem
Posted on 2011-04-20
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.
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