Hello,
I have a number of jobs divided into two subsets: the first ones with higher priorities and it must be serviced in any case; the second subset with lower priority and it can be serviced when other constraints are satisfied (capacity and TW constraints).
How do I have to proceed?
Thank you,
Anis.
Hi @Anis_Mjirda,
You can check out this post in the old mailing list and Stefan’s answer there might be helpful to you, which I quote below:
You need a SoftContraint and a custom objective function. With the soft constraint, SoftRouteConstraint might be sufficient, you can for example decrease the insertion costs of a priority job by a certain value v so that it is more likely that a priority job will be inserted. At the same time you should consider this in your objective function, e.g. add (-1)*v if your priority job is assigned.
Best regards,
He
There’s obviously many different ways to do it, the way I would do it is as follows:
Define a “required skill” for the high priority jobs. Then have two (or two sets of) vehicles. The first vehicle has the skill required to do the high priority jobs, the second one not.
You run the algorithm and the jobs allocated to the first vehicle is then your answer.
Thank you very much for your answers @pieter and @jie31best.
I implemented a SoftRouteConstraint following the example given
here
The problem that the value returned
@Override
public double getCosts(JobInsertionContext insertionContext)
is not considered in the calculation of the modified objective function value:
Here is my code: `
public class JobPriorityConstraint {
public static class JobUpdater implements StateUpdater, ActivityVisitor {
private StateManager stateManager;
private VehicleRoute route;
public JobUpdater(StateManager stateManager) {
super();
this.stateManager = stateManager;
}
@Override
public void begin(VehicleRoute route) {
this.route = route;
}
@Override
public void visit(TourActivity activity) {
if (activity instanceof TourActivity.JobActivity) {
String jobId = ((TourActivity.JobActivity) activity).getJob().getId();
stateManager.putProblemState(stateManager.createStateId(jobId), VehicleRoute.class, this.route);
}
}
@Override
public void finish() {
}
}
public static class PriorityConstraint implements SoftRouteConstraint {
private final StateManager stateManager;
private List<Order> orders;
public PriorityConstraint(StateManager stateManager, List<Order> orders) {
super();
this.stateManager = stateManager;
this.orders = orders;
}
public String getPriority(JobInsertionContext insertionContext) {
for (Order order : orders) {
if (insertionContext.getJob().getId().equals(order.getId())) {
return order.getPriority();
}
}
return null;
}
@Override
public double getCosts(JobInsertionContext insertionContext) {
String priority = this.getPriority(insertionContext);
VehicleRoute route = stateManager.getProblemState(stateManager.createStateId(insertionContext.getJob().getId()), VehicleRoute.class);
if (route == null) {
return 0;
}
if (route != null) {
if (priority == "High") {
return -10;
} else
return 0.;
}
return 0.;
}
}
}
and here is my objective value calculation :
vraBuilder.setObjectiveFunction(new SolutionCostCalculator() {
@Override
public double getCosts(VehicleRoutingProblemSolution solution) {
double c = 0.0;
for (VehicleRoute r : solution.getRoutes()) {
c += r.getVehicle().getType().getVehicleCostParams().fix;
c += stateManager.getRouteState(r, InternalStates.COSTS, Double.class);
/*for (Job job : r.getTourActivities().getJobs()) {
if (getPriorityString(orders, job).equals("High")) {
c -= 10;
//c=c+10;
}
}*/
}
c += solution.getUnassignedJobs().size() * c * .2;
return c;
}
});
Thank you for your help!
Thank you for your valuable ideas to solve this problem!
Let me add another options. In the latest master, you can now easily define priorities for each job. Look at this issue and the referenced commits to see and evaluate how I implemented this. Furthermore, you can find a simple example here.
Hi @stefan,
I have done some tests with the priority feature, and it seems that it does not make sure the high priority jobs are always served, i.e., they can still be unassigned while some other lower priority jobs are served.
For example, consider the following vrp:
VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
.addCapacityDimension(0, 2)
.build();
VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
.setType(type)
.setReturnToDepot(false)
.setStartLocation(Location.newInstance(0, 0))
.build();
Service s1 = Service.Builder.newInstance("s1")
.addSizeDimension(0, 1)
.setLocation(Location.newInstance(0, 1))
.build();
Service s2 = Service.Builder.newInstance("s2")
.addSizeDimension(0, 1)
.setLocation(Location.newInstance(0, 1))
.build();
Service s3 = Service.Builder.newInstance("s3")
.addSizeDimension(0, 2)
.setLocation(Location.newInstance(0, -100))
.setPriority(1)
.build();
VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
.addJob(s1).addJob(s2).addJob(s3)
.addVehicle(v1)
.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
.build();
The solution returned by Jsprit is that s3 is unassigned despite its priority.
Perhaps adding another factor to the score in the Scorer class might help, something like
(4 - unassignedJob.getPriority()) * Integer.MAX_VALUE
(BTW, why Integer.MAX_VALUE here? I am not quite comfortable with the fixed value here - it might be not large enough in some cases - maybe something proportional to maxCosts is more appealing.)
The approach I have tried is the “old-fashioned” SoftRouteConstraint in which I [quote]
decrease the insertion costs of a priority job by a certain value v
[/quote], as in the first reply to the OP. Obviously, the solution depends very much on the value v - it has to be sufficiently large to work, and, again, I’d prefer some dynamic value, e.g., 5 * maxCosts would work in the above case.
Moreover, I have a feeling that both approaches (i.e., the priority feature, and the SoftRouteConstraint) might lead to sub-optimal solution.
What do you think?
Best regards,
He
Hi @jie31best, Thanks for your tests. You are correct, it is still a soft approach. In your example, it seems to be better in terms of objective value to assign the two low prio jobs. You should account for that in your objective function. It might be better to increase the weight of unassigned high priority jobs (compared to other prio jobs). I am not sure yet whether it makes much sense to further refine the scorer (I need to check). In the score you just want to make sure that high prio jobs are preferred over low prio jobs, i.e. if two jobs have the same score then please prefer high prio over low prio.
When it comes to your SoftConstraint approach, I do not think it has much effect since it basically controls the insertion position, i.e. at which position a job will be inserted, not so much whether a job will be inserted or not.
What do you mean with sub-optimal results? Do you mean that given high prio jobs are served, there are possible solution that serve high prio jobs as well, but that are more efficient? Do you have an example?
I think the most promissing way is to refine the objective function (assign high value to unassigned high prio jobs), but still as long as it is no hard approach, but a soft one as the priority approach actually is, you can always design problems such that low prio jobs are served before high prio jobs.
Best,
Stefan
Hi @stefan,
Thanks for your reply.
In real life, when it comes to high priority jobs, one just wants to make sure it is served, and profit is not the first thing to consider, just like what the OP requests. I understand that, in jsprit, we try to achieve this by playing around with the score, the insertion cost and the objective function, like what the priority feature and the SoftRouteConstraint approach do.
Eventually I combine those two approaches, i.e., besides setting priority for some jobs, I also reward the insertion of those jobs in a SoftRouteConstraint as well as in the objective function, and meanwhile penalize the unassignment of those jobs in the objective function. Yet, as you said, it is still a soft approach and won’t resolve the issue for good.
The only hard approach I can think of to make sure a job is assigned is to use initial routes, but the drawback is obvious: 1) one has to specify the vehicle for the jobs, and 2) the sequence of those jobs in the initial routes cannot be optimized.
I understand that, in the current Scorer, it makes sure that, when two jobs have the same score, the high priority one is preferred. But the issue I see is that, when a low priority job has a higher score than a high priority job, the former may be selected even though the score of the latter is inflated.
Regarding using the fixed Integer.MAX_VALUE when secondBest == null, my concern is that this value might not be large enough in some cases and a dynamic value can always serve to be sufficiently large.
The SoftConstraint approach I’m using is to define a SoftRouteConstraint like the following:
public double getCosts(JobInsertionContext jobInsertionContext) {
if (jobId.equals(jobInsertionContext.getJob().getId()))
return -rewardJobAssigned;
return 0;
}
It was just my suspicion, and now that I think a bit about it, it might be a false one. 
My suspicion was that, since the priority feature 1) sorts the jobs based on priority for half of the time in Best Insertion, and 2) inflates the score for high priority jobs in Regret Insertion, basically it is manipulating the sequence of the insertion of jobs, and it might be possible that the “manipulated” insertion sequence (high priority first, low priority second) would lead to a worse solution than the “normal” insertion sequence - but it turns out the sequence might not matter here as long as the jobs that are served are the same in both cases.
Best regards,
He
Hi jie31best, hi to all,
has the “priorities” requirement been satisfactorily resolved?
I also have these requirements and read from this case that this was created using soft constraint and therefore does not guarantee the requirement 100%.
I would really appreciate your answer or help!
Best regards, Rainer