Problem with addInitialVehicleRoutes - array index out of bounds

Hi

I have built a model that makes three consecutive runs, each with an additional set of jobs and each with the routes from the previous run set as initialVehicleRoutes. It looks something like this:

Utils. **LOGGER** .log(Level. **INFO** , "Commencing Run 1 with jobs=" + vrpBuilder.getAddedJobs().size());
VehicleRoutingProblemSolution solution = getSolution(problem, **null** , depotList, jobVehicleMap, maxPickupSitesPerRoute, maxDropsPerRoute, maxIterations);
vrpBuilder_run2.addInitialVehicleRoutes(solution.getRoutes());
problem_run2 = vrpBuilder_run2.build();
Utils. **LOGGER** .log(Level. **INFO** , "Commencing Run 2 with jobs=" +    vrpBuilder_run2.getAddedJobs().size());
VehicleRoutingProblemSolution solution2 = getSolution(problem_run2, solution, depotList, jobVehicleMap, maxPickupSitesPerRoute, maxDropsPerRoute, maxIterations);
vrpBuilder_run3.addInitialVehicleRoutes(solution2.getRoutes());
problem_run3 = vrpBuilder_run3.build();
Utils. **LOGGER** .log(Level. **INFO** , "Commencing Run 3 with jobs=" + vrpBuilder_run3.getAddedJobs().size());
VehicleRoutingProblemSolution solution3 = getSolution(problem_run3, solution2, depotList, jobVehicleMap, maxPickupSitesPerRoute, maxDropsPerRoute, maxIterations);

On a sample data set the first run has 54 jobs, the 2nd run has 46 jobs.
The first run always runs ok but the 2nd run always throws an exception as follows:

threw exception [java.lang.ArrayIndexOutOfBoundsException: 48] with root cause

java.lang.ArrayIndexOutOfBoundsException: 48
at com.graphhopper.jsprit.core.algorithm.recreate.RegretInsertionConcurrentFast.updateInsertionData(RegretInsertionConcurrentFast.java:176)
at com.graphhopper.jsprit.core.algorithm.recreate.RegretInsertionConcurrentFast.insertUnassignedJobs(RegretInsertionConcurrentFast.java:149)
at com.graphhopper.jsprit.core.algorithm.recreate.AbstractInsertionStrategy.insertJobs(AbstractInsertionStrategy.java:91)
at com.graphhopper.jsprit.core.algorithm.module.RuinAndRecreateModule.runAndGetSolution(RuinAndRecreateModule.java:55)
at com.graphhopper.jsprit.core.algorithm.SearchStrategy.run(SearchStrategy.java:142)
at com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm.searchSolutions(VehicleRoutingAlgorithm.java:224)

Note that the exception is on index 48 which I suspect relates to the 1st of the added jobs (pickup & delivery = 47,48).
If I comment out the addInitialVehicleRoutes lines of code and just run them as three runs with distinct jobs, it all works without a hitch.

As I build each “run” I create the vrpBuilder_run object with the original vehicle list. I assume that is the right thing to do.

Note however that I am using a custom ruinEnd routine and If I disable that routine the whole thing runs ok.
clearly there is some problematic interaction between addInitialVehicleRoutes and the ruinEnd. But I cant work out what.
Below is the ruinEnd code.

	@Override
public void ruinEnds(Collection<VehicleRoute> routes, Collection<Job> unassignedJobs) {
	Map<TourActivity, VehicleRoute> toDeleteActRouteMap = new HashMap<>();
	for(VehicleRoute route : routes){
		for (int i = 0; i < route.getActivities().size()-1; i++) {
			TourActivity act1 = route.getActivities().get(i);
			TourActivity act2 = route.getActivities().get(i + 1);

			// ruin jobs less than 10 tonne
			if(act1.getSize().get(VehicleTypes.CONSTRAINT_CAPACITY) < 10000) // ruin jobs less than 10 tonne
				toDeleteActRouteMap.put(act1, route);

			// we also check distance to the next delivery here - we ruin the next job
			if(act2 instanceof DeliverShipment){
				Job j1 =  ((JobActivity)act1).getJob();
				Job j2 = ((JobActivity)act2).getJob();				        
				Double distance =  jobDistance.getDistance(j1,j2);
				if(distance > 15000){
					toDeleteActRouteMap.put(act2, route);
				}
			}
		}


		RouteRuns runs = new RouteRuns(route);

		Vehicle  v = route.getVehicle();
		int[] vehicleData =(int[])v.getUserData();
		int minimumLoad = 0;

		if(vehicleData == null){
			Utils.LOGGER.log(Level.INFO, "UserData was null: " +v.getId());
			minimumLoad = 4200;
		} else {
			minimumLoad = vehicleData[Constants.VEHICLE_MINIMUM_LOAD];
		}
		for(int i = 0; i < runs.size(); i++){
			if(runs.getRunDemand(i) < minimumLoad){
				ArrayList<Integer> run =  runs.get(i); 
				for(int idx : run){
					if(route.getActivities().get(idx) instanceof DeliverShipment){
						toDeleteActRouteMap.put(route.getActivities().get(idx), route);
					}

				}
			}
		}
		for (Map.Entry<TourActivity, VehicleRoute> entry : toDeleteActRouteMap.entrySet()) {
			TourActivity act = entry.getKey();
			VehicleRoute r = entry.getValue();
			if (act instanceof TourActivity.JobActivity) {
				Job job = ((TourActivity.JobActivity) act).getJob();
				boolean removed = r.getTourActivities().removeJob(job);
				if(removed){
					//unassignedJobs.add(job);  // this line throws a unsupportedOperationException
                                                                                         // dont know why yet
				}

			}
		}

	}
}

