Hexaly, Gurobi, OR-Tools on the Team Orienteering Problem (TOP)

Benchmark Transportation Routing

Maxime Optimization Scientist February 4, 2025

In the Team Orienteering Problem (TOP), we define start and end points and a set of locations, each with an associated prize. The goal is to determine n disjoint paths from the start point to the end through a subset of locations that maximizes the sum of the collected prizes while respecting a limit on the traveled distance. For the instance of our benchmark, no feasible solution exists where all points are visited due to the travel distance limit. Therefore, the best subset of points to visit needs to be determined.

On the Team Orienteering Problem (TOP), Hexaly reaches a 0.3% average gap to the best known solutions in 1 minute of running time on the Chao benchmark and a 0.7% average gap on the Dang benchmark. Gurobi and OR-Tools find good solutions for small-scale instances but quickly struggle to find quality solutions as the size increases.

Input data

The instances used to compare the three solvers are from two sets of academic instances. The first set was taken from Chao et al. and contains 157 instances with a number of customers varying from 64 to 102. The second set was introduced by Dang et al. and contains 82 instances with a number of customers ranging from 102 to 401.

Mathematical models for the Team Orienteering Problem (TOP)

Gurobi model

The results reported for Gurobi are obtained by running the MILP formulation presented in Hammami et al.

OR-Tools model

The OR-Tools model is implemented in C++. It comes from its documentation and uses the Vehicle Routing API with callbacks for the distance matrix. It uses routing dimensions to handle the maximum duration constraint and disjunctions to allow dropping some customers.

Hexaly model

The Hexaly model for the Team Orienteering Problem (TOP) uses one list variable per truck. We ensure the customers are not visited more than once thanks to a disjoint constraint. We compute the distance traveled by the trucks using a lambda function applied along the lists.

function model() {
    // list variables: ordered set of customers visited by each truck
    routes[k in 0...nbTrucks] <- list(nbCustomers);

    // each customer can be visited at most by one truck
    constraint disjoint[k in 0...nbTrucks](routes[k]);
    for [k in 0...nbTrucks] {
        local route <- routes[k];
        local c <- count(route);

        // Profit collected by the truck
        routeProfit[k] <- sum(0...c, i => profit[route[i]]);

        // Distance travelled by the truck
        routeDistances[k] <- sum(1..c-1, i => distance[route[i - 1]][route[i]])
                + (c > 0 ? (distanceFromInitialDepot[route[0]] + distanceToFinalDepot[route[c - 1]]) : 0);
        constraint routeDistances[k] <= maxRouteDuration;        
    }

    // totalProfit collected
    totalProfit <- sum[k in 0...nbTrucks](routeProfit[k]);
    maximize totalProfit
}

Hexaly, Gurobi, OR-Tools results on the Team Orienteering Problem (TOP)

We compare the three solvers’ performance within 1 minute of running time. We use Hexaly 13.5, Google OR-Tools 9.11, and Gurobi 11.0, all with default parameters. The OR-Tools search strategy is set to the recommended one: guided local search. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM.

The table below presents the gap, expressed in %, to the best solutions known in the literature, also called state-of-the-art (SOTA) solutions. For the sake of readability, we grouped the instances by size. For each group, the gap reported in the table corresponds to the arithmetic mean of gaps in % in all instances of the group.

Hexaly finds solutions with gaps to the best known solution lower than 3% for all instances of the two benchmarks in less than 1 minute. Gurobi and OR-Tools find good solutions for instances with less than 70 points but struggle to find quality solutions as the size increases.

Conclusion

Hexaly offers a concise and straightforward approach to the Team Orienteering Problem (TOP) based on “list” decision variables. The resulting model is highly scalable and provides much better solutions than Gurobi and OR-Tools on the Team Orienteering Problem (TOP) instances.