Can you help me with my Clarke and Wright algorithm implementation?

Question

I am trying to implement the Clarke and Wright algorithm to construct an initial VRP solution. It seems to run properly but for some reason the solution's quality I get is not the expected one.

Here's my code to compute the savings element:

private void computeSavingsElements() {
    for(int i = 0; i<vrp.getDimension(); i++) { 
        for(int j = 0; j <  i; j++) {           
                double savingValue =  vrp.distance(i, 0) + vrp.distance(0, j) - lamda * vrp.distance(i, j);
                SavingsElement savingElement = new SavingsElement (i,j, savingValue);
                savingsElements.add(savingElement);                                                 
        }
    }
    Collections.sort(savingsElements); // sort in ascending order
    Collections.reverse(savingsElements); // but we need descending order
    
}

The method to construct the solution:

private void constructSolution() {
    List<VRPNode> nodes = this.vrp.getNodesList();
    VRPNode depot = this.vrp.getDepot();
    double vehicleCapacity = this.vrp.getVehicleCapacity();
    
    
    VRPSolution solution = new VRPSolution(vehicleCapacity, depot);
    
    /*
     * In the initial solution, each vehicle serves exactly one customer
     */
    for (VRPNode customer:nodes) {
        if (customer.getId()!=0) { // if not depot
            VRPRoute route = new VRPRoute(vehicleCapacity, depot);
            route.addCustomer(customer);
            solution.addRoute(route);
            route = null; // eliminate obsolete reference to free resources
        }
    }   
    
    //System.out.println("INITIAL SOLUTION: \n"+solution.toString());
    
    int mergesCounter=0;
    for (SavingsElement savingElement : this.savingsElements) {
        if (savingElement.getSavingValue() > 0) { // If serving customers consecutively in a route is profitable
            
            VRPNode i = this.vrp.getNode(savingElement.getNodeId1());
            VRPNode j = this.vrp.getNode(savingElement.getNodeId2());
            
            VRPRoute route1 = solution.routeWhereTheCustomerIsTheLastOne(i);
            VRPRoute route2 = solution.routeWhereTheCustomerIsTheFirstOne(j);
            
            if ((route1!=null) & (route2!=null)) {
                if (route1.getDemand() + route2.getDemand() <= this.vrp.getVehicleCapacity()) { // if merge is feasible
                    /*
                     * Merge the two routes
                     */
                    solution.mergeRoutes(route1, route2);
                    mergesCounter++;
                }
            }
            
            
        }
        
    }   
    //System.out.println("\n\nAfter "+mergesCounter+" Merges"+"\n"+solution.toString());
    this.solutionConstructed = solution;
    
}

And for the route merges:

public void mergeRoutes(VRPRoute a, VRPRoute b) {
    /*
     * Provided that feasibility check has already been performed
     */
    List<VRPNode> customersFromRouteA = new LinkedList<VRPNode>(a.getCustomersInRoute());
    List<VRPNode> customersFromRouteB = new LinkedList<VRPNode>(b.getCustomersInRoute());
    
    /*
     * Remove the old routes
     */
    solutionRoutes.remove(a);
    solutionRoutes.remove(b);
    
    /*
     * Construct a new merged route
     */
    VRPRoute mergedRoute = new VRPRoute(vehicleCapacity,depot);
    
    /*
     * The new route has to serve all the customers 
     * both from route a and b
     */
    for (VRPNode customerFromA:  customersFromRouteA) {
        mergedRoute.addCustomer(customerFromA);
    }
    
    for (VRPNode customerFromB:  customersFromRouteB) {
        mergedRoute.addCustomer(customerFromB);
    }
    
    addRoute(mergedRoute);

    evaluateSolutionCost();
}

It seems to compute the savings correctly and to merge the route as it should, but the constructed solution's cost is too much. For example in a given instance I get 1220 while it should be 820.

Answer 1

One apparent issue is that your code only considers joining route j after route i when j < i. You should also consider joining them the other way around - in other words, in the inner loop in computeSavingsElements j should go up to the number of customer nodes (vrp.getDimension()).

Of course it's hard to tell if there are bugs in the parts of the code you are not showing, e.g. is the array routeWhereTheCustomerIsTheLastOne properly updated?