Multiple roundtrip deliveries from warehouse within bounded time window

Hi all,

First of all, jsprit is really awesome! I’m helping a friend with a delivery problem and I can’t imagine where we would be without jsprit!

I have the following delivery problem:

  1. There is one central warehouse where all packages are delivered.
  2. When a customer create an order, he/she specifies the time window within which the order is to be delivered, e.g. 4 - 5 pm, 5 - 6 pm, etc.
  3. The item delivered is perishable food item, and must be delivered within, say, one hour of the package leaving the warehouse.
  4. The driver may return to the central warehouse after delivering a few packages to pick up more packages for another set of deliveries.
  5. The objectives are, in the following descending order of importance:
    i). All packages must be delivered. No unassigned jobs.
    ii). Minimize the number of vehicles used.
    iii). Minimize the total distance traveled.

I tried to model this problem as a VRP as the following:

  • Use shipments rather than services so as to indicate that the driver may return to the dispatch location.
  • For each shipment, the pickup location is specified as the central warehouse and the delivery location is the customer’s address. The delivery time window is the time window provided by the customer.
  • Wrote a customized scoring function to heavily punish unassigned jobs.
  • Specified a finite fleet of drivers and a large number of initial drivers, but indicated the preference for using fewer drivers by setting a large vehicle fixed cost.
  • Expressed requirement #3 by writing a customized StateUpdater and HardConstraint to keep track of the time elapsed since departure from dispatch location and indicating that routes whose total time elapse greater than a certain threshold are inadmissible.

I ran the program with the above setup and found that jsprit was not able to create routes that had the driver return to the central warehouse to pick up more packages. In a toy example:

  • There are two time windows, 5 - 6 pm, and 6 - 7 pm.
  • There are 3 customer orders in 5 - 6 pm window, and 2 customer orders in 6 - 7 pm window.
  • There are 2 vehicles.
  • Packages must be delivered within 1 hour of leaving the warehouse.

In this example, jsprit gave a solution that had vehicle 1 deliver all orders in the first time window, and vehicle 2 deliver all orders in the second time window. I tried to force only 1 vehicle be used (it needs to return to base to pick up the packages for the second time window) by increasing the vehicle fix cost, but it didn’t help.

Do you know what I did wrong?


Hi @jovialnomad,

Your requirement #3 seems related to this post.

The description you gave on how you implemented it seems a bit suspicious:

Did you somehow disallow a route whose total time since departure from dispatch location is longer than 1 hour instead of the shipments?

Best regards,