As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning algorithm at least make sure that every kid gets a gift once in a while while Santa also serves as many kids as possible each year?
Consider a complete graph with real, positive weights and a constant $k$. We want to solve a variant of the Travelling Sales Person problem:
Is there a circular route of length at most $k$ that serves more than $m$ nodes?
The optimisation version would be:
Maximise the number of nodes that can be served with a circular route of length at most $k$.
This is motivated by real-world limitations on routes: Santa has one night to deliver as many gifts as possible, a sales person has eight hours for one day's route, and so on.
The first, but not final question is: how hard is this problem? Let's assume we can start at any node, but that should not make too much of a difference.
Now, in order to model fairness, let's assume there are $N$ nodes and we can visit at most $M$ with every tour. Ideally, we would want that every node is visited $t\cdot\frac{M}{N}$ times across $t$ efficient tours. Since there may be bottleneck nodes that have to be visited more often in order to ensure routes visit many nodes, some will inevitably have to be visited less often. That also excludes the trivial approximation of removing once visited nodes until all have been visited.
So, here is the final question. Let $T$ be the number of tours needed until all nodes have been visited by efficient $k$-tours. How can we algorithmically determine the minimal value of $T$ (and all the necessary routes)? How complex is this problem?
I guess this is really a multi-criterial problem: each tour should visit as many nodes as possible while we want to keep tours as disjoint as possible.
