The Travelling Salesman problem

Posted on 2011-04-20
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
Question by:Richard Korts
    LVL 4

    Accepted Solution


    Author Closing Comment

    by:Richard Korts
    This is great.

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


    Author Comment

    by:Richard Korts
    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

    How to run any project with ease

    Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
    - Combine task lists, docs, spreadsheets, and chat in one
    - View and edit from mobile/offline
    - Cut down on emails

    Join & Write a Comment

    These days socially coordinated efforts have turned into a critical requirement for enterprises.
    Nothing in an HTTP request can be trusted, including HTTP headers and form data.  A form token is a tool that can be used to guard against request forgeries (CSRF).  This article shows an improved approach to form tokens, making it more difficult to…
    The viewer will learn how to look for a specific file type in a local or remote server directory using PHP.
    The viewer will learn how to create and use a small PHP class to apply a watermark to an image. This video shows the viewer the setup for the PHP watermark as well as important coding language. Continue to Part 2 to learn the core code used in creat…

    755 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    17 Experts available now in Live!

    Get 1:1 Help Now