Prize-Collecting (Team Orienteering)

In prize-collecting problems (also called Team Orienteering Problem — TOP), not all customers need to be visited. Each customer carries a profit — a prize for visiting — and the solver weighs every prize against the cost of collecting it.

How It Works

• Each customer has a profit field: the prize for visiting, in the objective's units — with the default weights, the units of your duration matrix
• A customer is visited when its prize outweighs the extra travel cost (and any other cost) of reaching it; otherwise it is skipped
• Constraints (capacity, time windows, duration limits) still apply to the customers that are visited
• Prize-collecting is a property of the whole instance: set profit on every customer or on none — a mix raises a ValidationError

This is useful when you have more customers than you can profitably serve and want the solver to choose.

Note

Profit values must be non-negative. Make them comparable to your travel costs: with durations in seconds, profit=1800 means a customer is worth up to a 30-minute detour. Prizes that are tiny relative to typical detours will simply cause everyone to be skipped.

Example

from tqrouting import TQRouter, VRPInstance, Customer, VehicleType, Location

router = TQRouter()

# Durations in seconds; prizes therefore in "seconds worth of detour".
instance = VRPInstance(
    customers=[
        Customer(location=Location(matrix_id=1), profit=1500),
        Customer(location=Location(matrix_id=2), profit=500),
        Customer(location=Location(matrix_id=3), profit=2400),
        Customer(location=Location(matrix_id=4), profit=250),   # far out, small prize
        Customer(location=Location(matrix_id=5), profit=900),
    ],
    fleet=[
        VehicleType(
            start_location=Location(matrix_id=0),
            end_location=Location(matrix_id=0),
            max_duration="01:00:00",       # 1-hour budget also limits what fits
            n_vehicles=2,
        ),
    ],
    duration_matrix=[
        [0, 600, 1050, 750, 2400, 900],
        [600, 0, 450, 900, 2100, 1050],
        [1050, 450, 0, 600, 1800, 750],
        [750, 900, 600, 0, 1950, 300],
        [2400, 2100, 1800, 1950, 0, 2250],
        [900, 1050, 750, 300, 2250, 0],
    ],
)

solution = router.solve(instance, time_limit=2)

print(f"Total profit: {solution.total_profit}")
print(f"Customers visited: {solution.total_n_visits} / 5")
print(f"Skipped: {solution.unvisited_customers}")

for route in solution.routes:
    customers = [v.customer_id for v in route.visits]
    print(f"  Route {route.id}: profit = {route.route_profit}, duration = {route.route_duration:.0f} s, customers {customers}")

Output:

Total profit: 5300.0
Customers visited: 4 / 5
Skipped: [3]
  Route 0: profit = 5300.0, duration = 2850 s, customers [0, 1, 2, 4]

Customer 3 (prize 250) sits at least 30 minutes from every other stop: reaching it costs an hour-long detour, far more than its prize, so the solver leaves it unvisited. The other four fit into one 47-minute route, and the second vehicle stays home.

Profit Weight

profit_weight converts your profit units into objective units. Keep the default 1.0 when prizes are already expressed in the objective's units, as above.

Set it when prizes live in a different currency. For example, prizes in EUR against durations in seconds, with driver time at 36 €/h (= 0.01 €/s): one euro justifies 1 / 0.01 = 100 seconds of extra driving:

# profit values are EUR; 1 € of prize is worth up to 100 s of detour
solution = router.solve(instance, profit_weight=100)

Reading Results

When profit is used, the solution includes additional fields:

Field	Description
solution.total_profit	Total profit collected across all routes
solution.unvisited_customers	IDs of the customers the solver chose not to visit
route.route_profit	Profit collected by a specific route

print(f"Skipped customers: {solution.unvisited_customers}")

When custom customer IDs are set on the instance, unvisited_customers contains those IDs.

---

Interactive Example

See the objectives notebook for runnable prize-collecting examples.