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.
Optimal solutions for routing problems with profits / C. Archetti, N. Bianchessi, M.G. Speranza. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 161:4-5(2013), pp. 547-557. [10.1016/j.dam.2011.12.021]
Optimal solutions for routing problems with profits
N. Bianchessi;
2013
Abstract
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Optimal-solutions-for-routing-problems-with-profits_DAM-12.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
216.96 kB
Formato
Adobe PDF
|
216.96 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
