Tutorial 2 - Nearest Customers

In this tutorial you will build on what you learned in Tutorial-1 and use OR-Objects to construct a street network like the one above. Then you will customize a shortest path algorithm and use it to find customers nearest to the . The customers are labeled 'A' through 'J' and the nearness of a customer is measured by travel time. The symbols are traffic lights which require one minute to cross. The 'L' and 'R' mark corners where left and right turns are not allowed.

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

Tutorial 2 - Contents

Street Network

Street Class
Node Class
Build Graph

Algorithm

Properties Class
Initialization

Generate

Single Path
Multiple Paths

Draw

All Paths
Path

Street Network

The street network is stored in a SparseGraph and the classes Street and Node are used as the edge and vertex values respectively.

    SparseGraph graph;
    .............
    graph = new SparseGraph();

Street Network - Street Class

This class is used as the value for all edges. It contains the length and average speed for a section of street. The speed and length will be used together to compute the time to traverse the section, which is the cost that the algorithm will minimize.

class Street
{
    double speed;
    double length;

    Street(double len, double spd)
    {
        speed = spd;
        length = len;
    }
}

Street Network - Node Class

This class is used as the value for all vertices. It contains the coordinates that are used to draw the paths.

class Node

{

int x, y;

    Node(int X, int Y)
    {
        x = X;
        y = Y;
    }
}

Street Network - Build Graph

This method constructs the graph that represents the street network. This first portion adds the vertices for the intersections, customers and the depot.

    private void
    buildGraph()
    {
        try {
        // Add Intersections //
        graph.addVertex("N1E1", new Node( 44, 37));
        graph.addVertex("N1E2", new Node( 44, 79));
        ............................................
        graph.addVertex("S2E3", new Node(102, 115));
        graph.addVertex("S2E4", new Node(102, 148));

        // Add Customers //
        graph.addVertex("A",    new Node(135, 37));
        graph.addVertex("B",    new Node(166, 79));
        ............................................
        graph.addVertex("I",    new Node(183, 54));
        graph.addVertex("J",    new Node( 79, 133));

// Add Depot //
graph.addVertex("Depot", new Node( 79, 79));

The next step is to add the edges. Notice that the edges adjacent to the restricted right and left turns use the street name as a key. These names are used in Properties.isConnectionRestricted to prevent wrong turns. The one-way street is added as a directed edge.

// Add one-way street section
graph.addEdge("N2W1","N3W1",new Street(1.0,20),true);

        // Add Right Turn Restricted Edges
        graph.addEdge("N1E1","G",new Street(0.5,20),false,"E1");
        graph.addEdge("N1E1","N1E2",new Street(1.0,20),false,"N1");

        // Add Left Turn Restricted Edges
        graph.addEdge("G","N2E1",new Street(0.5,20),false,"E1");
        graph.addEdge("N2E1","N2E2",new Street(1.0,20),false,"N2");

        // Add Other Edges //
        graph.addEdge("N1E2","Depot",new Street(0.5,20));
        graph.addEdge("Depot","N2E2",new Street(0.5,20));
        graph.addEdge("N2E1","A",new Street(0.5,20));
        graph.addEdge("A","N3E1",new Street(0.5,20));
        ................................................
        graph.addEdge("N3E1","N4E1",new Street(1.0,20));
        graph.addEdge("N4E1","N5E1",new Street(1.0,20));
        ................................................

Algorithm

This tutorial uses the Connections algorithm because it uses the connection restriction and cost properties. If the street network didn't have turn restrictions then the Dijkstra algorithm would be a better choice since it is more efficient.

Algorithm - Properties Class

This class is used to customized the properties the algorithm uses to generate the paths. The algorithm calls getEdgeCost to obtain the cost of traversing an edge. Since we want to minimize the path travel time, this returns the time to traverse the street section in minutes.

class Properties
extends PropertiesAdapter
{
    public double
    getEdgeCost(EdgeI edge, boolean reverse)
    {
        Street street = (Street)edge.getValue();
        return (street.length/street.speed) * 60.0;
    }

The algorithm calls getVertexCost to obtain the cost of crossing a vertex. In this tutorial the cost of crossing a traffic light is one minute and zero for all other vertices.

public double

getVertexCost(VertexI v)

{

if("S1E3".equals(v.getKey())) return 1.0;

if("N3E2".equals(v.getKey())) return 1.0;

return 0.0;

}

The method 'isConnectionRestricted' implements the left and right turn restrictions. It also prevents u-turns.

public boolean

isConnectionRestricted(EdgeI in, VertexI v, EdgeI out)

{

if(in == out) return true; // No u-turns

Object inKey = in.getKey();

Object outKey = out.getKey();

if("N1".equals(inKey) && "E1".equals(outKey)) return true;

if("N2".equals(inKey) && "E1".equals(outKey)) return true;

return false;

}

Algorithm - Initialization

After the graph is built a new shortest path algorithm is constructed on the graph. The call to setProperties customizes the algorithmto use the vertex and edges values.

        buildGraph();
        algorithm = new Connections(graph);
        algorithm.setProperties(new Properties());

Generate - Single Path

This method generates and draws the path from src to dst. First it clears all the candidates and sets the destination as a candidate. It then generates the path from the source vertex and calls drawAllPaths to display the path.

    public void
    generateSinglePath(Object src, Object dst)
    {
        try{
            algorithm.setCandidate(false);
            algorithm.setCandidate(dst, true);
            algorithm.generatePathsFrom(src);
        }
        catch(VertexNotFoundException e){}
        catch(InvalidPropertyException e){}

drawAllPaths(algorithm.candidates());
}

Generate - Multiple Paths

This method generates and draws the paths beginning at the depot and ending at the candidates. First it selects all the customers as candidates and sets the maximum number of paths to generate. Then it creates the paths either from or to the depot and calls drawAllPaths with an enumeration on the candidates to display them.

    public void
    generateMultiplePaths(int n, boolean isFrom)
    {
        try{
            algorithm.setCandidate(false);
            algorithm.setCandidate("A", true);
            algorithm.setCandidate("B", true);
            ..................................
            algorithm.setCandidate("I", true);
            algorithm.setCandidate("J", true);

algorithm.setMaxPaths(n);

            if(isFrom)
                algorithm.generatePathsFrom("Depot");
            else
                algorithm.generatePathsTo("Depot");
        }
        catch(VertexNotFoundException e){}
        catch(InvalidPropertyException e){}

drawAllPaths(algorithm.candidates());
}

Draw - All Paths

This method receives an enumeration on the candidates. It iterates through each candidate that has a path and calls drawPath to display its path.

    public void
    drawAllPaths(Enumeration destinations)
    {
        Graphics g = this.getGraphics();
        paint(g);
        g.setColor(Color.white);

        try{
            while(destinations.hasMoreElements()){
           VertexI dest = (VertexI)destinations.nextElement();
           drawPath(g, dest);
            }
        }
        catch(VertexNotFoundException){}
    }

Draw - Path

This method draws the path from a candidate to the root. It gets an Enumeration on the path elements from the algorithm and uses it to walk down the path drawing the edges.

    public void
    drawPath(Graphics g, VertexI dest)
    throws VertexNotFoundException
    {
        Enumeration path = algorithm.pathElements(dest);
        VertexI vertex = (VertexI)path.nextElement();
        Node lastNode = (Node)vertex.getValue();
        while(path.hasMoreElements()){
            path.nextElement(); // Remove Edge
            vertex = (VertexI)path.nextElement();
            Node node = (Node)vertex.getValue();
            g.drawLine(lastNode.x,lastNode.y,node.x,node.y);
            lastNode = node;
        }
    }