GraphHopper.com | Forum | GitHub | Maps | Blog

Bug? initial route, fixed cost parameter, and break


#1

Hi all,

I think I might have encountered another bug with break. This time it is triggered by initial route and fixed cost parameter. That is, when all jobs in the vrp are in initial routes, and when there is a positive fixed cost parameter defined in the algo, the vehicle break will not take place. See the sample code at the end of the post for a small example.

In the sample code, if we change the value of FIXED_COST_PARAM to 0.0, or if we add another service to the vrp but not the initial route, then the break will appear.

What do you think? Any idea will be appreciated. Thanks.

Best regards,
He

    VehicleTypeImpl vehicleType = VehicleTypeImpl.Builder.newInstance("type")
        .build();
    VehicleImpl vehicle = VehicleImpl.Builder.newInstance("van")
        .setType(vehicleType)
        .setReturnToDepot(true)
        .setStartLocation(Location.newInstance(0, 0))
        .setEarliestStart(0)
        .setBreak(Break.Builder.newInstance("break")
                .addTimeWindow(1, 1)
                .build()
        )
        .build();
    Service service = Service.Builder.newInstance("s")
        .setLocation(Location.newInstance(0, 1))
        .build();
    VehicleRoute route = VehicleRoute.Builder.newInstance(vehicle)
        .addService(service)
        .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
        .addVehicle(vehicle)
        .addInitialVehicleRoute(route)
        .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
        .build();

    Jsprit.Builder algoBuilder = Jsprit.Builder.newInstance(vrp)
        .setProperty(Jsprit.Parameter.FIXED_COST_PARAM, "1.0")
        ;
    VehicleRoutingAlgorithm algo = algoBuilder.buildAlgorithm();
    VehicleRoutingProblemSolution solution = Solutions.bestOf(algo.searchSolutions());
    SolutionPrinter.print(vrp, solution, SolutionPrinter.Print.VERBOSE);

#2

I think I have figured it out:

all jobs are in initial routes, so vrp.getJobs().size() = 0;

fixed cost parameter > 0, so IncreasingAbsoluteFixedCosts is created with noJobs = 0;

thus nuOfJobs in SolutionCompletenessRatio is 0, and so solutionCompletenessRatio is always NaN;

therefore additionalICostsAtRouteLevel in BreakInsertionCalculator is always NaN, and thus break cannot be inserted.

a fix could be made to SolutionCompletenessRatio:

solutionCompletenessRatio = nuOfJobs == 0 ? 1 : (1 - ((double) nuOfJobsToRecreate / (double) nuOfJobs));