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".

  1. Does this problem have a name or it is something new?
  2. 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.
  3. How can we find the shortest path, ignoring hotel costs?
  4. What is a way to find an optimal solution (cheapest travel) if every hotel cost is the same?
  5. What is the optimal solution when costs of hotels are different?
  • 2
    $\begingroup$ Any interest in Radmanesh et al., Solution of Traveling Salesman Problem with Hotel Selection in the framework of MILP-tropical optimization, American Control Conference (ACC), 2016, ieeexplore.ieee.org/document/7526547 ? Or Castro et al., The multiple travelling salesperson problem with hotel selection, RESEARCH PAPER 2014-030, Faculty of Applied Economics, University of Antwerp? $\endgroup$ – Gerry Myerson Dec 3 '17 at 21:43
  • 2
    $\begingroup$ Or Baltz et al., Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection, J Oper Res Soc (2015) 66: 615. doi.org/10.1057/jors.2014.17, link.springer.com/article/10.1057/jors.2014.17 ? Or Vansteenwegen et al., The Travelling Salesperson Problem with Hotel Selection, Journal of the Operational Research Society, Vol. 63, Issue 2, pp. 207-217, 2012, papers.ssrn.com/sol3/papers.cfm?abstract_id=1983831 ? $\endgroup$ – Gerry Myerson Dec 3 '17 at 21:49

Your Answer

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

Browse other questions tagged or ask your own question.