algorithm - 将订单发送给计时工的最佳解决方案？

Question

伙计们我遇到一道算法题，不是作业，只是一个网站的题。说明如下:

1.家政中介公司拥有两大资源:数以百万计的小时工和家政订单。

2。计时工只有一个 id。

3.一个内务订单可以这样描述:

struct order_head {
    uint32_t id;  // order id
    double pos_x; // (pos_x, pos_y) indicate the house's position. pos_x is the house's x-coordinate
    double pos_y; // pos_y is the house's y-coordinate
    int8_t time_len; // The house cleaning time required the customer.
    int8_t has_start_time; // Does the customer designate the serving time interval.
    int32_t start_time; // If the customer designate the serving time, this indicate the start_time of the time interval. (start_time, start_time+time_len) indicate the serving time
};

目标:
从海量数据来看，公司安排计时工接单，所有 worker 的总工作时间越大算法越好。

假设:

1.一天的工作时间为08:00~18:00，10小时。

2。 worker 按小时计酬，比如 30 美元/小时，但必须在从结束工作的房子到开始工作的房子的交通上浪费一些时间。两栋房子之间越远，浪费的时间就越多。

3.最初， worker 们被安置在他们的第一个服务室。

这个问题我想了好几天，但我想不出最适合这个问题的传统算法。它可能与大数据处理算法有关，但我不确定。有人能想到这个问题吗？
谢谢!

Answer 1

编辑: 考虑之后，我意识到这个问题可以简化为 Multiple Traveling Salesman Problem (specifically with time windows)因此没有多项式时间解。但是，在这个问题上已经做了很多工作，我相信您可以找到合适的算法来满足您的需求。这是一个 SO question that might help out with that .
.

或者，这是我的自制算法:

可以使用图论和 Hamiltonian paths 来解决它:

• 首先创建一个directed graph来自工作，其中每个顶点都是一个工作，每对顶点之间有一条边uv，权重为u.time_len+travelTime(u,v)
• 然后必须找到 shortest Hamiltonian path这张图，花费时间 O(n²*2n)
• 在此之后，您只需使用一个 worker 遍历列表，直到累积了最大权重 < 10，然后继续下一个 worker
• 请注意您的初始权重将是第一个作业节点的时间成本

最短哈密顿路径算法注释:

• 您需要保留 weight/10 和 weight%10 变量
• 当 weight/10 增加 1 时，返回一个步骤并重做所有边缘权重减少 travelTime(u,v) (表示移动到一个新的 worker )
• 测试以确保 weight%10 大于或等于 u.start_time 时将 u 评估为路径中的下一个节点(确保 worker 只会在开始时间之后到达)

确切的开始时间

确切的开始时间(工作人员必须恰好在 start_time 到达，不能早于，不能晚于)会带来更多问题。这可以通过以下几种方式解决(尽管该解决方案现在可能不是最优的):

• 简单地改变 worker 在哈密顿路径上的起始位置
• 为每个确切的起始节点，创建一个 <10 的权重路径(如果方便，这可以包括其他确切的起始节点)。然后从图中删除所有这些节点及其关联的边，假设每条路径使用一个 worker ，并在剩余的图上继续使用原始算法