How can I ensure that services occur in the same route using constraints?

jsprit
1

I’m trying to use Jsprit constraints to ensure that a solution route has a specific set of services… Given the services [S1, S2, S3, ..., S10], I want to ensure that services [S2, S4, S6] occur in the same route…

For this, I am using HardRouteConstraint…

@Override
public boolean fulfilled(JobInsertionContext context) {

    // jobIds = [S2, S4, S6]

	Job thisJob = context.getJob();
	if (jobIds.contains(thisJob.getId())) {
		for (String jobId : jobIds) {
			VehicleRoute route = stateManager.getProblemState(stateManager.createStateId(jobId), VehicleRoute.class);
			// if the jobs are assigned to a different route, reject this route
			if (route != null && route != context.getRoute()) return false;
		}
	}
	return true;
}

This works partially fine… If S2, S4 and S6 are part of the solution, they appear in a single route, and are not split between different routes…

The problem is that if I have a limited vehicle capacity (say, 3), Jsprit can possibly return a solution like:

Routes: [
    [S1, S2, S3]
    [S5, S7, S8]
    [S9, S10]
]
Unassigned Jobs: [S4, S6]

This is understandable, but not what I want… I want that if a route includes S2, it should also include S4 and S6, in any order…

How can I ensure that a valid solution does not contain such routes: [X, S2, Y] or [S2, X, S4]…

Thanks,
Asim

2

Hello,

The only way to force S2, S4 and S6 to be the in the solution is to edit the objective function and particularly the “Unassigned jobs” part.

Moreover you can be more efficient in your constraint if you set a stateUpdater in order to save for each activity its associated vehicle without scanning the actual route at each insertion.

To have your jobs in a right after order, you should have look at this :
https://github.com/jsprit/playground/blob/master/src/stackoverflow/Stackoverflow_RelatedJobs_13_and_21_inSameRoute_13_immediatelyAfter_21.java

You just should have to replace the softConstraint by a Hard one

1 Like
3

Hi @braktar… Thanks for the response… I already took the link you gave as a starting point… I tried both options:

  1. Keeping it as a SoftRouteConstraint… It didnt work at all for me… The activities ended up in any route…
  2. Converting it to a HardRouteConstraint… It didnt work completely… The code given above is an extract from this class… It ensured the if any activity from the set [S2, S4, S6] appeared in a route, you would have no other routes having an activity from this set… I understand that this is because the constraint code rejecting such solutions… Sometimes, I end up with routes like [S2, S4, S6, ... ]… But most of the time, I end up with routes like [..., S2, ..., S6, ...] and an unassigned list like [S4, ...]… I understand that this is because the solver is trying random configurations to see which one passes all the constraints… Sometimes it stumbles upon the correct solution… Other times it doesn’t…

I have even tried to use SolutionCostCalculator to define an objective function… Such that if there is no route with the complete set [S2, S4, S6], the solution should not be accepted… But it doesnt work either… Apparently the first solution that is generated by the system is stored nevertheless (even if SolutionCostCalculator rejects it)…

I have tried using InitialRoutes as well… It kinda works… But it respects the order too much… If the initial route was defined as [S2, S4, S6], it doesnt allow a route like [..., S4, S6, ..., S2] which might be shorter than [S2, ..., S4, S6]…

My end objective is to devise a structure of code generic enough so it can cater a user-defined series of jobIDs and ensure that either 1. All are present in any order in a route… 2. Some may be present in any order in a route… 3. All are present in the given order in a route with other activities inserted between them (InitialRoute)… 4. All are present in the given direct order with no other activities inserted between them… A long shot, I know… But I still wanna try doing it…

Perhaps the following might work… @braktar… Your thoughts about this would be really welcomed…

  1. Increase the priority of the set [S2, S4, S6] so that the system tries to adjust them first… Also, a hard route constraint that would calculate the capacity of the route and the vehicle and reject immediately if a non-required activity was attempting to be inserted in the route which would reduce the remaining capacity enough so that the set [S2, S4, S6] would not be able to fit in the route anymore…
  2. If there was a way to override the insertion algorithm that it should first start with the following permutations of routes: [S2, S4, S6], [S4, S6, S2], [S6, S2, S4], [S2, S6, S4], [S6, S4, S2], [S4, S2, S6], …, and see if a viable solution comes up or not… This is what I dont know how to do, if at all possible…
4

Hi Asim,

It seems that the gap between what you want and what you’ve got is that you need to make sure the jobs in the set (S2, S4 and S6) are always served.

The first thing you might want to try is the priority feature.

If that does not work, you can try defining a custom objective function, in which you impose a sufficiently high penalty if an unassigned job is one of those in the set.

Note that the above are both “soft” approaches, meaning they cannot guarantee the jobs in the set are always served. Nevertheless I think you can give them a try and see if they help.

Best regards,
He