NAG Toolbox for MATLAB Demo for the Travelling Salesman Problem

The NAG Toolbox routine nag_mip_tsp_simann (h03bb) calculates an approximate solution to a symmetric travelling salesman problem using simulated annealing via a configuration free interface.

This demo illustrates such the use of the routine to find a solution for a set of cities in the UK and Ireland.

Contents

The Classical Travelling Salesman Problem

Consider a salesman who has to visit a set of cities once each in a round trip in order to meet customers in each of these cities. There are many routes that can achieve this task, but there is likely only one (and its reverse) that will minimize the cost of that trip.

In simplest terms the cost will just be the total distance travelled, that being the sum of the distances travelled from one city to the next. However, in the problem framework, the cost of travelling from one city to another can be any positive value, which might be a function of many things.

For the purposes of this demo, the matrix of costs of travelling form any city to any other is simply the distance matrix computed from the city longitudes and latitudes.

Map of UK and Ireland and City List

travelling_salesman_demo.m contains a list of cities and their longitudes and latitudes. This list can be added to by editing the file: * add city names to the end of the array city_names * add latitude and longitude (in that order) for each cities as extra rows to the matrix latlong. You can select a subset of cities in the list to visit by changing the values in the index array choose. For example,

          choose = [1 3 5 7 9 11 13 15 17 19 21];
        

travelling_salesman_demo.m also contains details of the coastlines for the UK, Ireland and most of their associated islands. A map of the islands is drawn and then overlayed with the chosen set of cities.

Screenshot of Demo

nag_mip_tsp_simann (h03bb)

This routine is called to find a cost-efficient route through the chosen cities, starting and ending at the home city (Oxford by default). This route is then displayed on the map.