Selected Problems

The Team Orienteering Problem (TOP) and the Capacitated Team Orienteering Problem (CTOP)

In the TOP, a fleet of vehicles is given with a maximum duration constraint on the route of each vehicle. The objective is to maximize the total collected profit while satisfying duration constraints. In the CTOP, a demand is associated with each customer and vehicles have a maximum capacity. The objective is to maximize the total collected profit while satisfying duration and capacity constraints. In the CTOP with Incomplete Service (CTOP-IS), a customer can be served only partially but a single visit is allowed to each customer, while in the CTOP with Split Deliveries each customer can be visited by more than one vehicle. In the latter problem, there can be either case of a complete service required (SDCTOP) or the case where an incomplete service is allowed (SDCTOP-IS).

The Capacitated Profitable Tour Problem (CPTP)

In the CPTP, a fleet of vehicles is given and the objective is to maximize the difference between the total collected profit and the travelling cost. No side constraint is considered on vehicle routes.

The Clustered Orienteering Problem (COP)

The OP is the single vehicle version of the TOP. In the COP, customers are clustered in groups and a profit is associated with each group. The profit is collected only if all customers in the group are served. The objective is to find the vehicle route which maximizes the total collected profit while satisfying the maximum duration constraints.

The Directed Profitable Rural Postman Problem (DPRPP)

In the DPRPP customers are arcs of a directed graph. A single vehicle is available and the objective is to find the route that maximizes the difference between the total collected profit and the travelling cost. No side constraint is imposed on the route.

The Undirected Capacitated Arc Routing Problem with Profits (UCARPP)

In the UCARPP customers are edges of an undirected graph. A profit and a demand are associated with each customer. A fleet of vehicles is available and each vehicle route has to satisfy both capacity and maximum duration constraints. The objective is to find the set of routes that maximizes the total collected profit.

The Team Orienteering Arc Routing Problem (TOARP)

In the we are given a directed graph. Two subset of arcs are defined "required arcs", that have to be traversed, and "profitable arcs" that, is traversed, give a profit. A fleet of vehicles is available and each vehicle route has to satisfy a maximum duration constraint. The objective is to find the set of routes that maximizes the total collected profit.