I was wondering how I could define loose Job dependencies between jobs. I have found some information about this, and have already implemented what I thought would be a working solution, but something is evading me.
The specific goal (though later I’d like to generalize this) is to ensure that a Pickup-Delivery task can only be done after another specific Pickup-Delivery task. For context, the issue here is that the first Pickup-Delievery represents grabbing a piece of hardware and leaving it in a store, but later in the day, it must be taken back from the store to its owner - of course you need to make these in order and you must make sure that the second pair of Pickup-Delivery tasks only happens if the first already happened. Note that it does not need to happen exactly after, and it may happen later in time – but it must happen after. As such, we say that the second pair of Pickup-Delievery tasks loosely depends on the first.
My attempt at a solution involves:
A StateUpdater which creates a StateId where we store the start and end times of every service
A HardActivityConstraint which prevents insertion of activity X if it is being inserted before the activity on which it depends.
The StateUpdater is indeed inserting data into the StateManager, and the HardActivityConstraint is running. However, the results are not ideal: one specific pair of Pickup-Delivery tasks is inserted into the route, and none other is.
Am I missing something in my logic? I have experimented with this in several ways for several days now and since this is my latest attempt I may have a bug in my code too.
suppose the activity that X depends on is Y (i.e., X must be after Y), then the constraint also needs to prevent insertion of Y if it is being inserted after X. not sure if this is missing in your implementation.
moreover, it is possible that only one of the jobs is served and the other is unassigned. currently there is no “hard” way to make sure a job is served. what you can do is to set high priority for the job.
btw, i might be overlooking, but does your constraint want the two jobs to be served in the same route?
Regarding the two constraints (insertion of Y after X and preventing X before Y), there are edge cases and our implementation may not be the best:
What do we do if we are trying to insert X but Y isn’t inserted yet? Should we allow it?
Similarly, what do we do if we are trying to insert Y but X isn’t inserted yet?
Currently, I allow 2) but disallow 1).
The jobs do not have to be served in the same route. Some driver might do the first pair of tasks and another one do the second.
After some bugfixes regarding time window management and estimation, I currently have this scenario (each task is a pair of pickup/delivery jobs): Tasks A1, A2 (A2 depends on A1), B1, B2 (B2 depends on B1) and C1, C2 (C2 depends on C1)
Regardless of 1) and 2), tasks B1 and B2 always get correctly scheduled.
Depending on what I do in 1) and 2) I get different results. With what I currently have, I only execute tasks B1 and B2. It seems bizarre to me, but:
JSprit tries to insert A2 and C2 (it fails because of 1) )
JSprit never tries to insert A1 and C1
Is there any reason for JSprit not even trying a particular task? This isn’t the first time I’ve been faced with this situation
Most of the above issues have been fixed and were the result of some bugs on our part.
However, we have determined that this isn’t just a matter of loose job dependencies. If you take a look at my description, we want more than job dependencies: we want atomicity. We want to ensure that if task A2 cannot be done, then A1 cannot be done either. They are either all done, or none of them are done. How would you go about implementing this concept of atomicity? (should I create a new thread?)
My plan was to override the cost function (we already have a highly modified cost function) to achieve this, so that it would be better to leave the two tasks (A1 and A2) out than to leave one of them (A1 or A2). In practice, we give additional penalties if either A1 or A2 are left out, but not if both are left out or if both are assigned. The penalties are made in such a way that they overcome the individual unassigned penalties.
The main problem now seems to be that JSprit never tries the scenario where both A1 and A2 are excluded, and is thus leaving A1 (because it doesn’t know that removing it would be better). Is there some setting we can tune for this, perhaps related to the ruin step? We just need JSprit to experiment removing some jobs to see if that improves the score (which it will)
Thank you again, and do say if I should open a new topic for this
For this, I think you can use the listeners, for example, the IterationEndsListener. Below I give an example where s1 and s3 must be either both done or both unassigned. Note that I add an initial solution, because the IterationEndsListener does not apply to the generated initial solution if I do not define one.
VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
.addCapacityDimension(0, 5)
.build();
VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
.setType(type)
.setReturnToDepot(false)
.setStartLocation(Location.newInstance(0, 0))
.build();
final Delivery s1 = Delivery.Builder.newInstance("s1")
.setLocation(Location.newInstance(0, 0))
.addSizeDimension(0, 0)
.build();
Delivery s2 = Delivery.Builder.newInstance("s2")
.setLocation(Location.newInstance(0, 10))
.addSizeDimension(0, 0)
.build();
final Delivery s3 = Delivery.Builder.newInstance("s3")
.setLocation(Location.newInstance(0, 0))
.addSizeDimension(0, 10)
.build();
VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
.addVehicle(v1)
.addJob(s1)
.addJob(s2)
.addJob(s3)
.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
.build();
Jsprit.Builder algorithmBuilder = Jsprit.Builder.newInstance(vrp);
final VehicleRoutingAlgorithm algorithm = algorithmBuilder.buildAlgorithm();
algorithm.setMaxIterations(1);
VehicleRoutingProblemSolution iniSolution = new VehicleRoutingProblemSolution(
new ArrayList<VehicleRoute>(), vrp.getJobs().values(), 0);
final SolutionCostCalculator calculator = algorithm.getObjectiveFunction();
double iniCost = calculator.getCosts(iniSolution);
iniSolution.setCost(iniCost);
algorithm.addInitialSolution(iniSolution);
algorithm.addListener(new IterationEndsListener() {
@Override
public void informIterationEnds(int i, VehicleRoutingProblem problem, Collection<VehicleRoutingProblemSolution> solutions) {
for (VehicleRoutingProblemSolution solution : solutions) {
Collection<Job> unassignedJobs = solution.getUnassignedJobs();
Collection<Job> jobsToBeUnassigned = new HashSet<Job>();
if (unassignedJobs.contains(s1) && !unassignedJobs.contains(s3))
jobsToBeUnassigned.add(s3);
else if (unassignedJobs.contains(s3) && !unassignedJobs.contains(s1))
jobsToBeUnassigned.add(s1);
for (Job job : jobsToBeUnassigned) {
for (VehicleRoute route : solution.getRoutes()) {
if (route.getTourActivities().servesJob(job)) {
if (route.getTourActivities().removeJob(job))
solution.getUnassignedJobs().add(job);
}
}
}
double cost = calculator.getCosts(solution);
solution.setCost(cost);
}
}
});
VehicleRoutingProblemSolution s = Solutions.bestOf(algorithm.searchSolutions());
SolutionPrinter.print(vrp, s, SolutionPrinter.Print.VERBOSE);
I gave a simplified overview in this thread to get the idea across. In truth, our solution is much more general and allows arbitrary groups of tasks which must be done together. We had in the meantime hacked up a much less efficient solution because we were unaware of algorithm listeners. Your solution is great and was easily adapted to our scenario. Many, many thanks!
