A salesman is employed by a large corporation. He has a $n$ cities to visit, connected by roads, forming a graph. But as travel takes a lot of time, he has to pick hotels between visits. He cannot take any hotel he wishes; rather there are precisely $m$ hotels where he may rest.
He has to plan his travel in such way that after visiting $p$ cities, he has to visit a hotel. We may generalise it to say he has to visit $q$ different hotels. (Maybe it will be traveling celebrity problem?)
So basically he has a graph $G(E,V)$, where $E$ are the edges, $V$ the nodes, and two sets of nodes: $C$ (cities) and $H$ (hotels) with $C \cup H = V$ and $|C|=n$, $|H|=m$. Find a path in the graph starting at one of the $C$ nodes, ending at a different $C$ node and forming pattern $(p,q)$, $p$ nodes from set $C$, then $q$ nodes from set $H$, then repeat. The path may not visit every $H$ element and it may visit some of $H$ elements many times, but it has to visit every $C$ node once.
So it is like finding a Hamiltonian path but with "rests".
- Does this problem have a name or it is something new?
- In what cases does it have a solution? It probably depends both on the numbers of nodes $p$, $q$, and where on the graph they are located.
- How can we find the shortest path, ignoring hotel costs?
- What is a way to find an optimal solution (cheapest travel) if every hotel cost is the same?
- What is the optimal solution when costs of hotels are different?