The bus sightseeing problem

The basic characteristic of vehicle routing problems with profits (VRPP) is that locations to be visited are not predetermined. On the contrary, they are selected in pursuit of maximizing the profit collected from them. Significant research focus has been directed toward profitable routing variants due to the practical importance of their applications and their interesting structure, which jointly optimizes node selection and routing decisions. Profitable routing applications arise in the tourism industry aiming to maximize the profit score of attractions visited within a limited time period. In this paper, a new VRPP is introduced, referred to as the bus sightseeing problem (BSP). The BSP calls for determining bus tours for transporting different groups of tourists with different preferences on touristic attractions. Two interconnected decision levels have to be jointly tackled: assignment of tourists to buses and routing of buses to the various attractions. A mixed-integer programming formulation for the BSP is provided and solved by a Benders decomposition algorithm. For large-scale instances, an iterated local search based metaheuristic algorithm is developed with some tailored neighborhood operators. The proposed methods are tested on a large family of test instances, and the obtained computational results demonstrate the effectiveness of the proposed solution approaches.