Tutorial 6 - Vehicle Routing Problem (VRP)

In this tutorial you will extend the problem introduced in Tutorial-4. The supply service located at the depot now owns a fleet of helicopters. The problem is to design delivery routes to serve all customers while minimizing the flight distance and not exceeding the load capacity or the range of the helicopters. A red dot () marks a customer demanding a 300 kilogram payload. A yellow () payload weighs 200 kilograms and a green () weighs 100 kilograms. The black dot () marks the depot. This tutorial also introduces geometric transform objects which are used to convert between the geographic, map and screen coordinate systems.

For simplicity, the material covered in Tutorial-4 and most of the applet details will be skipped. If you would like to see all the details then view the complete source.

Tutorial 6 - Contents

Initialization
Projection

Set Projection
Show Coordinates

Customers

Customer Class
New Customers

Algorithm

Composite
Construction
Improvement

Show

Build Solution
Paint Tours

Initialization

The method 'initTutorial' initializes the state of the applet before execution begins. The method 'newAlgorithm' is called to create the VRP algorithm that will be used initially. The variable 'geoRange' is set to the boundary of the service area and the two uniform distributions are constructed to generate coordinates inside the boundary. The load distribution is constructed to generate customer payload demands of 100, 200 and 300 with equal probability. The last line sets the initial projection to "Mercator".

    public void 
    initTutorial()
    {
        .
        .
        newAlgorithm(constructType, subalgorithmType, improveType);
        geoRange = new drasys.or.geom.geo.Range(160, -6.5, 162, -5);
        lonDist = new UniformDistribution(geoRange.west(), geoRange.east(), 123);
        latDist = new UniformDistribution(geoRange.south(), geoRange.north(), 321);
        loadDist = new DiscreteUniformDistribution(100,100,3); 
        setProjection("Mercator");
    }

Projection - Set Projection

The method 'setProjection' sets the map projection used to convert between geographic and map coordinates. It also sets the two dimensional transform to convert between map and screen coordinates.

    public void setProjection(String projectionStr)
    {
        if(projectionStr.equals("Mercator"))         
            projection = new Mercator(geoRange);
        else if(projectionStr.equals("Albers"))         
            projection = new Albers(geoRange);
        else if(projectionStr.equals("Lambert Conic"))         
            projection = new LambertConic(geoRange);
        
        xyRange = projection.forward(geoRange);
        PointI xyLowerLeft = projection.forward(geoRange.southwest());
        PointI xyUpperRight = projection.forward(geoRange.northeast());
        PointI screenLowerLeft = new Point(10, 150);
        PointI screenUpperRight = new Point(240, 10);
        screenTransform = new Transform(        
            xyLowerLeft, xyUpperRight,             
            screenLowerLeft, screenUpperRight);
        newCustomers(sizeOfStops);
    }

Projection - Show Coordinates

When the mouse is clicked on the map, the screen coordinates are first converted to map coordinates. Then the map coordinates are converted to geographic coordinates and displayed in the message area.

    public void
    mouseClick(int x, int y)
    {
        PointI projectedPoint = screenTransform.inverse(new Point(x,y));
        projectedPoint = xyRange.bound(projectedPoint);
        drasys.or.geom.geo.PointI geoPoint = projection.inverse(projectedPoint);
        String lon = (""+(geoPoint.longitude()+5.0E-7)).substring(0,10);
        String lat = (""+(geoPoint.latitude()-5.0E-7)).substring(0,9);
        messageLabel.setText("Lon,Lat = "+lon+", "+lat);
    }

Customers - Customer Class

The Customer class contains all the information about a customer. Customer is a subclass of a two dimensional rectangular point that stores the map coordinates of the customer and allows it to be used as a vertex value in a PointGraph. It also implements the DoubleI interface which causes any vertex that contains it to return 'load' from the doubleValue method. The doubleValue method is the default way that VRP algorithms obtain vertex load values. The variable 'screenCoord' is a two dimensional rectangular point that stores the screen coordinates used to draw the customer.

class Customer
extends Point
implements DoubleI
{
    double load;
    PointI screenPoint;

    Customer(double ld, PointI projectedPt, PointI screenPt)
    {
        super(projectedPt);
        load = ld;
        screenPoint = screenPt;
    }
    
    public double doubleValue(){return load;}
}

Customers - New Customers

The array of randomly generated customers is constructed in 'newCustomers'. Notice the 'customer' array holds the depot in location zero and the depot has a key value of "Depot" and a load of zero. Notice that the newly constructed PointGraph is used to initialize a MatrixGraph which is then used later in the algorithm. This is done so that the inter point distances will be pre computed and stored in a matrix inside the MatrixGraph for efficiency.

    public void newCustomers(int n)
    {
        customers = new Customer[n+1];
        PointGraph pointGraph = new PointGraph();
        drasys.or.geom.geo.PointI geoPoint;
        PointI xyPoint, screenPoint;
        
        Object key = "Depot";
        double load = 0;
        for(int i=0; i<=n;){
            geoPoint = new drasys.or.geom.geo.Point(        
                lonDist.getRandomScaler(),         
                latDist.getRandomScaler());
            xyPoint = projection.forward(geoPoint);
            if(!xyRange.includes(xyPoint)) continue;
            screenPoint = screenTransform.forward(xyPoint);
            customers[i] = new Customer(load, xyPoint, screenPoint);
            pointGraph.addVertex(key, customers[i]);
            key = new Integer(i);
            load = loadDist.getRandomScaler();
            i++;
        }
        graph = new MatrixGraph(pointGraph, null);
    }

