Tutorial 5 - Route Simulation

In this tutorial you will use the street network that was introduced in Tutorial-2 to simulate a service route. A single vehicle is located at the depot and each day it must visit all the customers that demand service. The customers that need service vary randomly and are known at the start of the day. The simulation will determine the expected time the vehicle will spend traveling to customers each day based on the average daily demand.

The simulation uses a poisson distribution to randomly select the number of customers that need service each day. Then a uniform distribution is used to pick the actual customers to visit. The chosen customers are selected in a traveling salesman algorithm which is then used to construct the vehicle tour. Finally the tour is drawn on the map and displayed in the message area.

Tutorial-2 explained the construction of the street network and how use a single vertex shortest path algorithm. This tutorial assumes you have read and understand Tutorial-2 and will not repeat that information. For simplicity, some of the applet details will be skipped. If you would like all the details then view the complete source.

Tutorial 5 - Contents

Initialize

Travel Graph
Demand Distributions

Simulate

One Day
Single Step
Run

Show

Tour
Path

Initialize - Travel Graph

This simulation uses the all pairs shortest path algorithm 'Iterate' to find the travel time between customers. 'Iterate' uses the single vertex shortest path algorithm 'Connections' as a sub algorithm to find the shortest paths.. The method 'initTutorial' constructs the street graph and both of the shortest path algorithms. It then uses the 'Iterate' algorithm to build a travel graph which contains the depot and all of the customers along with time it takes to travel between them. Finally the travel graph is used to construct the traveling salesman algorithm that will be used to construct the vehicle route.

    ConstructI  tsp;
    SparseGraph  graph;
    SingleVertexI singleVertexAlgorithm;

    .........

    public void
    initTutorial()
    {
        try{
            graph = new SparseGraph();
            image = this.getImage(this.getDocumentBase(), "Tutorial_5.gif");
            buildGraph();
            singleVertexAlgorithm = new Connections(graph);

The string array 'keys' contains the keys of the vertices that are included in the travel graph. The next four lines create the 'Iterate' algorithm, set the shortest path properties and clear all origin and destination vertices. The 'for' loop selects the depot and all of the customers to be both origins and destinations in the travel graph.

            String[] keys = {"A","B","C","D","E","F","G","H","I","J","Depot"};
            AllPairsI allPairsAlgorithm = new Iterate(graph, singleVertexAlgorithm);
            allPairsAlgorithm.setProperties(new Properties());
            allPairsAlgorithm.setOrigin(false);
            allPairsAlgorithm.setDestination(false);
            for(int i=0; i<keys.length; i++){
                allPairsAlgorithm.setOrigin(keys[i], true);
                allPairsAlgorithm.setDestination(keys[i], true);
            }

The next two lines build the travel graph and construct the traveling salesman algorithm that will use it. The graph returned from generateGraph is an instance of a 'MatrixGraph' which can be viewed as a matrix where, the origin vertices are associated with the rows, the destination vertices are associated with the columns and the matrix elements contain the travel times. 'MatrixGraph' is optimized for this purpose and is very efficient if the edges are retrieved with mutable methods and 'doubleValue' is used to get the edge values.

            AddI travelGraph = new SparseGraph();
            allPairsAlgorithm.fillGraph(travelGraph);
            tsp = new FullEnumeration(travelGraph);

            reset(3,5);
        }
        catch(VertexNotFoundException e){}
        catch(InvalidPropertyException e){}
        catch(DuplicateEdgeException e){}
        catch(DuplicateVertexException e){}
    }

Initialize - Demand Distributions

The 'reset' method is called to reset the simulation and to update the simulation parameters. In addition to resetting all of the simulation variables, it initializes the demand distributions.

The poisson distribution is a single parameter discrete distribution that represents the probability that N independent events will occur during some time interval, the time interval for this simulation is one day. The single parameter is the mean number of events expected for the day and is contained in the variable 'numberVisited'.

The discrete uniform distribution used here represents a set of equally spaced integers where all the integers have the same probability of selection. The set is defined by three parameters, the least integer in the set, the increment between adjacent elements and the number of elements in the set. The parameters are set to (0,1,10) so that each integer in the set will correspond to exactly one customer.

    DiscreteDistributionI poisson, uniform;

    ........

    public void
    reset(int nVisited, int nDays)
    {
        tour = null;
        dayCount = 0;
        totalTime = 0.0;
        currentTime = 0.0;
        numberVisited = nVisited;
        numberDays = nDays;
        poisson = new PoissonDistribution(numberVisited);
        uniform = new DiscreteUniformDistribution(0,1,10);
        update(this.getGraphics());
        tourLabel.setText("");
        showDist();
    }

