2
$\begingroup$

This is a real world problem, which due to some specific aspects of it I am having a hard time finding relevant literature for it.

I am looking for either an algorithm, or a pointer to relevant paper(s) describing a solution. I'm assuming one was already published, but I am just fumbling with my search terms.

Problem statement: I have many sites across town in which IoT hardware is deployed. Every day, a team of engineers need to service some subset of these sites. The time which an engineer would need to spend in a site to service it is a constant determined by today's schedule, and is not dependent of the engineer.

All engineers must start at the depot at the start of the day, and return to it at the end of the day, but for any given day, the number of engineers vary, and the number of hours any one engineer is rostered for might also vary.

How do I assign ordered lists of sites to different engineers in order to minimise the total time spent outside of the depo?

To put formally: if I have a graph with weighted edges, and weighted vertices, and a list of N max weights, how do I find N loops, all containing a specific vertex v_0, and each uniquely corresponding to a specific max weight, and not exceeding it, such that each vertex other than v_0 is visited exactly once, and the total weight across all loops is minimised (where the weight of the loop is defined as the total weight of all edges, and vertices which are part of it)?

$\endgroup$
5
  • $\begingroup$ What determines the time it takes an engineer to service a site? You say it depends on "today's schedule", but I am wondering whether that is really accurate. It depends on what other sites the engineer is also visiting, and what sites other engineers are visiting? Seems hard to imagine. Do you mean that the time it takes to service a site depends on the date? $\endgroup$
    – D.W.
    Nov 15 at 18:54
  • $\begingroup$ In the last paragraph, the array of weights doesn't seem to be used. Did you mean that to constrain which loops are allowable? What is meant by a "max weight"? $\endgroup$
    – D.W.
    Nov 15 at 18:56
  • $\begingroup$ The time it takes to service a site is completely independent. It is not affected, by other sites, other engineers, or the path taken to get there. As an example, let's say a particular site requires a service of type X, which takes 30 minutes, on the third Tuesday of every month. Then on the third Tuesday of every month, the schedule would include site X, with a weight of 30 minutes. $\endgroup$
    – Itamaram
    Nov 16 at 5:45
  • $\begingroup$ @D.W. I've edited the question to hopefully clarify it, I'm not sure I've done a great job. This is indeed an additional constraint, that there is a 1-to-1 mapping between loops and max weights, such that no loop exceeds its max weight $\endgroup$
    – Itamaram
    Nov 16 at 5:52
  • $\begingroup$ What does "not exceeding it" mean? The total weight of each loop must not exceed the corresponding max weight? Something other than that? $\endgroup$
    – D.W.
    Nov 16 at 5:54

1 Answer 1

1
$\begingroup$

The problem is NP-hard: the special case of $N=1$ is the traveling salesman problem. Therefore, you can't expect any efficient algorithm that will always work.

A reasonable approach in practice is to use integer linear programming (ILP). The problem you are describing could be viewed as basically an operations research problem, and operations research makes widespread use of ILP solvers. The basic idea is to introduce zero-or-one integer variables $x_{i,j,(u,v)}$, which will be 1 if the $i$th loop uses the edge $(u,v)$ as the $j$th step of the loop, or 0 otherwise. Now we can express all the constraints required for this to form a valid solution to the problem using linear inequalities. For instance:

  • Forms a valid path that ends at $v_0$: $0 \le \sum_u x_{i,j,(u,v)} = \sum_w x_{i,j+1,(v,w)} \le 1$ for all $v \ne v_0$, and $\sum_w x_{i,j+1,(v_0,w)} = 0$.

  • Starts at $v_0$: $\sum_w x_{i,1,(v_0,w)}=1$.

  • Forms a loop: $\sum_j \sum_u x_{i,j,(u,v_0)}=1$.

  • Each loop respects the max-weight constraint: $\sum_j \sum_{u,v} \text{wt}(u,v) x_{i,j,(u,v)} \le \text{maxwt}[i]$.

  • Each vertex is visited by exactly one loop: $\sum_{i,j,u} x_{i,j,(u,v)} = 1$ for every $v \ne v_0$.

  • Minimize total cost: minimize $\sum_{i,j,u,v} \text{wt}(u,v) x_{i,j,(u,v)}$.

You might need to adjust some of the details above to exactly match your problem formulation, but hopefully this gives you the idea. If your problem size is fairly small (the graph is fairly small, $N$ is fairly small), then an off-the-shelf ILP solver might be able to solve this. If you are dealing with large problem instances, it might be infeasible to find the optimal solution, and you might need to resort to other approaches, like heuristics or approximation algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.