Metaheuristics for the Orienteering Problem with Hotel Selection

Formally, the Team Orienteering Problem with Hotel Selection (TOPHS) can be stated as follows: a set of n customer locations is given and each location i = s + 1, . . . , s + n is assigned a service or visiting timeTi and a score Si. The time Cij needed to travel from location i to j is known for all pairs of customer locations. The available time that each trip d = 1, . . . ,m takes is limited to a given time budget C. The goal is to determine a tour of maximal score, composed of m connected trips, that visits each location at most once. In this formulation, the number of trips m is not a decision variable, but a given parameter of the problem. Every trip should start and end in one of the available hotels i= 0, . . . , s. The starting and ending location of the tour (i.e. of the first and last trip respectively) are assumed to be identical and given (i = 0). This starting and ending location can also be used as a hotel during the tour. Clearly, the TOPHS is a generalization of the TOP, and is also NP-hard.

An appropriate algorithm should be designed tosolve this problem and possible variants in real-time. The algorithm(s)should be tested on (newly created) benchmark instances. This implies that the algorithm should be programmed (in VC++ ), extensively tested on problems with different sizes and characteristics and fine tuned to deal with real problems in an efficient way. In many cases, these problems require a solution immediately, which probably leads to (Meta) heuristic approaches. We look for quantitative results that support the design decisions and prove the quality of the designed method (model and algorithm).