Jsprit.Parameter.FAST_REGRET

kelish09 · March 20, 2017, 3:03pm

Hi,

I have a question regarding Jsprit.Parameter.FAST_REGRET.

I am trying to use it with initial routes, but no solution is generated. If I remove “Jsprit.Parameter.FAST_REGRET”, the solution is generated. I don’t know why is that.

From the description of FAST_REGRET, it says “Fast regret boosts your computation, i.e. it reduces computation time significantly. However, it can only be use currently if no complicated dependencies between jobs and activities are defined.”

What does “no complicated dependencies between jobs and activities are defined” mean?

Is it possible to use FAST_REGRET when you have initial routes?

Thanks!

roganjosh · March 20, 2017, 5:51pm

Hi,

This is incredibly obscure I’m afraid. What do you mean “no solution is generated”? How are you using “Jsprit.Parameter.FAST_REGRET”? Are there errors; what’s your setup? You need to give us some basis on which to make a judgement.

kelish09 · March 20, 2017, 6:18pm

Sorry if I wasn’t clear. Here is how I use Jsprit.Parameter.FAST_REGRET:

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

VehicleRoute initialRoute = VehicleRoute.Builder.newInstance(getVehicle(“IDxxx”, vrpBuilder)).addService(getService(“s1”, vrpBuilder)).addService(getService(“s2”, vrpBuilder)).build();
vrpBuilder.addInitialVehicleRoute(initialRoute);
VehicleRoutingProblem problem = vrpBuilder.build();
…
Builder vraBuilder = Jsprit.Builder.newInstance(problem).setStateAndConstraintManager(stateManager, constraintManager);
vraBuilder.setProperty(Jsprit.Parameter.FAST_REGRET, “true”);
VehicleRoutingAlgorithm vra = vraBuilder.buildAlgorithm();
…

The problem is that there are no errors to show or tack, and no solution is produced. It is just stopped.
However, if I remove the initialRoute part, it works fine and the solution is produced. Or if I remove the vraBuilder.setProperty(Jsprit.Parameter.FAST_REGRET, “true”) part and keep the initialRoute part, it works fine and the solution is produced.

Thanks!

kelish09 · April 6, 2017, 12:42am

Hi,

Does anyone experience the same problem described above?

Can “Jsprit.Parameter.FAST_REGRET” be used with “addInitialVehicleRoute( )”?

Thanks!

jie31best · April 6, 2017, 8:24am

are the jobs you added to the initialRoute (i.e., services s1 and s2) part of the vrp? if so, you probably will need to remove them from the vrp.

kelish09 · April 6, 2017, 3:50pm

No, they are not part of the vrp. I checked that.

kelish09 · April 7, 2017, 2:38pm

It is very strange that when I add Jsprit.Parameter.FAST_REGRET, it does not work:

vraBuilder.setProperty(Jsprit.Parameter.FAST_REGRET, “true”);

If I remove it, it works fine with the initialRoute.

Any thoughts what Jsprit.Parameter.FAST_REGRET does? Thanks!

jie31best · April 10, 2017, 4:12am

are there any other constraints that you added to the problem?

and also just to confirm, the algo worked fine when you added Jsprit.Parameter.FAST_REGRET and removed the initial route?

Best regards,
He

kelish09 · April 10, 2017, 4:27am

There are no other constraints.

Yes, the algo worked fine when I added Jsprit.Parameter.FAST_REGRET and removed the initial route.

Thanks!

jie31best · April 10, 2017, 4:30am

hmm, is it possible that you can share with us the full code to construct the vrp and the algo? thanks.

kelish09 · April 10, 2017, 7:34pm

Here is the full code:

import jsprit.core.algorithm.VehicleRoutingAlgorithm;
import jsprit.core.algorithm.box.Jsprit;
import jsprit.core.problem.VehicleRoutingProblem;
import jsprit.core.problem.VehicleRoutingProblem.Builder;
import jsprit.core.problem.io.VrpXMLReader;
import jsprit.core.problem.io.VrpXMLWriter;
import jsprit.core.problem.job.Job;
import jsprit.core.problem.job.Service;
import jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import jsprit.core.problem.solution.route.VehicleRoute;
import jsprit.core.problem.vehicle.Vehicle;
import jsprit.core.reporting.SolutionPrinter;
import jsprit.core.util.Solutions;
import java.util.Collection;

public class MultipleDepotWithInitialRoutesExample {

public static void main(String[] args) {

    VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
    /*
     * Read cordeau-instance p01
	 */
    new VrpXMLReader(vrpBuilder).read("input/cordeau01.xml");

	/*
     * Add initial route with 1_4_vehicle and services 44, 26
	 */
    VehicleRoute initialRoute = VehicleRoute.Builder.newInstance(getVehicle("1_4_vehicle", vrpBuilder)).addService(getService("44", vrpBuilder))
        .addService(getService("26", vrpBuilder)).build();
    vrpBuilder.addInitialVehicleRoute(initialRoute);

    VehicleRoutingProblem vrp = vrpBuilder.build();

    // this works fine
//VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp).buildAlgorithm();
	
    // this does not work, when Jsprit.Parameter.FAST_REGRET is used
VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp)
			.setProperty(Jsprit.Parameter.FAST_REGRET, "true").buildAlgorithm();
    
    
    Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();

    SolutionPrinter.print(Solutions.bestOf(solutions));

}

private static Service getService(String serviceId, Builder vrpBuilder) {
    for (Job j : vrpBuilder.getAddedJobs()) {
        if (j.getId().equals(serviceId)) {
            return (Service) j;
        }
    }
    return null;
}

