A branch‐and‐cut algorithm for the Team Orienteering Problem

• Date: 01 March 2018
• DOI: http://doi.org/10.1111/itor.12422
• Author: M. Grazia Speranza,Renata Mansini,Nicola Bianchessi
• Published date: 01 March 2018

Intl. Trans. in Op. Res. 25 (2018) 627–635

DOI: 10.1111/itor.12422

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A branch-and-cut algorithm for the Team Orienteering

Problem

Nicola Bianchessia, Renata Mansiniband M. Grazia Speranzac

aChair of Logistics Management, Gutenberg School of Management and Economics,

Johannes Gutenberg UniversityMainz, Jakob-Welder-Weg 9, D-55128 Mainz, Germany

bDepartment of Information Engineering, University of Brescia,via Branze 38, 25123 Brescia, Italy

cDepartment of Economics and Management, University of Brescia,C.da S. Chiara 50, 25122 Brescia, Italy

E-mail: nbianche@uni-mainz.de [Bianchessi]; renata.mansini@unibs.it [Mansini]; grazia.speranza@unibs.it [Speranza]

Received 24 August2016; received in revised form 14 January 2016; accepted 6 April 2017

Abstract

The Team Orienteering Problemaims at maximizing the total amount of profit collected by a fleet of vehicles

while not exceeding a predefined travel time limit on each vehicle. In the last years, several exact methods

based on different mathematical formulations were proposed. In this paper, we present a new two-index

formulation with a polynomial numberof variables and constraints. This compact formulation,reinforced by

connectivity constraints, was solved bymeans of a branch-and-cut algorithm. The total number of instances

solved to optimality is 327 of 387 benchmark instances, 26 more than anyprevious method. Moreover, 24 not

previously solved instances were closed to optimality.

Keywords:Team Orienteering Problem; two-index mathematical formulation; branch-and-cut algorithm

1. Introduction

The Team Orienteering Problem (TOP) can be defined over a complete directed graph G=(V,A)

with node set V={0,...,n+1}and arc set A={(i,j):i= n+1;j= 0;i= j;i,j∈V}. The node

set Vcontains nodes 0 and n+1, representing the initial and final depots, respectively, and the set

N={1,...,n}, indicating the ncustomers. Each node i∈Vhas a profit pi, with p0=pn+1=0. A

nonnegative travel time tij, with t0,n+1=0, is associated with each arc (i,j)∈A. Travel times satisfy

the triangle inequality. A fleet Fof midentical vehicles is available to serve the customers. When a

customer is visited, the corresponding profit is collected by the vehicle serving the customer. Each

customer cannot be visited more than once. Each routeis a path from node 0 to node n+1ingraph

G. Moreover, the duration of the route associated with each vehicle cannot exceed a predefined

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.