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

Nicola Bianchessi, Renata Mansini, M. Grazia Speranza

Research output: Contribution to journalArticle

Abstract

The Team Orienteering Problem aims 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 number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch-and-cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.

LanguageEnglish
Pages627-635
Number of pages9
JournalInternational Transactions in Operational Research
Volume25
Issue number2
DOIs
StatePublished - 1 Mar 2018

Cite this

Bianchessi, Nicola ; Mansini, Renata ; Speranza, M. Grazia. / A branch-and-cut algorithm for the Team Orienteering Problem. In: International Transactions in Operational Research. 2018 ; Vol. 25, No. 2. pp. 627-635
@article{cb1d2d41030540079174ad70c221b40f,
title = "A branch-and-cut algorithm for the Team Orienteering Problem",
abstract = "The Team Orienteering Problem aims 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 number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch-and-cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.",
keywords = "branch-and-cut algorithm, Team Orienteering Problem, two-index mathematical formulation",
author = "Nicola Bianchessi and Renata Mansini and Speranza, {M. Grazia}",
year = "2018",
month = "3",
day = "1",
doi = "10.1111/itor.12422",
language = "English",
volume = "25",
pages = "627--635",
journal = "International Transactions In Operational Research",
issn = "0969-6016",
publisher = "Blackwell Publishing",
number = "2",

}

A branch-and-cut algorithm for the Team Orienteering Problem. / Bianchessi, Nicola; Mansini, Renata; Speranza, M. Grazia.

In: International Transactions in Operational Research, Vol. 25, No. 2, 01.03.2018, p. 627-635.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A branch-and-cut algorithm for the Team Orienteering Problem

AU - Bianchessi,Nicola

AU - Mansini,Renata

AU - Speranza,M. Grazia

PY - 2018/3/1

Y1 - 2018/3/1

N2 - The Team Orienteering Problem aims 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 number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch-and-cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.

AB - The Team Orienteering Problem aims 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 number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch-and-cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.

KW - branch-and-cut algorithm

KW - Team Orienteering Problem

KW - two-index mathematical formulation

UR - http://www.scopus.com/inward/record.url?scp=85019618698&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85019618698&partnerID=8YFLogxK

U2 - 10.1111/itor.12422

DO - 10.1111/itor.12422

M3 - Article

VL - 25

SP - 627

EP - 635

JO - International Transactions In Operational Research

T2 - International Transactions In Operational Research

JF - International Transactions In Operational Research

SN - 0969-6016

IS - 2

ER -