Orienteering Problem (OP)

A single vehicle is stationed at a depot and must depart from it, visit a subset of cities, and return to the depot, forming a closed tour. There are n cities in total, including the depot, which is designated as city 1. Every pair of distinct cities is connected by a direct link whose travel time is known, nonnegative, and symmetric, meaning the time to travel between any two cities is the same in either direction. Each city other than the depot has an associated nonnegative prize value; the depot has a prize of zero. All prizes, travel times, and the time budget are integers.

The vehicle must complete its tour within a given maximum total travel time. The tour must start and end at the depot, and every city on the tour is visited exactly once. The tour must form a single connected cycle passing through the depot; that is, every visited city other than the depot must be reachable from the depot along the edges of the tour without passing through any unvisited city, which prevents the solution from decomposing into disconnected subtours. A visited city is entered and exited exactly once, meaning exactly two links of the tour are incident to it. An unvisited city has no tour links incident to it. The tour must contain at least three cities (including the depot), so trivial back-and-forth trips between two cities are not permitted.

The planner must decide which subset of cities to include in the tour and which links to traverse. The goal is to maximize the total prize collected, defined as the sum of the prize values of all visited cities, subject to the requirement that the sum of travel times along all links used in the tour does not exceed the maximum allowed travel time.