GraphHopper.com | Forum | GitHub | Maps | Blog

Questions about fast regret and dependency type of jobs


#1

Hi,

Recently I am testing with fast regret. I have some questions about the update insertion data part of it.

I understand that, when it is not the first run, if the dependency type of the job is not defined or is NO_TYPE, it updates for the last modified route only; and if the dependency type is INTER_ROUTE or INTRA_ROUTE, it updates for all the routes. I understand the reason is that the current fast regret does not work when there are dependencies between the jobs, as commented in #161.

I used to think that when there is no dependencies between the jobs, if I define INTER_ROUTE or INTRA_ROUTE dependency type on all the jobs, it would return the same solution as the “regular” regret because it always updates for all the routes. However, I have conducted some tests on the pickups_and_deliveries_solomon problems and find out that is not the case. The tests also show that the solution changes quite a bit for some problems when I increase the proportion of the jobs on which I define INTER_ROUTE or INTRA_ROUTE dependency type.

I wonder does it indicate that there is something not correct with the current fast regret approach, or is it expected?

Please find below the code snippet and the test results.

Best regards,
He

code snippet:

    VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
    VrpXMLReader vrpXMLReader = new VrpXMLReader(vrpBuilder);
    vrpXMLReader.read("jsprit-examples/input/pickups_and_deliveries_solomon_c101.xml");
    VehicleRoutingProblem vrp = vrpBuilder.build();

    Jsprit.Builder algorithmBuilder = Jsprit.Builder.newInstance(vrp);

    // fast regret with dependency type intra_route on jobs
    StateManager stateManager = new StateManager(vrp);
    ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
    int count = 0;
    for (String jobId : vrp.getJobs().keySet()) {
        constraintManager.setDependencyType(jobId, DependencyType.INTRA_ROUTE);
        count++;
        if (count > vrp.getJobs().size() * 0.1) break;
    }
    algorithmBuilder.setStateAndConstraintManager(stateManager, constraintManager);
    algorithmBuilder.setProperty(Jsprit.Parameter.FAST_REGRET, "true");

    VehicleRoutingAlgorithm algorithm = algorithmBuilder.buildAlgorithm();
    VehicleRoutingProblemSolution s = Solutions.bestOf(algorithm.searchSolutions());
    SolutionPrinter.print(vrp, s, SolutionPrinter.Print.CONCISE);

test results:


#2

Hi @stefan,

I think I might have found a bug in fast regret (for the case where there are both jobs with dependency type INTRA_ROUTE/INTER_ROUTE and jobs with no type in the problem):

Assume in the unassigned job list we have a job A with dependency type INTRA_ROUTE and a job B with no type. When update insertion date, all routes will be updated with the latest version number in the updates map due to job A. However, for job B, only the last modified route will be really updated and added into the insertion data set with the latest version number, and all other routes are not.

Later, when get the best scored job, there is a comparison between the latest version number of the route obtained from the updates map and the version number of the versioned insertion data. Now, for job B, only the version number of the versioned insertion data for the last modified route matches the latest one, and all other routes have out-of-date version number. Therefore, job B can only be inserted into the last modified route or an empty one.

Hopefully I have made myself clear, and do you think this is a bug or do I simply misunderstood something @stefan? Thanks.

Best regards,
He


#3

Some updates: now I have achieved this for the tested problems. and “almost” achieved that the solution does not change when I increase the proportion of the jobs on which I define INTER_ROUTE or INTRA_ROUTE dependency type (by “almost” I mean for 5 out of 7 tested problems). Please find at the end the test results.

What I have done:

  1. fix the above bug;

  2. add this part of comparing job ids when two jobs have the same score to fast regret;

  3. deactivate the insertion noise by set INSERTION_NOISE_PROB to a negative value.

So back to the question I asked at the beginning, it is expected apparently. Now my new questions is, for the two problems where the solution still changes when I increase the proportion of the jobs with dependency type after I make the above changes to the code, why? and is it expected?

Best regards,
He


#4

Hi @jie31best
Is your fix merged to main branch? If not, can you please share it?