Algorithm - Composite

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

The Composite class is a generic implementation of a composite VRP 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 vrp;

Algorithm - Construction

The method 'newAlgorithm' is called to create a new VRP algorithm when the parameters change. The string arguments name the algorithms to use. This first section of the method creates the chosen VRP construction algorithm with an optional TSP sub algorithm. The TSP newAlgorithm is used by VRP construction algorithms to reduce the cost of a tour when its expansion is restricted by the cost constraint. Notice the construction of the BestOf VRP algorithm if "Best Of Above" is selected as the construction algorithm. The BestOf object is initialized with a set of VRP algorithms and applies each algorithm in turn while retaining the best solution for use.

    public void
    newAlgorithm(String constructStr, String subalgorithmStr, String improveStr)
    {
        drasys.or.graph.tsp.ImproveI subalgorithm = null;
        if(subalgorithmStr.equals("None"))         
            subalgorithm = null;
        else if(subalgorithmStr.equals("2-Opt"))         
            subalgorithm = new drasys.or.graph.tsp.TwoOpt();
        else if(subalgorithmStr.equals("3-Opt"))         
            subalgorithm = new drasys.or.graph.tsp.ThreeOpt();
        else if(subalgorithmStr.equals("US-5"))        
            subalgorithm = new drasys.or.graph.tsp.Us(5);
        
        ConstructI construct = null;
        if(constructStr.equals("Clarke&Wright - savings list"))        
             construct = new ClarkeWright(iterations,strength,subalgorithm);
        else if(constructStr.equals("Gillett&Miller - polar sweep"))         
            construct = new GillettMiller(iterations,strength,subalgorithm);
        else if(constructStr.equals("Best Of Above")){
            BestOf bestOf = new BestOf();
            bestOf.addConstruct(new ClarkeWright(iterations,strength,subalgorithm));
            bestOf.addConstruct(new GillettMiller(iterations,strength,subalgorithm));
            construct = bestOf;
        }

Algorithm - Improvement

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

        ImproveI improve = null;
        if(improveStr.equals("None"))         
            improve = null;
        else if(improveStr.equals("Improve With Tsp: 2-Opt"))         
            improve = new ImproveWithTSP(new drasys.or.graph.tsp.TwoOpt());
        else if(improveStr.equals("Improve With Tsp: 3-Opt"))         
            improve = new ImproveWithTSP(new drasys.or.graph.tsp.ThreeOpt());
        else if(improveStr.equals("Improve With Tsp: US-5"))         
            improve = new ImproveWithTSP(new drasys.or.graph.tsp.Us(5));
        
        vrp = new Composite(construct, improve);
        vrp.setCostConstraint(rangeConstraint*1000);
        vrp.setCapacityConstraint(capacityConstraint);
    }

Show - Build Solution

The method 'buildSolution' creates the solution tours. There are three types of tours that 'buildSolution' can construct. If the tour type is 'Closed' then 'buildSolution' will construct all the tours so that they begin and end at the depot. If the tour type is 'Outbound' then all the tours will start at the depot and end at arbitrary customers. If the tour type is 'Inbound' then all the tours will start at arbitrary customers and end at the depot.

    public Vector[]
    buildSolution(GraphI graph)
    throws VertexNotFoundException, SolutionNotFoundException
    {
        vrp.setGraph(graph);
        if(tourType.equals("Closed")) 
            vrp.constructClosedTours("Depot");
        else if(tourType.equals("Inbound")) 
            vrp.constructInboundTours("Depot");
        else if(tourType.equals("Outbound")){
            vrp.constructOutboundTours("Depot");
        }
    return vrp.getTours();
    }

Show - Paint Tours

After the solution is constructed it is painted onto the screen using 'paintTours'. The array argument 'tours' contains the Vector objects which hold the vehicle tours. There is one tour in each 'Vector' and the vector contains all the vertices and edges in the tour in order from the origin to the destination. If a tour is closed the first vertex will be repeated at the end of the vector.

    public void
    paintTours(Vector[] tours)
    throws SolutionNotFoundException
    {
        int meters = 0;
        Graphics g = this.getGraphics();
        g.setColor(Color.blue);
        for(int i=0; i<tours.length; i++){
            Enumeration e=tours[i].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();
                meters += customer1.distanceTo(customer2);
                int x1 = (int)customer1.screenPoint.x();
                int y1 = (int)customer1.screenPoint.y();
                int x2 = (int)customer2.screenPoint.x();
                int y2 = (int)customer2.screenPoint.y();
                g.drawLine(x1, y1, x2, y2);
                e.nextElement(); // Skip Vertex
            }
        }
        
        String msg = "Vehicles - "+tours.length+", ";
        msg += "Distance(Km) - "+meters/1000;
            messageLabel.setText(msg);
        
    }