Tutorial 4 - Traveling Salesman Problem (TSP)

In this tutorial you will learn to use OR-Objects to model the problem pictured to above. A supply service is located at the depot and uses a helicopter to make deliveries. The problem is to design a tour which connects all the selected customers to the depot while minimizing the flight distance.

For simplicity, some of the applet details will be skipped. If you would like all the details then view the complete source.

Tutorial 4 - Contents

Customers

Customer Class
Customer Array

Selection

Spatial Index
Mouse Button

Algorithm

Composite
Construction
Improvement

Show

Build Graph
Construct Tour
Paint Tour

Customers - Customer Class

The Customer class contains all the information about a customer. Customer is a subclass of a geographic point which stores the coordinates of the customer and allows it to be used as a vertex value in a PointGraph. Customer also contains 'screenCoord' which is a two dimensional rectangular point that stores the screen coordinates used to draw and select the customer. The boolean variable 'isSelected' is used to mark the customers that need delivery.

class Customer
extends drasys.or.geom.geo.Point
{
    String key;
    boolean isSelected;
    drasys.or.geom.rect2.Point screenCoord;

    Customer(String id, double longitude, double latitude, int x, int y)
    {
        super(longitude, latitude);
        key = id;
        isSelected = false;
        screenCoord = new drasys.or.geom.rect2.Point(x,y);
    }

}

Customers - Customer Array

The 'customers' array contains all the available customers. Notice that element zero is the depot, it will always be selected. All customers have an ID, geographic coordinates and screen coordinates.

    public static final Customer[] customers = {
        new Customer("Depot", 161.325, -6.355,  132,  135),
        new Customer("A", 160.215, -5.155,  21,  15),
        new Customer("B", 161.015, -5.195, 101,  19),
        new Customer("C", 162.105, -5.225, 210,  22),
        new Customer("D", 160.565, -5.465,  56,  46),
        new Customer("E", 161.375, -5.465, 137,  46),
        new Customer("F", 161.025, -5.585, 102,  58),
        new Customer("H", 160.205, -5.845,  20,  84),
        new Customer("I", 161.035, -5.975, 103,  97),
        new Customer("J", 162.005, -5.835, 200,  83),
        new Customer("K", 160.325, -6.455,  32, 145),
        new Customer("L", 162.195, -6.505, 219, 150)
    };

Selection - Spatial Index

A point index is used find the nearest customer when the mouse button is presssed. The point index used is KDTree which uses the screen coordinate point for the key and the Customer object for the value. Notice the depot is not put in the index.

        PointIndexI index;

...

        index = new KDTree();
        for(int i=1; i<customers.length; i++){
            index.put(customers[i].screenCoord, customers[i]);
        }

Selection - Mouse Button

This method is called with the screen coordinates of the mouse cursor when the button is clicked. A point is created with the screen coordinates and passed to the point index to find the nearest customer. Once the nearest customer is found, the selected flag is toggled and the customer points are repainted.

        public void
        mouseClick(int x, int y)
        {
            PointI clickPoint = new drasys.or.geom.rect2.Point(x,y);
            PairI pair = index.getNearestNeighborTo(clickPoint);
            Customer Customer = (Customer)pair.getSecond();
            Customer.isSelected = Customer.isSelected ? false : true;
            paintcustomers(getGraphics());          
        }

Algorithm - Composite

The algorithm used is a composite TSP algorithm. A composite TSP algorithm combines a construction algorithm with an improvement algorithm. The construction algorithm is used to create an initial tour, then the improvement algorithm is used to make the tour better. In OR-Objects, construction TSP algorithms implement the ConstructI interface and improvement algorithms implement the ImproveI interface.

The Composite class is a generic implementation of a composite TSP algorithm. It is passed the construction and improvement algorithms when it is created. If null is passed for the improvement algorithm then only the construction algorithm will be used.

    Composite tsp;

Algorithm - Construction

