In this paper, we consider the orienteering problem with hotel selection (OPHS) and introduce an additional cap on the available budget, frequently experienced in practice but neglected in the literature. We present a heuristic solution approach for the modified problem configuration, which comprises the construction of initial solutions and the improvement of those solutions using a multi-start VNS heuristic with adaptive adjustment. Within computational studies on adjusted benchmark data, we evaluate the impact of the considered budget constraint by comparing the results of the original OPHS with the results of its budget constraint extension. Further, we show the efficiency of the proposed metaheuristic.