Optimal solutions for routing problems with profits

C. Archetti; N. Bianchessi; M. G. Speranza

doi:10.1016/j.dam.2011.12.021

Optimal solutions for routing problems with profits

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

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	547-557
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	161
Issue number	4-5
DOIs	https://doi.org/10.1016/j.dam.2011.12.021
Publication status	Published - 1 Mar 2013

Keywords

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

Access to Document

10.1016/j.dam.2011.12.021

Persistent URL (handle)

Persistent link

Cite this

@article{657462dcf3084b6ca1fbafa5221620fb,

title = "Optimal solutions for routing problems with profits",

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

keywords = "Branch-and-price, Capacitated Profitable Tour Problem, Capacitated Team Orienteering Problem, Heuristic, Profits, Routing",

author = "C. Archetti and N. Bianchessi and Speranza, {M. G.}",

year = "2013",

month = mar,

day = "1",

doi = "10.1016/j.dam.2011.12.021",

language = "English",

volume = "161",

pages = "547--557",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "4-5",

}

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

SN - 0166-218X

VL - 161

SP - 547

EP - 557

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 4-5

ER -

Optimal solutions for routing problems with profits

Abstract

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this