The method 'newAlgorithm' is called when either the construct or improve choice changes. The two string arguments name the algorithms to use. This first section of the method creates the chosen construction algorithm.

    public void
    newAlgorithm(String constructStr, String improveStr)
    {
        ConstructI construct = null;
        if(constructStr.equals("Nearest Add")) construct = new NearestAddition();
        else if(constructStr.equals("Nearest Ins")) construct = new NearestInsertion();
        else if(constructStr.equals("Farthest Ins")) construct = new FarthestInsertion();
        else if(constructStr.equals("Cheapest Ins")) construct = new CheapestInsertion();
        else if(constructStr.equals("GENI-7")) construct = new Geni(7);
        else if(constructStr.equals("Enumeration")) construct = new FullEnumeration();
        else System.out.println("Can't find: "+constructStr);

Algorithm - Improvement

This second part of 'newAlgorithm' creates the chosen improvement algorithm and builds the composite algorithm using the two underlying algortihms.

        ImproveI improve = null;
        if(improveStr.equals("2-Opt")) improve = new TwoOpt();
        else if(improveStr.equals("3-Opt")) improve = new ThreeOpt();
        else if(improveStr.equals("US-5")) improve = new Us(5);
        else if(improveStr.equals("None")) improve = null;
        else System.out.println("Can't find: "+improveStr);
        
        tsp = new Composite(construct, improve);
    }

Show - Build Graph

To show the tour a PointGraph is built that models the selected customers. A PointGraph accepts vertex values that are points and uses the distance between the points to generate graph edges as they are requested.

        PointGraph graph = new PointGraph();
        for(int i=0; i<customers.length; i++){
            Customer Customer = customers[i];
            if(Customer.isSelected)
                graph.addVertex(Customer.key, Customer);
        }

Show - Construct Tour

After the graph is built a tour is constructed by calling 'buildTour'. There are three types of tours that 'buildTour' can construct. If the tour type is 'Closed' then buildTour will construct a closed tour. If the tour type is 'Open' then an open tour with arbitrary begin and end points will be constructed. If the tour type is 'Depot' then an open tour will be constructed starting at the depot and ending at a arbitrary customer.

        public void
        buildTour(GraphI graph)
        throws TourNotFoundException, VertexNotFoundException
        {
            tsp.setGraph(new MatrixGraph(graph, null));
            if(tourType.equals("Closed")) 
                tsp.constructClosedTour();
            else if(tourType.equals("Open")) 
                tsp.constructOpenTour();
            else if(tourType.equals("Depot")){
                tsp.constructOpenTourFrom("Depot");
            }
        }

Notice that the TSP algorithm is initialized with a 'MatrixGraph' constructed from the graph argument instead of the argument dorectly. The reason is that the argument is an instance of a 'PointGraph' and the distance calculations for the geographic points is relatively expensive. The 'MatrixGraph' will compute all of the distances just once and store the results so that the TSP algorithm can run more efficiently.
.

Show - Paint Tour

After the tour is constructed it is painted onto the screen. The method 'getTour' returns a vector which contains all the vertices and edges of the tour. If a tour is closed the first vertex will be repeated at the end of the vector. The while loop enumerates all the elements in the tour drawing only the edges.

    public void
    paintTour()
    {
        Graphics g = this.getGraphics();
        g.setColor(Color.blue);
        
        Enumeration e=tsp.getTour().elements();
        e.nextElement(); // Skip Vertex
        while(e.hasMoreElements()){
            EdgeI edge = (EdgeI)e.nextElement();
            Customer Customer1 = (Customer)edge.getToVertex().getValue();
            Customer Customer2 = (Customer)edge.getFromVertex().getValue();
            int x1 = (int)Customer1.screenCoord.x();
            int y1 = (int)Customer1.screenCoord.y();
            int x2 = (int)Customer2.screenCoord.x();
            int y2 = (int)Customer2.screenCoord.y();
            g.drawLine(x1, y1, x2, y2);
            e.nextElement(); // Skip Vertex
        }
    }