Optimal solutions for routing problems with profits

C. Archetti*, N. Bianchessi, M. G. Speranza

*Corresponding author for this work

    Research output: Contribution to JournalArticleAcademicpeer-review


    In this paper, we present a branch-and-price algorithm to solve two well-known vehicle routing problems with profits, the Capacitated Team Orienteering Problem and the Capacitated Profitable Tour Problem. A restricted master heuristic is applied at each node of the branch-and-bound tree in order to obtain primal bound values. In spite of its simplicity, the heuristic computes high quality solutions. Several unsolved benchmark instances have been solved to optimality.

    Original languageEnglish
    Pages (from-to)547-557
    Number of pages11
    JournalDiscrete Applied Mathematics
    Issue number4-5
    Publication statusPublished - 1 Mar 2013


    • Branch-and-price
    • Capacitated Profitable Tour Problem
    • Capacitated Team Orienteering Problem
    • Heuristic
    • Profits
    • Routing


    Dive into the research topics of 'Optimal solutions for routing problems with profits'. Together they form a unique fingerprint.

    Cite this