Initial Routes - Vehicles already dispatched

awesim · September 9, 2016, 5:49pm

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

braktar · September 12, 2016, 8:22am

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 :

jie31best · September 13, 2016, 6:45am

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

birchwood · February 14, 2018, 10:37am

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

jie31best · February 20, 2018, 3:32am

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.

birchwood · February 20, 2018, 7:25am

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?

jie31best · February 20, 2018, 7:36am

github.com

graphhopper/jsprit/blob/master/docs/Walkthrough Constraints.md#example

It is assumed that you know the basics of the [applied algorithm](Meta-Heuristic.md). In the recreation-step each
removed job is re-inserted into the ruined solution again (one after another). To actually insert a job, the algorithm
calculates its "best" insertion position. This implies also to check the feasibility of the insertion step
which is in turn dependent on constraints (such as capacity constraints).

## jsprit knows hard and soft constraints. 

- Hard constraints must be met and cannot be broken
- soft constraints are always fulfilled but uses penalties to express "good" and "bad" insertions.

jsprit comes with built-in or default constraints (such as capacity and time-window constraints) and allows you to add
custom constraints. However, you can also disable the default constraints. To add custom constraints use
<code>core.algorithm.VehicleRoutingAlgorithmBuilder</code> to build an algorithm instead of
<code>core.algorithm.io.VehicleRoutingAlgorithms</code>.

Note that

<pre><code>VehicleRoutingAlgorithmBuilder vraBuilder = new VehicleRoutingAlgorithmBuilder(routingProblem, "yourAlgorithmConfig");
vraBuilder.addCoreConstraints();
vraBuilder.addDefaultCostCalculators();

This file has been truncated. show original

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.

birchwood · February 20, 2018, 7:56am

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?