Pick and Delivery Problem with Time Windows

I have a fleet of vehicles and a warehouse of apparatus. Most of the apparatus is rented out and delivered to users for a few hours at a time and then collected later in the day. Some edge cases involve a driver having to stay and manually operate the apparatus on behalf of the user then return it as usual. I am looking at cutting my costs and increasing productivity using a systematic approach rather than sitting for hours on end and manually configuring the schedules for all the orders on a daily basis. Is it possible to set up a Pick up and Delivery Problem with Time Windows solver for such use cases with JSPRIT? If so, which examples would be helpful in doing this please?

Yes, I think you could do this easily enough, but you might need to skew the features a little to get what you need. The most crucial thing I would need to know is what the driver does after the apparatus is dropped off (assuming that the driver does not have to remain on site)?

Can the vehicle carry more than 1 such piece of equipment?

Hi, roganjosh. Thanks for the response :slight_smile: - the driver and vehicle have to stay with the apparatus for a period of time and then they pack up and move on to the next job so potentially, yes. This has been difficult to program and test and I have done a lot of experimentation. Here are a few ideas I have been playing with:
1 - Set the unloading time to the duration of the full visit (eg 4 hour visit =240 mins so set unload time to 240 mins). Should I set pick up or delivery unload for this or possibly split the unload in 2 and overlap the min arrival time of pickup with the max arrival or drop off to try force the 2 to be on one route?
2 - Swapping negative and positive values for pickup and drop off demands to see if we can account for the fact that the apparatus is a constant on the whole journey.
3 - Creating ‘fake’ depots with the same coordinates as ‘base’ but adding them as nodes with the pickup or delivery depot as the destination or depot ID eg I have 1 depot and 10 nodes. 2 nodes require that the driver stays with the apparatus. It is physically possible for the driver to complete visiting all 10 nodes in one route but during a full route, the driver may have to return to base to drop apparatus A and collect apparatus B due to capacity issues. If I run the solver, I get 2 routes; one that completes 8 of the nodes including apparatus A and one that has a drop off with stay and pickup of apparatus B. There is a gap of 4 hours, during which the driver could include Route B within Route A by including a drop off to base of apparatus A and pick up of apparatus B.

Given that, in the real world ( I am using examples where actual completed jobs are used), a lot of the routes are very different but allow for return to base. How would you suggest approaching the type of problem and do you think my manipulation of the 3 metrics above is a recipe for disaster?
PS - I’ve looked at a few 90% solved routes that we can manually add on the remainder to nodes by splitting off the skipped ones and adding them on their own then matching differences manually. Is it possible to do this programmatically though?

I might have misunderstood here, but can you not just define them as services and set a service time for the whole duration?

Ok, re-read it. So (correct me if I’m wrong):

  1. Driver arrives and drops off equipment X that takes time A
  2. Driver may move on to deliver equipment Y that takes time B
  3. Driver returns to pick up X after A+ some fixed allocated time with equipment
    … and so on.

Yeah, that’s it. Think of a rental market where drivers may be required to operate machinery on some drop offs and not at all on others.

drop off 1 - Kit X, time taken A
pick up 1 - Kit X, time taken A
drop off 2 - Kit Y, time taken B
pick up 2 - Kit Y, time taken C

One caveat being; all kit needs returning home to base by COP, preferably same day.

This is a very interesting scenario. I look forward to the solution.

A similar scenario is that, in a delivery route, the driver has a few helping hands. At location A, helping hand (1) gets off and does deliveries in the neighborhood; the driver moves on to Location B, where helping hand (2) gets off and does deliveries in the neighborhood; and so on. Later the driver returns to location A to pick up helping hand (1) and so on.

The sequence of the returning pickups of the helping hands does not need to be the same as that of the dropping off of them. And when the number of deliveries in the neighborhood of a location is small, there is no need to drop off a helping hand and then later come back for him/her.

The save will be on time (no waiting time, no service time, etc.), while there will be extra cost on traveling time/distance, salary for the helping hands, etc.

Hi there :slight_smile: Yes, that is a similar situation and one that could possibly be helped in part, with how you input the data. I wonder if you tried something like; BEFORE you run your problem sequence of pick up and deliveries, look at the nodes that are within n distance from the Base node and omit the pickups so that they are not part of the problem solving.

For example, you have a base at 10,10 (x,y) and helping hands are able to walk back to base if they are within 1 position x or y, of the base. Run over all your data before you crunch it and omit every pickup where x and or y are 9-11. That way you now only have drop offs within the walking distance and the pickups will only be for those outside of the catchment.
Although this is a crude example, you could easily use geolocation (assuming you have lat/long of each node) with a radius in miles/km around a given lat/long (Base) to strip out the unnecessary data prior to using Jsprit.

It looks like the problem you are looking to solve is the Pickup and Delivery Problem with Time Windows, which I believe example of which are in here https://github.com/graphhopper/jsprit/tree/v1.6/jsprit-examples/src/main/java/jsprit/examples . Does that sound helpful or am I confusing the issue?