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) {


    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")

    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);
    	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)

    VehicleRoutingAlgorithm vra = Jsprit.createAlgorithm(vrp);

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

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

    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]";
	  case "1":
		  newString = "[x=10.0][y=0.0]";
	  case "2":
		  newString = "[x=10.0][y=-3.0]";
	  case "3": //fastest edge between 0 and 2
		  newString = "[x=5.0][y=-8.0]";
		  System.out.println("WARNING, FALLING TO DEFAULT");
	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

jsprit is used to solve vehicle routing problems, where you either calculate the distances with some metric (e.g. euclidean) or specify the shortest distance between each point in a matrix.

If your distances between two points A and B vary scenario-based, then you could just create two matrices and each time before running a scenario use a different version of the VehicleRoutingTransportCostsMatrix.

If the distances depend on some parameter which changes depending on the route (e.g. the selected vehicle type), then you could modify the VehicleRoutingTransportCostsMatrix as mentioned above. Instead of having the standard matrix which looks like Map<RelationKey, Double> distances you could modify the matrix to look like Map<MatrixKey, Map<RelationKey, Double>>. Thereby the MatrixKey is some parameter that specifies which matrix should be used for the distance. Of course then you also have to modify the getTransportCost() method in VehicleRoutingTransportCostsMatrix to include the MatrixKey.

Thank you for the explanation. So that means to solve a problem with multiple pickups I would create a matrix e.g. with GraphHopper that shows the distance/time between each spot and each spot and then feed this matrix into jsprit to get the best order of operations?

So jsprit never really “sees” the map in terms of streets, junctions etc., it only sees a matrix that connects n to n-1 for each n that is a pickup spot?

EDIT: Ok I got it working. Thank you for your help!