Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to homes.

So drivers have to be coordinated to pickup food at a location and deliver to customers at home.

Primary goal is to minimize time to delivery, i.e. time between order and arrival at homes. The secondary goal is to maximize driver capacity (i.e., least amount of time to deliver all orders).

Bear in mind that the orders come in over a four hour period, so let's say evenly, i.e. one very 3 minutes. Also, let's assume the orders are randomly to the 20 restaurants.

Assume that I can calculate time to travel from any location to a destination to the second.

I know the location of all drivers in realtime. I also know their statuses, i.e. are they currently on their way to pick up an order (to take to a known destination), have they already picked up an order and are enroute to a known destination.

Constraints are: 1) Must pick up an order after a given time (i.e. meal preparation time for restaurant) 2) Must deliver order in under 45 mins (otherwise alert thrown) 3) Must pad time with "x" minutes to accommodate for time spent walking to store to pickup order, etc. 4) Must pad time with "y" minutes to accommodate for time spent delivering order to customer and collecting payment. 5) Drivers have only a given set of payment methods (e.g. Cash, Visa, Amex, MasterCard). We must match customer request (cash, visa, etc) with driver capability (cash, visa, amex, etc).

So for example, if I get two orders with close by destination and close by pickup locations, even if there is another "Free" driver (not doing anything), it would be more efficient to use the same driver to pickup both orders and deliver both orders.

You can assume there will be delivery zones enforced for each restaurant, meaning, most people ordering from them will most likely be close to them. Therefore, this algorithm should manage to segment drivers automatically into city zones, and favor drivers within the zone already.

share|improve this question
    
What precisely is your question? –  Henry May 8 '11 at 22:38
    
I think you would do well to start with a simplified model and try to solve that problem, and then start adding in extra complications like random order arrival time, fixed time to make deliveries, delivery zones etc. –  Chris Taylor May 8 '11 at 22:46
    
I'm trying to solve a Vehicle Routing Problem with Pickup and Delivery and Time Windows. I've been looking through research papers, but I can only find either Vehicle Routing Problem with Pickup and Delivery or Vehicle Routing Problem with Time Windows. Nothing that combines both. Wondering if anyone has any insight on satisfying both constraints. –  pmah May 8 '11 at 23:28
    
Cross-posted to programmers.stackexchange.com/questions/74709/… where it was closed. –  El'endia Starman May 9 '11 at 3:43
    
Try looking at the book: The Vehicle Routing Problem: Edited by Paolo Toth and Daniele Vigo, SIAM, 2002. –  Joseph Malkevitch May 9 '11 at 13:18
show 1 more comment

1 Answer 1

This problem is very similar to the DARPA COORDINATORS problem, which spurred a lot of research on the subject. In general, it is still an open problem and is extremely hard. A special modeling language called C-TAEMS was created for solving such problems. Searching for "C-TAEMS" on Google scholar reveals a number of papers that are likely relevant, e.g.,

In general, though, I am not aware of any existing algorithm or approach that performs better than a human.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.