In cases where the quantity of shipment is larger than capacity of largest vehicle the shipment is not served. In reality larger shipment is broken into smaller pieces and are served by multiple trucks. Is there a optimized way to break shipment into more than one piece and serve by multiple truck and also optimize it.
Let me add my 2 cents worth comment on this problem:
You can either:
a) Optimise the problem by changing the core of Jsprit or use another more general purpose optimiser that can also solve VRP problems. This is not necessarily difficult, but will require a reasonable amount of time and effort.
or
b) You can just use Jsprit with “human assisted heuristic”.
The choice would obviously depend on how much a very good solution is worth to you.
My guess is that a “human assisted heuristic” like described below could very well give you a good enough solution:
Manually test different choices and compare the results:
One choice would be to divide the loads into equal parts so that each vehicle has some “spare” capacity
Another choice would be to divide the loads into the biggest load that can fit into one vehicle and a smaller load. (Or a number of bigger loads with a small last load).
Based on this, one could have a separate “master optimiser” that optimises the “size of the pieces”, cascading to Jsprit “slave optimiser” that will solve the different optimisation problems, each with a fixed “pieces distribution”.
If there is only one load that is too big for the largest vehicle, then a simple Newton-Raphson based algorithm, written in Java in Jsprit environment might do the trick. (I know Newton-Raphson assumes a smooth function it is obviously not valid, but because it’s very simple it might be worth a try. NR does sometimes work even though the function is not smooth.)
1 Like
Thanks Pieter for your suggestions.
We were working on a similar line ( Using Jsprit with a human assisted heuristic), but our problem has non-uniforms vehicles. i.e trucks of different loads. In such case optimal division of package will depend on problem and other constraint and changing core of Jspirit is not an option for us.
So in absence of any other better option we have to go ahead with method suggested by you.
@pieter @Bhoumik_Shah Can you please elaborate more on
Based on this, one could have a separate “master optimiser” that optimises the “size of the pieces”, cascading to Jsprit “slave optimiser” that will solve the different optimisation problems, each with a fixed “pieces distribution”.
If there is only one load that is too big for the largest vehicle, then a simple Newton-Raphson based algorithm, written in Java in Jsprit environment might do the trick.
Any sample or approach would be great help.
Thanks