private static Vehicle getVehicle(String vehicleId, Builder vrpBuilder) {
    for (Vehicle v : vrpBuilder.getAddedVehicles()) {
        if (v.getId().equals(vehicleId)) return v;
    }
    return null;
}}

jie31best · April 11, 2017, 2:40am

services 44 and 26 are added to the initial route by .addService(getService(“44”, vrpBuilder)) and .addService(getService(“26”, vrpBuilder)). it looks to me that they are part of the vrp, no?

Best regards,
He

kelish09 · April 11, 2017, 3:07am

No, they are not part of the vrp. You can check it using:
vrp.getJobs().containsKey(“44”);
vrp.getJobs().containsKey(“26”);

“since job (service) 26 and 44 are already planned in initial route and thus static AND sequence is fixed they should not be in jobMap anymore (only variable jobs are in jobMap).”

The example I posted is from:

github.com

graphhopper/jsprit/blob/master/jsprit-examples/src/main/java/com/graphhopper/jsprit/examples/MultipleDepotWithInitialRoutesExample.java

/*
 * Licensed to GraphHopper GmbH under one or more contributor
 * license agreements. See the NOTICE file distributed with this work for
 * additional information regarding copyright ownership.
 *
 * GraphHopper GmbH licenses this file to you under the Apache License,
 * Version 2.0 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.graphhopper.jsprit.examples;

import com.graphhopper.jsprit.analysis.toolbox.Plotter;

This file has been truncated. show original

Thanks!

kelish09 · April 11, 2017, 3:10am

I got the following error when I run the above code with “Jsprit.Parameter.FAST_REGRET”:

Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: 50
at jsprit.core.algorithm.recreate.RegretInsertionFast.updateInsertionData(RegretInsertionFast.java:164)
at jsprit.core.algorithm.recreate.RegretInsertionFast.insertUnassignedJobs(RegretInsertionFast.java:136)
at jsprit.core.algorithm.recreate.AbstractInsertionStrategy.insertJobs(AbstractInsertionStrategy.java:89)
at jsprit.core.algorithm.InsertionInitialSolutionFactory.createSolution(InsertionInitialSolutionFactory.java:56)
at jsprit.core.algorithm.PrettyAlgorithmBuilder$2.informAlgorithmStarts(PrettyAlgorithmBuilder.java:144)
at jsprit.core.algorithm.listener.VehicleRoutingAlgorithmListeners.algorithmStarts(VehicleRoutingAlgorithmListeners.java:127)
at jsprit.core.algorithm.VehicleRoutingAlgorithm.algorithmStarts(VehicleRoutingAlgorithm.java:296)
at jsprit.core.algorithm.VehicleRoutingAlgorithm.searchSolutions(VehicleRoutingAlgorithm.java:196)
at MultipleDepotWithInitialRoutesExample.main(MultipleDepotWithInitialRoutesExample.java:48)

jie31best · April 11, 2017, 4:22am

exactly, I got the same error when I constructed a small example.

what you need to do is that you should not add services 26 and 44 to the vrp.

kelish09 · April 11, 2017, 4:42am

What do you mean not adding them to vrp? They are already not part of vrp since I put them in initial route.

jie31best · April 11, 2017, 5:33am

look at the following example. s1 is added to the initial route, and is also added to the vrp. yes vrp.getJobs().containsKey(“s1”) will return false, but the algo will throw the error you encountered.

how to fix it? do not call .addJob(s1) when constructing the vrp.

    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
        .build();
    VehicleImpl v = VehicleImpl.Builder.newInstance("v1")
        .setType(type)
        .setReturnToDepot(false)
        .setStartLocation(Location.newInstance(1, 0))
        .build();
    Service s1 = Service.Builder.newInstance("s1").setLocation(Location.newInstance(0, 0))
        .build();
    Service s2 = Service.Builder.newInstance("s2").setLocation(Location.newInstance(0, 0))
        .build();
    Service s3 = Service.Builder.newInstance("s3").setLocation(Location.newInstance(0, 0))
        .build();
    VehicleRoute initialRoute = VehicleRoute.Builder.newInstance(v)
        .addService(s1)
        .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
        .addJob(s1)
        .addJob(s2).addJob(s3)
        .addVehicle(v)
        .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
        .addInitialVehicleRoute(initialRoute)
        .build();

    VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(vrp)
        .setProperty(Jsprit.Parameter.FAST_REGRET, "true")
        .buildAlgorithm();
    VehicleRoutingProblemSolution s = Solutions.bestOf(algorithm.searchSolutions());
    SolutionPrinter.print(vrp, s, SolutionPrinter.Print.VERBOSE);

kelish09 · April 11, 2017, 6:09pm

I think this is not the reason for the error. In my previous example that I posted which is adopted from (see below):

There is no addJob() for the jobs in the initialRoute(). So, s1 is added to the initial route, and is not added to the vrp.

Any other thoughts? Thanks!

github.com

graphhopper/jsprit/blob/master/jsprit-examples/src/main/java/com/graphhopper/jsprit/examples/MultipleDepotWithInitialRoutesExample.java

/*
 * Licensed to GraphHopper GmbH under one or more contributor
 * license agreements. See the NOTICE file distributed with this work for
 * additional information regarding copyright ownership.
 *
 * GraphHopper GmbH licenses this file to you under the Apache License,
 * Version 2.0 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.graphhopper.jsprit.examples;

import com.graphhopper.jsprit.analysis.toolbox.Plotter;

This file has been truncated. show original

stefan · April 11, 2017, 6:24pm

I ll have a look at this asap also (within the next two weeks).
I just opened an issue for this: https://github.com/graphhopper/jsprit/issues/331

kelish09 · April 11, 2017, 6:39pm

Great, thank you!!!