Best solution to dispatch order to hourly-paid worker?

Question

guys I have met a problem of algorithm, it is not a homework, but only a question from a site. It is described as below:

1. There is a housekeeping intermediary company which have two tremendous resources: millions of hourly-paid workers and housekeeping orders.

2. A hourly-paid worker only have an id.

3. A house-keeping order can be described like this:

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

Target:
From the tremendous data, the company schedule hourly-paid workers to pick orders, the total working time of all workers is larger the algorithm is better.

Assumption:

1. The working time of a day is 08:00 ~ 18:00, 10 hours.

2. The workers are hourly-paid say 30$/hour, but some time must be wasted in traffic from the end-worked house to start-to-work house. The farther between the two houses, the more time wasted.

3. Initially, the workers are placed at their 1st serving house.

I have thought of the problem for some days, but I can not think out a traditional algorithm best suited this problem. It may be relate to big data processing algorithms, but I am not sure. Could someone have good thought of this problem?
Thanks!

Answer 1

EDIT: After thinking about it I realized this problem could be reduced to the 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.
.

Alternatively, here's my home-rolled algorithm:

One could solve it using graph theory and Hamiltonian paths:

• First create a directed graph from the jobs, where each vertex is a job and there is an edge between each pair of vertices uv with weight u.time_len+travelTime(u,v)
• Then one must find the shortest Hamiltonian path of this graph, taking time O(n²*2n)
• After this, you simply traverse the list using a worker until max weight < 10 has been accumulated and then moving on to the next worker
• Note your initial weight will be the time cost of the first job node

Notes on the shortest Hamiltonian path algorithm:

• You'll need to keep weight/10 and weight%10 variables
• When weight/10 increases by 1, go back a step and redo it with all edge weights reduced by travelTime(u,v) (represents moving to a new worker)
• Test to ensure weight%10 is greater than or equal to u.start_time when evaluating u as the next node in your path (ensures worker will only arrive after start time)

Exact Start Times

An exact start time (worker must be there at exactly start_time, no earlier, no later) presents a bit more of a problem. This can be resolved (though the solution will now potentially be sub-optimal) several ways:

• Simply shift the worker's start location on the Hamiltonian path
• For each exact start node, create a <10 weight path (this can include other exact start nodes if convenient). Then remove all these nodes and their associated edges from the graph, assume one worker used for each path, and proceed with the original algorithm on the remaining graph