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

Nicola Bianchessi, Renata Mansini, M. Grazia Speranza

    Research output: Contribution to JournalArticleAcademicpeer-review

    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

    Fingerprint

    Travel time
    Profitability
    Polynomials
    Optimality
    Benchmark
    Profit
    Connectivity

    Keywords

    • branch-and-cut algorithm
    • Team Orienteering Problem
    • two-index mathematical formulation

    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",

    }

    Bianchessi, N, Mansini, R & Speranza, MG 2018, 'A branch-and-cut algorithm for the Team Orienteering Problem' International Transactions in Operational Research, vol. 25, no. 2, pp. 627-635. DOI: 10.1111/itor.12422

    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 JournalArticleAcademicpeer-review

    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 -

    Bianchessi N, Mansini R, Speranza MG. A branch-and-cut algorithm for the Team Orienteering Problem. International Transactions in Operational Research. 2018 Mar 1;25(2):627-635. Available from, DOI: 10.1111/itor.12422