Sequential (queued) pickups from a single location

We have a problem where we have multiple vehicles picking up multiple people from a single location. We need to be able to limit pickups so that only one can be carried out at a location at a time. This essentially means that vehicles will be queuing up at a location to achieve their pickup. Is this possible in jsprit?

Hi @deadpassive,

I think it is doable. You will need a state updater to record the “occupied” time slots of all the locations in each route. Then in a hard activity constraint, for the newAct and every downstream activity, you will need to check whether the new “occupied” time slot of the activity in the current route conflicts with those of the same location in other routes, and if yes, the insertion would be disallowed.

Note that, the constraint needs to go over the list of activities in the current route, thus it is not efficient, but at this point I cannot think of a more efficient approach.

Hopefully the above helps.

Best regards,
He

Thanks @jie31best, that sounds like a good starting point. I do have one concern however - we do not necessarily want the insertion to be disallowed as we want vehicles to be able to arrive at a location at any time, but they can only pick up / drop off one at a time. It sounds like the solution you propose will not allow vehicle to wait in line at a location in this way - is that correct?

Thanks again,
Jon

Hi Jon,

Yes the constraint I proposed will disallow the insertion instead of making the vehicle wait.

The kind of waiting you want seems not doable… :sweat_smile:

Best regards,
He

That’s a shame. As a workaround we are going to alter our input data to stagger our pick-up and drop-off times. Hopefully that should simulate our requirement to some extent.

Thanks anyway!

Jon

I’m a big proponent of this approach. Ditch the hard constraints and reformulate the problem before getting jsprit to solve it. In this case, unless there’s some driving principle, I’d probably randomise the staggering of the jobs (so that their queue order was random) and remove costPerWait to open the problem up a bit more (the latter would need testing though as this might have adverse effects elsewhere). This will possibly perform better than a hard constraint in terms of solution times.

EDIT: Why do you need to stagger drop-off times? That should come from the matrix, so should be hands-off provided that your pickup time slots are staggered. You don’t mention that drop-off must also be queued in your original question; is this the case?