HOME

OVERVIEW

APPLICATIONS

INTERACTIVE APPLETS
  • Build a robot
  • Extract anatomy
  • Traveling Salesmen
  • Evolving Curves
  • Image Denoising

    HISTORY OF THE METHODS/FLOW CHART

    PUBLICATIONS

    EDUCATIONAL MATERIAL

    ACKNOWLEDGEMENTS

    ABOUT THE AUTHOR/CV








    Copyright:
    1996-2010
    J.A. Sethian
  • Fast Marching Methods for the Continuous Traveling Salesman Problem


    The Traveling Salesmen Problem (TSP) is typically posed as follows: you are given a set of cities and a collection of links between the cities: each link carries a cost of traveling between the two cities (this is the symmetric TSP problem: if the cost in going in both directions is not the same, then the problem is asymmetric).

    Here, we are interested in a different, but related problem: Suppose the cost of traveling between the cities themselves is not known? Imagine that there are obstacles in the domain, or that the cost of traveling from one point to the next depends on position. In the figure below, if the cost of traveling through different colored regions is different, then you don't even know the path from one city to the next, let alone how to travel through all of them.
    The darker the area, the higher the cost. What is the cheapest path that visits all points? One way to construct the answer is using variants of fast marching methods, embedded in a graph-theoretic framework to solve the continuous traveling salesman problem.


    Below is a java applet that lets you try various costs functions and cities to determine the cheapest path.


    alt="Visit sun.com for the latest java version." Your browser is completely ignoring the <APPLET> tag! To Run:
    Link: Update to most recent java version.
    To enter points of interest/vertices/cities, do one of the following:
    -click on the mesh
    -enter x, y coordinates and click Enter
    -specify a number of cities to add and click Random
     To reset all points click Reset.

    This applet can compute:
    -the Minimum Spanning Tree(MST)
    -the MST joined with a minimum weight Perfect Matching among the vertices of odd degree in the MST
    -a heuristic solution to the Traveling Salesman Problem(TSP) using Christofides' algorithm, limit of 24 cities
    -the Optimal solution of the TSP, limit of 9 cities.
    -sample Contour lines over the mesh to one specified point, limit of 1 city

    All options should return a bright green lines displaying the appropriate result, after clicking Compute.
    The Research:
    The Paper

    The mesh is as you see it a greyscale image.  The darker the more costly to travel over that point, or slower, likewise, the lighter the less costly, or faster.  With the positions of the cities as shown, the object is to find the quickest path over the mesh from a single city, and jointly find the fastest path around all the cities. Different meshes can be selected in top right menu.
    If you discover problems with the applet - please take a screen shot and send it to me at astuteAjax gmail com cheers! June Andrews


    Main Reference:

    Andrews, J. and Sethian, J.A., Fast Marching Methods for the Continuous Traveling Salesman Problems, Proceedings National Academy Sciences, 2007. Vol. 17, No. 2, February 1995.