GraphHopper.com | Forum | GitHub | Maps | Blog

Potential bug resulting in unassigned jobs constrained by skills, determined by vehicle add order


#1

I was testing out a part of the skills constrained portion of jsprit, based on https://github.com/graphhopper/jsprit/blob/master/jsprit-examples/src/main/java/com/graphhopper/jsprit/examples/SimpleExampleWithSkills.java
here’s an excerpt of the relevant code:

final int WEIGHT_INDEX = 0;
VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance(“vehicleType”).addCapacityDimension(WEIGHT_INDEX, 1);
VehicleType vehicleType = vehicleTypeBuilder.build();

VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();

VehicleImpl.Builder vehicle2Builder = VehicleImpl.Builder.newInstance(“vehicle2”);
vehicle2Builder.setStartLocation(Location.newInstance(0,0));
vehicle2Builder.setType(vehicleType);
vehicle2Builder.addSkill(“saw”);
vehicle2Builder.addSkill(“drill”);
VehicleImpl vehicle2 = vehicle2Builder.build();
vrpBuilder.addVehicle(vehicle2);

VehicleImpl.Builder vehicleBuilder = VehicleImpl.Builder.newInstance(“vehicle1”);
vehicleBuilder.setStartLocation(Location.newInstance(0,0));
vehicleBuilder.setType(vehicleType);
vehicleBuilder.addSkill(“saw”);
vehicleBuilder.addSkill(“hammer”);
VehicleImpl vehicle = vehicleBuilder.build();
vrpBuilder.addVehicle(vehicle);

VehicleImpl.Builder vehicleBuilder = VehicleImpl.Builder.newInstance(“vehicle3”);
vehicleBuilder.setStartLocation(Location.newInstance(0,0));
vehicleBuilder.setType(vehicleType);
vehicleBuilder.addSkill(“hammer”);
vehicle = vehicleBuilder.build();
vrpBuilder.addVehicle(vehicle3);
/*

  • build services at the required locations, each with a capacity-demand of 1.
    */
    Service service1 = Service.Builder.newInstance(“1”).addSizeDimension(WEIGHT_INDEX, 1).addRequiredSkill(“saw”).setLocation(Location.newInstance(0,0)).build();
    vrpBuilder.addJob(service1);
    Service service2 = Service.Builder.newInstance(“2”).addSizeDimension(WEIGHT_INDEX, 1).addRequiredSkill(“drill”).setLocation(Location.newInstance(0,0)).build();
    vrpBuilder.addJob(service2);

VehicleRoutingProblem problem = vrpBuilder.setFleetSize(FleetSize.FINITE).build();

/*

  • get the algorithm out-of-the-box.
    */

VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);

/*

  • and search a solution
    */
    Collection solutions = algorithm.searchSolutions();

/*

  • get the best
    */
    VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

SolutionPrinter.print(pw, problem, bestSolution, SolutionPrinter.Print.VERBOSE);

Running this code results in the 2nd job being unassigned. However, if the order of adding vehicle2 was swapped with vehicle1 the correct solution is presented.

Is this a bug?


#2

You can try increasing the unassign cost (currently it is 0), for example:

    Jsprit.Builder algorithmBuilder = Jsprit.Builder.newInstance(problem);
    algorithmBuilder.setProperty(Jsprit.Parameter.MAX_TRANSPORT_COSTS, "100");

The initial solution is the same (the 2nd job being unassigned), but later iterations will generate the correct solution because the cost will be smaller with the introduction of the new unassign cost.


#3

Thanks for the prompt response!

Essentially, I suppose that by trying to simplify the problem by ignoring the distance between the jobs I had inadvertently caused the maxCosts to be lowered to 0 thus removing all unassigned job costs.

I think I understand it now. Thanks again!