In this case I would suggest you use the first option @stefan provided , i.e., use initial solution. It will make sure the jobs assigned to certain vehicles in the initial solution stick to the same vehicles throughout the optimization. Moreover, the sequence between those jobs will not change. This is because those jobs will not be ruined at all in the process.
If you prefer the second option, i.e., use initial routes, or you would like to allow the sequence between those jobs to change, then you would need some soft/hard route constraints to make sure those jobs must be assigned to certain vehicles.
EDIT: sorry I made a mistake here - basically I said exactly the opposite… The correct version is that the initial routes impose sequence on the jobs and the job-route assignment while initial solution does not. Sorry for the confusion.
Hi Josh,
Thanks for your kind words with regard to priorities, and it was astonishingly easy to implement :).
I’m wondering what setting greediness to 0.0 means internally?
The entire meta heuristic is based on simulated annealing and threshold acceptance principles. It basically means that in the beginning of the search the algorithm does also allow solutions that seem to be bad (worse than solutions already found). This is to avoid the search to get stuck in local optima too earlier. However, depending on your alpha the algorithm converge to a greedy approach, i.e. an approach that only accepts better solutions. Jsprit here uses the threshold acceptance function proposed by Schrimpf et al.. The threshold func is described here. Just look here to get an impression of the func (for an ini threshold of 100, alpha=0.1 and 1000 iterations). Therefore, my idea was that if you already have a good solution you do not need to give the search much space to deviate from it to explore the entire search space again, you just assume that it is the result of a reasonable search process and the couple of additional jobs just need to be inserted into the existing solution.
Edit: Since unassigned jobs are penalyzed, it should be always more favourable to assign them. And to avoid that already assigned jobs (from your initial solution) end up in the unassigned job list, you can use the new priority feature and set the priority to high for already assigned jobs. Note that you need to evaluate the initial solution again taking the unassigned jobs into account also, i.e. add a penalty for each unassigned job.
I have tried the first solution. Its not working out for me. What i did is that i got a solution with two jobs j1 and j3. Then i add a new vehicle and two other jobs j2 and j4, then i did this:
// Solve the problem
VehicleRoutingAlgorithm vehicleRoutingAlgorithm = vehicleRoutingAlgorithmBuilder.build();
//Add initial routes
if(initialSolution != null)
vehicleRoutingAlgorithm.addInitialSolution(initialSolution);
Collection<VehicleRoutingProblemSolution> solutions = vehicleRoutingAlgorithm.searchSolutions();
The result is the same initial solution i have sent. I checked the solutions object, and there were two solutions. Both solutions are the initial solution i have sent…
Second, my question, is there way to to ignore serviced jobs such they that will not be taken into consideration in calculating the new solution while in the same time maintaining that a vehicle will service the jobs from the initial solution ?
Oops, sorry I made a mistake in my previous comment - I was thinking of initial route when I was talking about initial solution…
So the correct version is, if you use initial routes, the sequence of those jobs in the initial routes will be maintained - as well as job-route assignment for those jobs in the initial routes.
On the other hand, initial solution will not impose such sequence or job-route assignment.
Basically I said exactly the opposite…
Sorry for the confusion. I will add EDIT to my previous comment.
You need to evaluate your initial solution again along with the new jobs, so just add your new jobs to the list of unassigned jobs and call your solution cost calculator. Otherwise, - as you observed - you will end up with the initial solution since it will always have a better objective value.
Thanks for you time. No problem. I am going to go with the second solution i.e. initial routes because that is exactly what i need.
Still if you could please answer the second question regarding serviced job. I am insisting on this question because i am looking for a proper way to implement this. I am guessing that jsprit must have a built-in functionality for this.
What i am looking for is that if there is a way that i can flag a job that it have been serviced when i send an initial route, such that these un-serviced job will not effect times, costs and vehicle capacity.
The solution i have in mind, is to store the initial route and serviced jobs in a database and when i want to re-optimize, i will create a new route with the same vehicle from the initial route and assign it the remaining unserviced jobs.
Solve initial route at start of the period, store that route (which contains 100% of activities to do)
in reality, you get 10% of the jobs completed before a new pickup/delivery comes into your system. You want to re-solve with this new activity
If you load the initial route in (1) back in a starting route, it will still contain jobs that were completed in period (2).
I think the idea is that, whilst reloading an initial route might reduce computation time, it also might not be up to date to reflect the current status at the time of re-solving. I believe (s)he is looking for a way to remove jobs from a solved route before using it as a seed for a new solution.
Why cant we ignore served jobs at all? For example, you have an initial route = { start(home), serve(A), serve(B), serve(C), end(home) }, the driver starts and serves A and heads to serve B. Suddently a new job D appears in the system while the driver is somewhere between A and B. The new problem would then cover the B, C, D and the initial route without serve(A), i.e. new_route = { start(somewhere between A and B), serve(B), serve(C), end(home) }.
This should be addressed by some higher-level logic to handle an up-to-date route at time of calling Jsprit. If Stefan’s suggestion is insufficient for this problem then you’re going head-on into a dynamic problem. Experience tells me that the initial route will be of little benefit if this is actually the case. I’ve spoken to plenty of commercial routing companies that won’t touch this stuff because it unravels so quickly…
That depends very heavily on the size of the problem and the number of constraints. Your proposed approach is fully acceptable in the case that jobs are being added to a non-dispatched vehicle. Calling graphhopper, adding buffer travel time and estimations on traffic are unlikely to be enough to get a vehicle where you expect it to be at the time a new job comes online. This may be acceptable within OP’s operations.
In problems heavily constrained in terms of time windows, en route rescheduling (failed pickup/delivery) and frequent but time-distinct jobs coming online (meaning you call a new solution repeatedly at intervals) will cause small discrepancies on each cycle to accumulate fast. Jsprit alone will not handle it.
What stefan suggested works for me. The reason i asked for this is because i am calling jsprit from a higher end, so i though instead of manipulating the route from there, maybe i could just tell jsprit that these jobs are already serviced.
ODL live looks promising. However, currently, I can only evaluate it by looking at the API, i.e. the model, which is from what I see smth to keep track of vehicles on the road and incoming jobs. I do not see any heuristics, strategies such as waiting for a new request or any way to feed in my expectations of where a new job is likely to appear. This - I guess - is hidden by purpose, but still it makes it impossible for me to evaluate.
And I have not used it, nor am I involved in it. Just you can see the facilities for overrides etc. Whether it’s user-friendly and a complete model, I don’t know.
What starts out as a “if I could just change this one thing and solve my problems” affair soon degenerates into one of the most complicated and confusing problems imaginable. It’s no longer a purely mathematical problem, you’re throwing customer satisfaction, acts of God, management and operational judgement into the mix.
I’m currently running into this exact problem but it doesn’t seem like a proper solution has been described quite yet. Example:
Vehicle A -----------Service C-------------Service B
Vehicle A is “assigned” to Service B in a 1-job initial route due to a decision in a previous optimization. Service C gets added to the problem since that previous optimization and it’s between Vehicle A and Service B. Despite it being less efficient to do so, I’d like for Vehicle A to go to Service B before Service C. It was my understanding that this is how initial routes worked, but it appears that Service C can get added between Vehicle A and Service B.
Is there any way to treat the initial route ordering of Vehicle A -> Service B as “immutable”? I’ve set the THRESHOLD_ALPHA to 0.0 but that did not seem to help.
One approach that I’m considering is adding a HardRouteConstraint that takes the list of services added to initial routes in its constructor and returns NOT_FULFILLED whenever nextAct is one of the services added to the initial routes.
Thanks in advance for any direction that can be offered here! These discussions have been incredibly helpful.
You are right that the “new” jobs (the jobs not in the initial routes) can be inserted before, between, or after the “old” jobs.
You are also right that the approach you described would work to disallow any “new” jobs to be inserted before an “old” job, only that it would be a HardActivityConstraint.
