食品配送中堆叠订单的算法（取货和送货）

Question

我正在尝试执行堆叠订单

虽然最佳解决方案是考虑从附近的餐厅取餐，这些餐厅的食物准备时间和送货地点都在附近。

我想从稍微简单一些的事情开始 - 即仅将来自具有相似食物准备时间的同一家餐厅的订单堆叠到多个送货点。（送货示例：https://riders.deliveroo.com.sg/en/tech-round-up-stacking-orders）

规模约为每小时20万个订单，5000名骑手，5000家餐厅。运行时间在这里很重要~最好少于 1 分钟（按需服务）

我的想法是这样的：

(1) 每几分钟收集一次订单，并按准备时间对所有订单进行排序 O(nlogn)

(2) 按餐厅分组订单 O(n)

(3) 从剩余准备时间最少的订单开始，查找同一餐厅在 window 时间内（比如 3-5 分钟）的所有订单，如果存在则将它们分组为一个堆栈。 O(1).

这里不考虑交付点的位置以减少计算 - 大多数交付点都在给定区域的 3 公里范围内。
对计算时间的全局最优不太感兴趣。选择剩余准备时间最少的订单是为了避免考虑骑手-订单排列匹配的所有组合。

(4) 运行车辆路径半最优 TSP 的模拟退火。（例如，从同一家餐厅取货订单 A、B、C -> 将 C 送到 A 再送到 B）

我知道对于多个 PICKUP 和 Dropoff 问题会转化为 VRPTW - 一个很难实时解决的问题。

一个更简单的问题 - 单次 Pickup 和多次 Drop off 是否有比我现在想到的更好的方法？

非常感谢。

Answer 1

我实现了你的算法

(1) Collect orders per few minutes interval and sort all orders by their prep time

(2) group orders by restaurant

(3) Starting from the order that has the smallest remaining prep time, look for any orders in the same restaurant within the time window (let's say 3-5 mins), if exists group them as a stack.

运行我的实现配置如下

theConfig.OrdersPerHour = 20000;        // incoming order per hour
theConfig.GroupTimeMins = 5;            // order collection time
theConfig.ResterauntCount = 1000;       // number of resteraunts
theConfig.PickupWindowMins = 5;         // pickup window time
theConfig.MaxPrepTimeMins = 15;         // maximum order preparation time

约1/3秒生成815个订单堆

C:\Users\James\code\pickup\bin>pickup.exe
Pickup
815 order stacks created
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        0.329374        0.329374        stack

您可以在 https://github.com/JamesBremner/pickup

查看代码

请注意，此时间不包括生成 driver 路线的时间。这应该不会花太长时间，因为每个 driver 将访问不到六个站点。这在很大程度上取决于正在搜索的图的大小。如果您可以围绕每个餐厅划分图表，那么它会很快。如果每次搜索可以在三分之一秒内完成，并且搜索是串联完成的，那么你将需要5分钟来执行800条路线。

作为初始实验，我假设：

将搜索图划分为 5 公里乘 5 公里，餐厅位于中心
曼哈顿距离
送货到最远的角落，或靠近最远的角落

对 Pathfinder travelling salesman implementation.

使用以下输入

format sales
manhatten 0 0 0
c 0.0 0.0 rest
c 2.5 2.5 topright
c -2.5 2.5 topleft
c 2.5 -2.5 bottomright
c 2 2 neartopright

给予

这需要 0.4 毫秒。

pickup timer test
manhatten 0 0 0
c 0.0 0.0 rest
c 2.5 2.5 topright
c -2.5 2.5 topleft
c 2.5 -2.5 bottomright
c 2 2 neartopright

route rest -> topright -> neartopright -> topleft -> bottomright -> rest ->
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        0.0003218       0.0003218       TravellingSalesManCalculation
       1        2.23e-05        2.23e-05        CalculateManhattenDistances

对于 800 个订单堆栈，在串行处理时是 1/3 秒。添加上面显示的订单堆叠时间，总计算时间不到一秒。您将不得不添加从您的服务器接收订单数据所花费的时间，然后将路由发送到 drivers 这将取决于您的服务器和网络，但我想您只需要几秒钟. （您还没有发布您的运行时要求！！！）

注意：我假设 driver 需要的只是一份按最佳顺序排列的送货地点列表，这样他们就可以使用自己的 GPS 设备找到下一次送货的详细路线。如果不是这种情况，并且 driver 需要详细的路由（左，右，第二个左...），那么这将花费更长的时间。请让我知道您希望它如何工作。

我已经将餐厅数量增加到 5000 家

C:\Users\James\code\pickup\bin>pickup.exe
Pickup
Orders per hour                20000
Order collection time mins     5
Restaurants                    5000
Pickup window mins             5
Maximum order preparation mins 15
1416 order stacks created
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        2.80843         2.80843         stack

由于订单率没有增加，每家餐厅的订单数量减少了，堆叠订单的机会也减少了 - 结果是计算时间显着增加。

食品配送中堆叠订单的算法（取货和送货）

Algorithm for stacked orders in food delivery (Pick up and deliveries)

algorithm

graph

or-tools

vehicle-routing