Let’s say jsprit has planned a delivery solution in 5,000 iterations.
I now want to change the problem very slightly: for example, by adding an extra destination, or changing the time window for one of the existing destinations.
Is it possible to seed the new calculation with the old solution to make it faster? It should be faster, I’d think, to start with the old solution which is almost good enough (i.e. just missing the new destination) than starting completely afresh.
I think you have at least 2 options.
First, you can setup a new problem with the additional jobs and define an initial solution that equals to the solution from your previous run plus an unassigned job list where you put the additional jobs to. You can then add this solution with this. Additionally, I would suggest to reduce the alpha parameter indicating the greediness of the algorithm. You can do it like this when building the algorithm builder.setProperty(Jsprit.Parameter.THRESHOLD_ALPHA, "0.0");. For example, alpha = 0.0 means that the algorithm only accepts better solutions.
Second, you can use your previous solution to specify initial routes and [add them to your new problem]((https://github.com/graphhopper/jsprit/blob/master/jsprit-core/src/main/java/com/graphhopper/jsprit/core/problem/VehicleRoutingProblem.java#L291)., i.e. you need to define the new problem with your additional jobs along with initial routes. Let us know if you have problems to implement these 2 options or if you encounter any problems.
Hi Stefan,
Couple of things. First, the job priority implementation looks awesome, thanks for that feature!
I’m wondering what setting greediness to 0.0 means internally? If more jobs are added to a problem then the cost of the solution naturally increases. So does this mean that 0 greediness will work up to the point that things start becoming unassigned? If things must be unassigned, would it allow pre-existing services to be kicked to unassigned if a cheaper route could be found that incorporated the new pickups? That would be undesirable from a planning standpoint since you’ve already committed to the initial jobs.
If the above is the case, I wonder if a combination of priorities and greediness could work? Essentially, don’t kick out any of the existing and take what you can from the new pool?
EDIT: I also can’t get your second hyperlink to work.
Cheers,
Josh
Hi Josh,
I think he meant VehicleRoutingProblem/Builder/addInitialVehicleRoutes by the second hyperlink.
Best regards,
He
Hi @jie31best, @stefan,
I have tried the second solution and it works great but i have a problem. Assume the following scenario:
I have a only one vehicle and three jobs. I run the optimizer and it returned a solution with the best route. The vehicle serviced two jobs but several other jobs were posted. So, we added a new vehicle and added the new jobs, and then set the initial route from the first vehicle and ran the optimizer. The optimizer will not know that the were two jobs that were serviced already by the old vehicle.
How can i make the optimizer know that these jobs were serviced and hence excluded from the new optimization ?
I have thought about doing it in code, but even i want to do it, then i have to re-calculate times and costs.
Thanks
Hi @rdbrid,
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.
Best regards,
He
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.
Best,
Stefan
Hi @jie31best,
Thanks for you time.
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.
Hi @jie31best, @stefan,
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.
What do you mean by
ignore serviced jobs
?
Why do you need jobs that have already been served in your initial solution at all?
I assume the scenario is the following:
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) }.
Exactly what I was typing to @rdbrid 
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…
What is your suggestion for a dynamic problem?
To already plan initial routes based on expectations?
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.
Hi @roganjosh, @stefan,
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.