Hello, we are having problem with creating a constraint for the folowing. We have a service job which has a service time of 12 hours. Our vehiceles have a service time for 8 hours but multiple days. What we do is split the job in blocks of 2 hours. This is working perfectly but now a customer wants 2 constraints. One is that every splitted job must be assigned to the same vehicle, so it is not allowed that split 1 is for vehicle one and split 2 is for vehicle two. The second constraint is that all the splitted jobs must be assigned, so if only 5 splitted jobs are assigned the route is not correct, because not the whole job is assigned.
Jsprit is very powerful and a custom constraint will most probably solve your problem. But before doing that, it’s maybe worthwhile to consider simple standard features like skills.
You haven’t specified the complete problem, so I don’t know if it will work, but have you tried using skills? Defining a specific skill for one vehicle and the same skill as a required skill for the job with the 12 hour service time will result in all the splitted jobs to be assigned to the one vehicle.
Hello, thanks for your reply, vehicle have different skills and working times so it is not possible to assign a skill on beforehand. Also this does not solve
The problem to assign all splitted jobs if not possible then keep the job unassigned.
Hi @Decoder,
The first constraint (multiple jobs should be assigned to the same vehicle) is frequently asked about and you can refer to the classic stackoverflow post on related jobs.
The second constraint (multiple jobs should be either all assigned or all unassigned) is thus more interesting. A workaround I can think of now is that you create a virtual vehicle to take unassigned jobs (or maybe multiple such vehicles, if your fleet is finite). The virtual vehicles would have infinite capacity, no time window limit, etc. - you get the idea. And the cost parameters should be sufficiently large so that the jobs should prefer normal vehicles over the virtual vehicles, but maybe not too large because the jobs should prefer such virtual vehicles over being unassigned. Impose the first constraint on those jobs as well, so that they either go to the same normal vehicle or go to the same virtual vehicle.
This might solve your problem - or not, please let us know your test result if you are going to try it. Thanks.
Best regards,
He
Hello, Thanks for your reply, we also tested the stackoverflow link with related jobs, what we saw (but maybe we are wriong) is that de route is set in the beginning and vehicle never changed. So yes, the jobs are assigned to one vehicle only but that vehicle is set very early, so when i have vehicle A and B, same location then this constraint gives the jobs too A for example, but when i give vehicle A a smaller shift, so he can do less, then still the jobs go to vehicle A. We thought that the folowing code could be the cause :
public void begin(VehicleRoute route) {
this.route=route;
}
The virtual vehicle seems interesting. Is there a sample for this ?
Hi @Decoder,
I think the cause is that, in the ruin phase, the associated split jobs are not all ruined. Therefore, in the recreate phase, the ruined split jobs will be inserted to the same route as the unruined associated split jobs due to the constraint. Thus, I think what you can do is to define a new ruin strategy in which you make sure that the associated split jobs are either all ruined or all unruined.
But before that, since the associated split jobs are at the same location, I think you can first try to increase the probability of radial ruin strategies and/or cluster ruin strategies like the following with Jsprit.Builder.newInstance().
.setProperty(Jsprit.Strategy.CLUSTER_BEST, "1.0")
Regarding the virtual vehicles, I am afraid I don’t have any sample for now. The basic idea is that the virtual vehicles should be able to take any jobs, and the jobs should prefer 1) normal vehicles > 2) virtual vehicles > 3) being unassigned. And this is realized by tweaking the parameters. In the solution, there should not be any unassigned jobs, but the jobs assigned to the virtual vehicles are practically unassigned ones.
Best regards,
He
Hi,
He wrote it, you can easily define a constraint that makes sure that your dependent jobs needs to be served by the same vehicle. However, one cannot appropriately set them unassigned if one of them cannot be served. You can surely put a single job in the unassigned job list, but you cannot put all dependent jobs there once you realize that one of them cant be served. What you can always do is to unassign all as sort of postprocess after an iteration, however, you might loose some optimization potential this way - actually, I dont know for sure whether this is really a problem in the end. Ideally, this should be handled like a shipment. A shipment is only be assigned once you know for sure that both the pickup and the delivery can be done. Thus, to handle your case a job needs to be defined as an arbitrary number of dependent activities. This is definitely interesting but I do not yet have an idea how to get this done effectively.
Best,
Stefan
Hi @stefan,
Do you have any comments on his concern that it is difficult for the dependent jobs to change route in the optimization process? I think the reason is that it is more difficult that the dependent jobs are all ruined.
Moreover, let’s assume all those dependent jobs are ruined and to be re-inserted, then when the first of them is being inserted, the insertion cost only consider the impact of that job only (a fraction of a big job), rather than the impact of the whole bunch as a big job. My concern is that this might lead to non-optimal solution. What do you think?
Thanks.
Best regards,
He
I agree. However, if they share the same location it is probably covered reasonably well by the radial ruin strategy.
the insertion cost only consider the impact of that job only (a
fraction of a big job), rather than the impact of the whole bunch as a
big job. My concern is that this might lead to non-optimal solution.
What do you think?
I agree also but lack a reasonable solution for it. Let me think about it. This will be also an issue if we allow inter-route dependencies, e.g. two drivers need to meet at some place and time to exchange something, which is I think one of the most interesting future developments.