Vrp solution prefers worst edge with highest cost, ignores very fastest route

I’ve got my first custom minimal example with 3-4 nodes running, it’s based on the “CostMatrixExample”. I have put normal paths at a cost of 5, a few “unpreferred” paths at a cost of 400 and a path with a cost of 2*1 that is supposed to be a “highway” and much faster than the 400 one.

My problem is that for some reason jsprit thinks the path with 400 (resulting in a cost of 410) is better than taking the same path back and it’s entirely ignoring the fastest node which would give a cost of just 22.

I’m sure I’m doing something wrong here but I cannot pin down the issue at all. I’ve changed almost nothing except for adding coordinates and cost. If you removed the fourth “quick” node it also prefers the 400 route instead of just driving the same path back. The Matrix is symmetrical so I’m unable to comprehend why this is happening.

Please don’t mind the tt function, it’s just because I quickly wanted to map the example strings to coordinates.

Thank you for your support.

public class CartMinimal {

static boolean HIGHWAY_EXISTS = false; //true adds node 3 that has the quickest link between 0 and 2
static double NA = 400.0; 			   //arbitrary number to prevent usage of this road, has no effect :(


public static void main(String[] args) {

    Examples.createOutputFolder();

    Location l0 = Location.Builder.newInstance().setIndex(0).setCoordinate(Coordinate.newInstance(0.0, 0.0)).build();
    Location l1 = Location.Builder.newInstance().setIndex(0).setCoordinate(Coordinate.newInstance(10, 0.0)).build();
    Location l2 = Location.Builder.newInstance().setIndex(0).setCoordinate(Coordinate.newInstance(10, -3.0)).build();
 
    VehicleType type = VehicleTypeImpl.Builder.newInstance("type").addCapacityDimension(0, 5).setCostPerDistance(1).build(); 
    
    VehicleImpl vehicle = VehicleImpl.Builder.newInstance("vehicle")
        .setStartLocation(l0).setType(type).build();

    Service s1 = Service.Builder.newInstance("1").addSizeDimension(0, 1).setLocation(l1).build();
    Service s2 = Service.Builder.newInstance("2").addSizeDimension(0, 1).setLocation(l2).build();

    
    VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
    
    costMatrixBuilder.addTransportDistance(tt("0"), tt("1"), 5.0);
    costMatrixBuilder.addTransportDistance(tt("0"), tt("2"), NA);
    costMatrixBuilder.addTransportDistance(tt("1"), tt("2"), 5.0);
    
    if(HIGHWAY_EXISTS) { //fastest between 0 and 2
    	costMatrixBuilder.addTransportDistance(tt("0"), tt("3"), 1.0);
    	costMatrixBuilder.addTransportDistance(tt("1"), tt("3"), NA);
    	costMatrixBuilder.addTransportDistance(tt("2"), tt("3"), 1.0);
    }

    costMatrixBuilder.addTransportTime(tt("0"), tt("1"), 5.0);
    costMatrixBuilder.addTransportTime(tt("0"), tt("2"), NA);
    costMatrixBuilder.addTransportTime(tt("1"), tt("2"), 5.0);
    
    if(HIGHWAY_EXISTS) {
    	costMatrixBuilder.addTransportTime(tt("0"), tt("3"), 1.0);
    	costMatrixBuilder.addTransportTime(tt("1"), tt("3"), NA);
    	costMatrixBuilder.addTransportTime(tt("2"), tt("3"), 1.0);
    }
    

    VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();

    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance().setFleetSize(FleetSize.FINITE).setRoutingCost(costMatrix)
        .addVehicle(vehicle).addJob(s1).addJob(s2).build();

    VehicleRoutingAlgorithm vra = Jsprit.createAlgorithm(vrp);

    Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();

    SolutionPrinter.print(Solutions.bestOf(solutions));
    
    new Plotter(vrp, Solutions.bestOf(solutions)).plot("output/yo.png", "po");

    System.out.println(solutions);
    
    new GraphStreamViewer(vrp, Solutions.bestOf(solutions)).setRenderDelay(300).display();

}

public static String tt(String id) { 
	
	String newString = "[x=0.9][y=0.9]"; //default value
	
	switch(id) {
		case "0":
		  newString = "[x=0.0][y=0.0]";
  	    break;
	  case "1":
		  newString = "[x=10.0][y=0.0]";
	    break;
	  case "2":
		  newString = "[x=10.0][y=-3.0]";
		break;
	  case "3": //fastest edge between 0 and 2
		  newString = "[x=5.0][y=-8.0]";
	    break;
	 
	  default:
		  System.out.println("WARNING, FALLING TO DEFAULT");
		  System.out.println(id);
	}
	return newString;
}

}

As far as I understand jsprit does not calculate the fastest path between locations A and B by visiting dummy node C, because C has no demand and there is no reason to visit this node. It merely looks into the matrix and retrieves the distance and time between location A and B, even though the route A, C, B might be faster than A, B.

If you want to vary the distance and time between two locations depending on some vehicle parameter or another parameter you could implement a vehicle- or parameter-dependent distance matrix which has different distance values depending on whether the highway is used or not.

Thank you for your reply but to be honest I then do not understand what jsprit is used for. If you could enlighten me on that or could tell me how I could model my problem so jsprit solves this minimal working example correctly that would be really helpful.

Thank you