GraphHopper.com | Forum | GitHub | Maps | Blog

Initial Routes - Vehicles already dispatched


#1

Hi…

I’m confused about how to use initial routes in Jsprit… The problem is as follows:

  • Suppose I have 10 orders to deliver… I use Jsprit to calculate a route like DEPOT > S1 > S2 > S3 > S4 > ... > S10 > DEPOT
  • I pack 10 orders and dispatch a vehicle along the route…
  • While the vehicle is going from S3 to S4, I receive 5 new orders (S11 thru S15)
  • I would like to use Jsprit here to find out if the route can be modified from S3 onwards to cater the new orders… Some options could be:
    1. S3 > S4 > S5 > S6 > S7 > S8 > S9 > S10 > DEPOT (pickup 5 new orders) > S11 > S12 > S13 > S14 > S15 > DEPOT
    • S3 > DEPOT(pickup 3 new orders) > S11 > S12 > S13 > S4 > S5 > S6 > S7 > S8 > S9 > S10 > DEPOT (pickup 2 new orders) > S14 > S15 > DEPOT
    • Keep existing route as is… Let the vehicle return… Then dispatch it like: DEPOT > S11 > S12 > S14 > S15 > DEPOT…

How can I achieve this in Jsprit? I have tried using InitialRoutes but it doesn’t work for me (or perhaps I dont understand the concept completely)… If I set Jobs as [S1, S2, ..., S14, S15] and set an InitialRoute as [S1, S2, S3], Jsprit doesnt respect the initial route order and you CAN get a new route like [S1, S14, S8, S2, S4, S9, S3, …]… I have already served [S1, S2, S3] and my vehicle is already somewhere between [S3, S4]…

Thanks,

Asim


#2

Did your vehicle start from a particular place or is it free ? In the second case, you either can have a virtual point which have a distance of 0 for each other Location or you can have look here :

The intermediate or initial DEPOT must be a Pickup at the Depot Location, and your S_i must be set as Delivery.

Moreover if you vehicle have could have no initial load or have a limited capacity you will need some modifications in the core :


#3

Hi Asim,

Finished jobs (S1, S2 and S3) should not appear in the initial route, like Stefan suggested in this post.

There is something you need to note regarding initial route: the jobs in the initial routes will not be ruined at all in the optimization process. Therefore, not only the job-vehicle assignment (in a multi-vehicle context) will not change, the sequence of them within the route will also not change. The new job(s) can still be inserted before/between/after them, though, like what you have already observed: [S1, S14, S8, S2, S4, S9, S3, …].

Moreover, if you model the jobs as services (or deliveries), it will not happen that the vehicle returns to the depot to pick up the new jobs. You should model the new jobs as shipments if you want that.

Hopefully it helps.

Best regards,
He


#4

Is there a way to also allow the initial route job sequence optimization?


#5

If you want only the job-vehicle assignment to be maintained and the sequence to be optimized, then you should not use the initial route in jsprit. Instead, you can use a hard constraint to force a job to be served by a specified vehicle, or, you can make use of the skills of the vehicles and the jobs.


#6

Can you please point to a example snippet where to start with hard constraints?
And what do you mean by using the skills of the vehicles - when I define a required skill for the job and the same skill for a vehicle, it doesn’t mean that the job is definitely in the route, does it?


#7

If the vehicle is the only one with that skill, then the job will at least not be in other routes.

If your concern is that the job might be unassigned, then unfortunately currently in jsprit there is no “hard” way to make sure a job is served (except initial route, but you do not want fixed sequence…) - there are “soft” ways, though, one of which is to assign priority to the jobs.


#8

I have tried assigning priorities - 1 for the required service and 10 for all others - if the required service is very far, it still is not guaranteed to be in the route…
Would it work if I ran the optimization twice - first with only the required jobs, (and start+stop location), to get the best sequence of the required jobs, then create an initial route with the results order and then add all other and re-optimize?