Hi @grantm009,

It seems the indices of the jobs are not updated in the second run and thus some of them could be out of bounds. This can be reproduced using the code I attached at the end.

EDIT:
hmm, I’m afraid the fix I proposed in the previous version of this reply does not really solve the issue. I will need to look into this one further. At this point I guess you might have to deactivate fast regret if you want to keep using your ruin listeners.

Best regards,
He

private static void testRuinListeners() {
    VehicleType vehicleType = VehicleTypeImpl.Builder.newInstance("car")
        .addCapacityDimension(0, 1)
        .build();
    final Vehicle vehicle = VehicleImpl.Builder.newInstance("car1")
        .setType(vehicleType)
        .setStartLocation(Location.newInstance(0, 1))
        .build();
    Shipment s1 = Shipment.Builder.newInstance("s1")
        .setPickupLocation(Location.newInstance(0, 0))
        .setDeliveryLocation(Location.newInstance(0, 0))
        .addSizeDimension(0, 2)
        .build();
    Shipment s2 = Shipment.Builder.newInstance("s2")
        .setPickupLocation(Location.newInstance(0, 0))
        .setDeliveryLocation(Location.newInstance(0, 0))
        .addSizeDimension(0, 1)
        .build();
    Shipment s3 = Shipment.Builder.newInstance("s3")
        .setPickupLocation(Location.newInstance(0, 0))
        .setDeliveryLocation(Location.newInstance(0, 0))
        .addSizeDimension(0, 1)
        .build();

    VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
    vrpBuilder.addVehicle(vehicle);
    vrpBuilder.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE);
    vrpBuilder.addJob(s1).addJob(s2).addJob(s3);

    VehicleRoutingProblem vrp = vrpBuilder.build();

    VehicleRoutingProblemSolution solution = solveVrpWithRuinListeners(vrp);

    VehicleRoute route = solution.getRoutes().iterator().next();

    VehicleRoutingProblem.Builder newVrpBuilder = VehicleRoutingProblem.Builder.newInstance();
    newVrpBuilder.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE);
    newVrpBuilder.addInitialVehicleRoute(route);

    solveVrpWithRuinListeners(newVrpBuilder.build());

}

private static VehicleRoutingProblemSolution solveVrpWithRuinListeners(VehicleRoutingProblem vrp) {
    Jsprit.Builder algoBuilder = Jsprit.Builder.newInstance(vrp);

    algoBuilder.setProperty(Jsprit.Parameter.FAST_REGRET, "true");

    algoBuilder.setProperty(Jsprit.Strategy.RADIAL_REGRET, "0");

    VehicleRoutingAlgorithm algo = algoBuilder.buildAlgorithm();

    algo.addListener(new RuinListener() {
        @Override
        public void ruinStarts(Collection<VehicleRoute> routes) {

        }

        @Override
        public void ruinEnds(Collection<VehicleRoute> routes, Collection<Job> unassignedJobs) {
            Map<TourActivity, VehicleRoute> toDeleteActRouteMap = new HashMap<>();
            for(VehicleRoute route : routes) {
                for (int i = 0; i < route.getActivities().size() - 1; i++) {
                    TourActivity act1 = route.getActivities().get(i);
                    TourActivity act2 = route.getActivities().get(i + 1);

                    toDeleteActRouteMap.put(act1, route);
                    toDeleteActRouteMap.put(act2, route);
                }
            }

            for (Map.Entry<TourActivity, VehicleRoute> entry : toDeleteActRouteMap.entrySet()) {
                TourActivity act = entry.getKey();
                VehicleRoute r = entry.getValue();
                if (act instanceof TourActivity.JobActivity) {
                    Job job = ((TourActivity.JobActivity) act).getJob();
                    boolean removed = r.getTourActivities().removeJob(job);
                    if(removed){
                        unassignedJobs.add(job);
                    }

                }
            }
        }

        @Override
        public void removed(Job job, VehicleRoute fromRoute) {

        }
    });

    VehicleRoutingProblemSolution solution = Solutions.bestOf(algo.searchSolutions());
    SolutionPrinter.print(vrp, solution, SolutionPrinter.Print.VERBOSE);
    return solution;
}

Okay, maybe try the following:

  1. add the following line for the new vrp builder for all initial routes:

    newVrpBuilder.addAllJobs(route.getTourActivities().getJobs());

  2. in RegretInsertionFast, change vrp.getJobs() in this line to vrp.getJobsInclusiveInitialJobsInRoutes()

  3. in ConstraintManager, change vrp.getJobs() in this line to vrp.getJobsInclusiveInitialJobsInRoutes(), and maybe other lines too

see if it works.

Best regards,
He

Hi He

Thanks for looking into this.

Thinking about your comments around indices not being updated I wondered if the order of adding initial routes and adding new jobs might be important. In my initial code I am adding the jobs and then adding the initial routes. I have changed that around and now it runs without crashing. However instead of adding jobs to the initial routes it created new routes for the vehicles with overlapping times. So one step forward and one step backward.

Next I applied your approach of: turn off fast regret and set radial_regret to 0.
The unassignedJobs.add(job); line still triggers the exception.

I think I understand your latest comments. I’ll try this next.

I’ll report back when done. Again - thanks
gmax

do you use some other ruin strategies that might return Collections.emptyList(), e.g., RuinString? if so, you will either have to turn it off, or make a change in the code to make it return new ArrayList<>().

OK thanks He

It will take some time to change the two jsprit modules. I usually compile from the maven libraries and getting the source into eclipse is proving… challenging :slight_smile: