4

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.

4

2 回答 2

1

这听起来像是带有时间窗口的车辆路径问题的在线版本。我建议你用谷歌搜索并阅读出现的论文。

于 2011-05-08T20:12:30.910 回答
1

这取决于您为算法本身获得了多少开发时间（不包括 GUI、警报等）。

  • 如果您谈论的是 1 或 2 天，请使用确定性算法：将订单放入 FIFO 堆栈中，然后迭代地获取下一个订单并将其分配给第一个可用的驱动程序。这几乎就是人类的做法。它也不是很有效（特别是有 3 家或更多餐厅）。
  • 如果您有更多时间（因为您正在为一家大公司谈论这个问题），那么乐趣就开始了。研究元启发式（禁忌搜索、遗传算法、模拟退火）。查看现有的库来为您完成大部分工作。例如，如果您使用 Java，请查看Drools Planner。

顺便说一句：如果你正在考虑暴力破解它。不要打扰：它不会扩展。

于 2011-05-09T07:28:59.810 回答