GraphHopper.com | Forum | GitHub | Maps | Blog

Maximum Wait Time Constraint


#1

Hello,
In my problem I’m dealing only with shipments which have a defined pickup time (I’m using shipment time window). I need to implement a maximum wait time constraint - if a vehicle arrives earlier to the pickup location, it cannot wait more then x minutes. And/or similar max distance constraint between 2 shipments (between prev shipment pickup and next shipment delivery in a route).

Also there cannot be more than 1 shipment in the vehicle at the same time (I use dimension for this)l

I’ve implemented HardActivityConstraint:
if(prevAct instanceof Delivery and newAct instanceof Pickup) {
calculate travel time from prevAct to newAct. Knowing prevActivity arrival time and newAct start time window we can easy compare
} else if (newAct instanceof Delivery and nextAct instanceof Pickup) {
similar. calculate travel time from newAct to nextAct and compare with nextAct start time window
} else fullfill;

It works reasonably good.
The problem I’m facing if there are some preassigned shipments (needs to be processed by the same vehicle) For this I’m using initial routes feature. But it breaks my constraint implementation:
Let’s say we have 5 shipments: S1 S2 S3 S4 S5 - all of them can be done by the same vehicle and satisfy my max wait time constraint (jsprit puts them in one route).
But if S1 and S5 are preassigned (part of initial route). Whenever jsprit tries to insert S2 or S3 or S4 in this initial route, it fails my constraint because for example wait time between S2 and S5 is not ok.
So the solution has to routes instead of one (S1, S5) and (S2, S3, S4).

What is direction I should look to solve my problem? Maybe I need an entire different approach?

Thank you.


#2

Hi @anatolyb,

I think this is kind of expected, given the nature of your constraint. When S1 and S5 are in one route and very far apart (time-wise), and when you try to insert the next job, it is possible that you cannot find a position in the route that any job can be inserted fulfilling the constraint and other constraints together.

This could also happen even when you do not have any initial routes. Just imagine that, after a ruin phase, what’s left is a route with S1 and S5.

I think you have two possible ways to tackle this:

  1. use a soft constraint instead; or
  2. you do not check for preassigned jobs in your hard constraint (it might be more complicated than just that).

In either case, I think you will need a custom objective function in which you penalize when the route does not satisfy your constraint.

Best regards,
He