1

basically, I'm trying to implement an algorithm that dispatches drivers to deliver batches (a batch is a collection of orders). The algorithm takes all the batches and all the drivers available, then dispatches a driver that fits the batch the most. Now, what makes a driver the best to take a batch? This depends on the following: The distance the driver is to the batch and the amount of items the driver can carry (A driver can be on a bicycle, some will be on a motorbike, some in a car and others in a van). For example, let's say a batch is waiting at location x, driver 1(on a motorbike) is 1 mile away from location x and driver 2 (in a car) is 3 miles away from location x. The algorithm gives driver 1 the batch because he/she is closer to the batch. Now if the batch has a bunch of items/orders, let's say 20 items. It'll give driver 2 because he/she has a car that should be able to contain the batch. I have a method/function that takes the positions(latitude and longitude) of both the driver and order and returns the distance between them. I also have a method/function that manages the order capacity of a driver.

I'm curious as to how to do the matching (preferably an algorithm), is there a widely accepted solution that does something like this in a scalable manner?

PS: If you're curious as to how I currently do this, I basically show all the drivers the same list of batches, they can take a peek on what each batch contains and accepts which ones they'll work on.

  • Sounds like a combination of the Knapsack Problem and the Traveling Salesman Problem. – Robert Harvey Feb 6 '15 at 19:04
  • What you are asking for is remarkably similar to what UPS and FedEx have to do. They spend millions on algorithms to do this, and are not interested in sharing ;) – Cort Ammon Feb 6 '15 at 19:07
  • In a way, yes. Although, it's mostly the last mile part of deliveries. – Tommy Adey Feb 6 '15 at 19:11
  • There is not one widely accepted solution, this is a whole field of scientific research. You will find starting points here en.wikipedia.org/wiki/Global_optimization and here en.wikipedia.org/wiki/…. – Doc Brown Feb 6 '15 at 20:04
  • You'll probably want to optimize for time, not distance. A car 6 miles away can get to an order faster than a bicycle 2 miles away. – Dan Pichelman Feb 6 '15 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.