Simulate - One Day

This main section of the simulation constructs the vehicle tour. The boolean array 'used' identifies customers that have been selected. The string array 'customers' contains the customer keys used to identify the customer vertices in the travel graph. The next two lines select the depot as the only selected vertex.

   public void
    simulateOneDay()
    {
        try{
            boolean[] used = new boolean[10];
            String[] customers = {"A","B","C","D","E","F","G","H","I","J"};

            tsp.selectVertex(false);
            tsp.selectVertex("Depot", true);

This next section gets the number of customers to visit from the poisson distribution and then randomly selects that number of customers using the uniform distribution. All customers have the same probability of selection and the while loop assures that no customer is selected more than once.

           int n = poisson.getRandomInteger();
           if(n < 1) n = 1;
           if(n > 8) n = 8;
           for(int i=0; i<n; i++){
               int idx = uniform.getRandomScaler();
               while(used[idx]) idx = uniform.getRandomInteger();
               used[idx] = true;
               String customer = customers[idx];
               tsp.selectVertex(customer, true);
           }

After the customers are selected in the traveling salesman algorithm a closed tour is constructed which repeats the first vertex at the end. Then the tour is rotated so that the depot is the repeated vertex and displays on the ends of the tour message.

           totalTime += currentTime = tsp.constructClosedTour();
           tour = tsp.getTour();
           tour = tsp.rotateClosedTour(tour, "Depot");
           showTourBuffered(tour);
           dayCount++;
        }
        catch(TourNotFoundException e){}
        catch(VertexNotFoundException e){}
    }

Simulate - Single Step

The method 'singleStep' is called when the single step button is pressed. It runs the simulation for an additional day by calling 'simulateOneDay'.

    public void
    singleStep()
    {
        if(dayCount >= numberDays) return;
        simulateOneDay();
        showDist();
    }

Simulate - Run

The method 'run' is called when the run button is pressed. It runs the simulation for the remaining days.

    public void
    run()
    {
        while(dayCount < numberDays)
            simulateOneDay();
        showDist();
    }

Show - Tour

The method 'showTour' draws the tour and displays the message that details the customers on the tour. The while loop adds each customer to the message string and calls 'showpath' to draw the travel path between adjacent customers.

   public void
    showTour(Graphics g, Vector tour)
    {
        String str = "";
        g.setColor(Color.white);
        Enumeration e=tour.elements();
        if(!e.hasMoreElements()) return;
        VertexI from = (VertexI)e.nextElement();
        str += from.getKey();
        while(e.hasMoreElements()){
            e.nextElement(); //Remove Edge
            VertexI to = (VertexI)e.nextElement();
            str += ", " + to.getKey();        
            showPath(g, from, to);
            from = to;
        }
        tourLabel.setText(str);
    }

Show - Path

The method 'showPath' draws the travel path between two customers. It creates the path between customers using the same sub algorithm that the 'Iterate' algorithm used to create the travel graph. It then loops through the vertices drawing the path. Notice that the vertex 'pathTo' is used to get the path from the shortest path algorithm instead of just using the argument 'to'. The reason is that the argument 'to' is a vertex from the travel graph, but the argument to 'pathElements' must be from the street graph since it is the graph used by 'singleVertexAlgorithm'.

    public void
    showPath(Graphics g, VertexI from, VertexI to)
    {
        try{
            singleVertexAlgorithm.setCandidate(false);
            singleVertexAlgorithm.setCandidate(to.getKey(), true);
            singleVertexAlgorithm.generatePathsFrom(from.getKey());
            VertexI pathTo = singleVertexAlgorithm.getNearestCandidate();
            Enumeration path = singleVertexAlgorithm.pathElements(pathTo);
            VertexI vertex = (VertexI)path.nextElement();
            Node node1 = (Node)vertex.getValue();
            while(path.hasMoreElements()){
                path.nextElement(); // Remove Edge
                vertex  = (VertexI)path.nextElement();
                Node node2 = (Node)vertex.getValue();
                g.drawLine(node1.x, node1.y, node2.x, node2.y);
                node1 = node2;
            }
        }
        catch(VertexNotFoundException e){}
        catch(InvalidPropertyException e){}
    }