GraphHopper.com | Forum | GitHub | Maps | Blog

Preventing load "top ups"


#21

Hi all,

I’m looking into this issue recently. It seems to me such constraint could lead to sub-optimal solutions. Let me use a small example to illustrate:

Assume there are three locations:

O: (0, 0)
A: (0, 1)
B: (1, 0)

Two shipments from A to O, and two more shipments from B to O, each with size 1.

There is only one vehicle, with capacity 3, starting and ending at O. There is no time window or any other constraint except for the desired “preventing load top ups” constraint.

Obviously the optimal solution would be AAOOBBOO, where A and B represent associated pickups and each O is a delivery, and the cost is 4.

Let’s see what happens when the algo builds initial solution:

  • When it tries to insert the first shipment into an empty route, all four shipments lead to the same marginal cost, so let’s assume it inserts a BO into the route;

  • Then when it tries to insert the second shipment, obviously it will insert another BO into the route without starting a new trip, so the route becomes BBOO and the marginal cost is 0;

  • When it tries to insert the third shipment, it has two choices: 1) starting a new trip, i.e., making the route AOBBOO, and the marginal cost is 2; and 2) going to two different pickup locations in one trip, i.e., making the route ABBOOO, and the marginal cost is 1.414. Thus the algo will choose the second option;

  • Then when it tries to insert the last shipment, due to the capacity, it has to start a new trip, and due to the desired constraint, the route will become AOABBOOO, and total cost is 5.414.

What will happen if we don’t have the desired constraint in the problem? The first three steps will be the same, and in the last insertion, the route will become AAOBBOOO, and total cost is 4.

Note that for this small example, the iterative ruin and recreate process that follows will be able to find the optimal solution, but, for some larger problems, it is possible that it cannot.

Best regards,
He


If specified initial solution is the best ever solution, activities will have 0 arrival and end times
#22

Hi He

Sorry I did not see your post previously. I hope my response is still relevant.
I think you are right in your scenario however two operational factors make it work for us.

  1. Ours is a star config for the start of the day. So the trucks all come to one depot to load up. Other depot pickups are “end of day” activities to move stock to and from the main depot.
  2. The order of loading the jobs for delivery order is important so we can’t load additional jobs mid-run without screwing up the delivery order access to the product in the vehicle.