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

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
};

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

假设：

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

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

3。最初，工人被安置在他们的第一个服务房。

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

Answer 1

编辑： 经过思考我意识到这个问题可以简化为 Multiple Traveling Salesman Problem (specifically with time windows) and thus does not have a polynomial time solution. However, much work has been done on that problem and I'm sure you could find a suitable algorithm to tailor to your needs. Here's a 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 作为路径中的下一个节点（确保工作人员只会在开始时间之后到达）

确切开始时间

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

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

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

Best solution to dispatch order to hourly-paid worker?

algorithm

bigdata

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