Dynamic routing with initial routes

jsprit
1

There is my scenario :
I am building a dynamic routing system.If there are 3 pickup points A,B,C and one depot D.At start,I can solve a routing plan like [D->A->C->B->D].After some time,perhaps this vehicle is between A and C.I want to reuse last time route [D->A->C->B->D] as InitialRoute and re-optimise a route when some new pickup requests in.However,at this time pickup A is completed.
My question is how can I get rid of completed service [D->A] and fix route [C->B->D] as InitialRoute that could accept or not accept new service requests [E,F,G…].
The only way I can figure out is to form a VehicleRoute by myself:

VehicleRoutingProblemSolution solution = Solutions.bestOf(solutions);
Collection routes = solution.getRoutes();
VehicleRoute newRoute = new VehicleRoute();
for (VehicleRoute route:routes){
for (Service service:route.getActivities()){
if(!service.isFinished()) newRoute.getActivities().add(service);
}}

Is there better way to achieve this goal? Thanks :slight_smile:

2

This is exactly the way to go. At this time (after pickup A is completed), it is new vehicle routing problem, and you can build a new problem with initial routes from scratch.

3

Hello stefan,thank you for your time.
I still have another question that is not related to above one.If my problem scale is about 10 vehicles and 10 points shipment.Is it possible to control solving time in milliseconds time?Or how to minimize solving time?

4

If you are (1) inserting only one job at a time, and (2) the already planned ones are in the initial route, and (3) travel times/costs are cached (=pre-computed) then it should take less than a second (for a problem of this size).

5

I will try to preprocess travel time costs. Thx :slight_smile: