Travelling Salesman Problem

Problem Description

This problem is described in Section 4.7 of [1].

Program Descriptions

  • tsp.m
    This MATLAB program gives the best found tour via the CE method.

    Usage:
    Call the program from MATLAB, with the following syntax:

    pi = tsp( N , rho , alpha , A , traj )

    Example: tour = tsp( 1000 , 0.05 , 0.8 , A , 0 )
    where A is a matrix of lengths between nodes.

    Inputs:   
     N - Number of samples to generate each round
     rho - fraction of best samples to take
     alpha - smoothing parameter
     A - A(i,j) is the distance between node i and node j
     traj - 0, node placements
       1, node transitions
    Outputs:   
     pi - the best tour found
  • gtsp0.m
    This program is used internally to generate tours via node placements.

  • gtsp1.m
    This program is used internally to generate tours via node transitions.

  • stsp.m
    This program is used internally to evaluate the performance of a particular tour.

  • minitsp.m This is a program which generates a smaller TSP problem (with a specified number of nodes) from a larger one. This idea is mentioned in Remark 4.13 in [1].

Bibliography

  1. D. P. Kroese and R. Y. Rubinstein.
    The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning.
    Springer, 2004.