I have a scheduling problem.
I have a set A of Plumbers and a set B of clients.
A plumber can visit multiple clients. A plumber must also end the day back home where they started.
The goal is to schedule all the clients to be visited by exactly one plumber such that the sums of the paths the plumbers take is minimal.
Some things I've thought of.
- Bipartite graph and use Dijkstra's algorithm to try to find best paths.
- Use Voronoi diagrams and their duels to figure out which houses plumbers are near.
I think my problem is I have two sets of things and a lot of graph theory algorithms seem to be concerned with a single set.
I'm looking for sources that may help me understand a solution to this problem.
//Answers to comments I'm trying to keep this abstract,
there isn't a set in stone number of clients per day but for argument sake maybe 8?
For this example I want to consider a graph where all plumbers are connected to all clients, the weights of these paths correlate to their distance in real life.
- The part of this that makes it not a bipartite graph is that a plumber can go between clients directly.
There also isn't a set constraint on the number of days, however there will be I would like to find a solution with a fluid bound on this.
I see the concern with one plumber visiting all clients. The weights of the paths between clients should prevent this. Consider a plumber with clients in Seattle and a plumber with clients in Chicago. The transamerican path would not be efficient in this case.
I can understand your question in two different ways regarding how to compute the total length of path when a plumber visits multiple clients. So, let's say that plumber $P_1$ is going to first visit client $C_1$ and then client $C_2$. It is not clear from your question how the total distance that $P_1$ has to go is calculated. Is the distance calculated as $dist(P_1,C_1) + dist(C_1,C_2)$ (because the plumber goes from client $C_1$ directly to client $C_2$)? Or is it calculated as $dist(P_1,C_1) + dist(P_1,C_2)$ because the plumber does not go directly from $C_1$ to $C_2$ (maybe, after visiting $C_1$, it first goes back to the office and then goes to $C_2$).
So, based on how this is calculated, the problem can be either very hard or very easy.
(1) Assuming that the plumber goes from one client directly to another client, the problem becomes NP-hard and, so, you would not be able to find an easy algorithm to solve it (unless, of course, $P=NP$).
In order to see that this problem is indeed NP-hard, you only need to reduce Euclidean TSP to this problem which is very straightforward. Given a Euclidean TSP instance, generate an instance of this problem by making each city a client and only one plumber which would be the traveling salesperson. Since there is only one plumber, the total cost of serving clients is the length of path that the plumber needs to traverse. Also, since all clients need to be served, the plumber needs to visit all cities (as required by Euclidean TSP). Hence, the shortest path for serving all clients is also the shortest tour for the traveling salesman in TSP. Therefore, the problem is NP-hard.
(2) However, assuming that the plumber does not go directly from one client to another, the problem becomes very easy. Since every client has to be visited, it is best if the plumber who is closest to that client visits it. This way, each client contributes the shortest possible overhead to the total length of the paths that the plumbers have to take.
So, in this case, you can match each client with the plumber closest to it and be sure that you have found the optimal answer. You can either implement this simple algorithm directly or you can use a weighted bipartite matching algorithm for it. However, if you want to use the bipartite matching, you would need to multiply the number of plumbers because you allow a plumber to be matched by several clients simultaneously.