On Solving the Set Orienteering Problem

Abstract

In the Set Orienteering Problem, a single vehicle, leaving from and returning to a depot, has to serve some customers, each one associated with a given spacial location. Customers are grouped in clusters and a given prize is collected once a customer in a cluster is visited. The prize associated with a cluster can be collected at most once. Travel times among locations are provided, together with a maximum available mission time, which normally makes it impossible to visit all the clusters. The target is to design a route for the vehicle that maximizes the total prize collected within the given time limit. In this study, building on the recent literature, we present new preprocessing rules and a new constraint programming model for the problem. Thanks to the symmetry exploitation carried out by the constraint programming solver, new state-of-the-art results are established.

Keywords

• set orienteering problem
• constraint programming
• preprocessing rules
• exact methods