How to optimize route when stops continue to be added in real time?


#1

I am trying to determine the most efficient route for a pizza delivery service and have a sample dataset that shows 75 address that need to be split among 6 cars for a simulated one hour lunch period.

When the cards begin from the store at 12:00, we may only have three deliveries and time goes on, additional orders come in. In the dataset, I’ve simulated 75 calls, their addresses, and the times during the one hour they would have made their order, and at which time their order/address could be added to a route at the earliest.

Is there any way to continuously add “new orders” to the routes and have the closest driver to the store come back to get a pizza and have it added onto his route?


#2

Dynamic planning is not supported as such, but there may be a workaround under the following assumptions:

  • After the cars have begun, each car drives its own route (e.g. no swapping of deliveries)
  • When a new order comes in, you know each car position and the orders that were delivered
  • Based on each car position you determine which car should get the new order

When a new order comes in, the procedure would be:

  • Select the route of the car than will get the order
  • Delete all addresses of ordes that were delivered
  • Add the current position of the car and set as departure address
  • Add the new order address and the store address
  • Set the store address to be visited before the new order address (pickup & delivery)
  • Recalculate the route