TY - JOUR
T1 - Optimal solutions for routing problems with profits
AU - Archetti, C.
AU - Bianchessi, N.
AU - Speranza, M. G.
PY - 2013/3/1
Y1 - 2013/3/1
N2 - 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.
AB - 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.
KW - Branch-and-price
KW - Capacitated Profitable Tour Problem
KW - Capacitated Team Orienteering Problem
KW - Heuristic
KW - Profits
KW - Routing
UR - http://www.scopus.com/inward/record.url?scp=84873411143&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84873411143&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2011.12.021
DO - 10.1016/j.dam.2011.12.021
M3 - Article
AN - SCOPUS:84873411143
VL - 161
SP - 547
EP - 557
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
IS - 4-5
ER -