The capacitated team orienteering problem with incomplete service

Claudia Archetti; Nicola Bianchessi; M. Grazia Speranza

doi:10.1007/s11590-012-0559-4

The capacitated team orienteering problem with incomplete service

Claudia Archetti^*, Nicola Bianchessi, M. Grazia Speranza

^*Corresponding author for this work

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

Abstract

In this paper we study the capacitated version of the Team Orienteering Problem (TOP), that is the Capacitated TOP (CTOP) and the impact of relaxing the assumption that a customer, if served, must be completely served. We prove that the profit collected by the CTOP with Incomplete Service (CTOP-IS) may be as large as twice the profit collected by the CTOP. A computational study is also performed to evaluate the average increase of the profit due to allowing incomplete service. The results show that the increase of the profit strongly depends on the specific instance. On the tested instances the profit increase ranges between 0 and 50 %. We complete the computational study with the increase of the profit of the CTOP due to split deliveries, that is multiple visits to the same customer, and to split deliveries combined with incomplete service.

Original language	English
Pages (from-to)	1405-1417
Number of pages	13
Journal	Optimization Letters
Volume	7
Issue number	7
DOIs	https://doi.org/10.1007/s11590-012-0559-4
Publication status	Published - 1 Oct 2013

Keywords

Capacitated Team Orienteering Problem
Exact algorithms
Incomplete service
Split deliveries

Access to Document

10.1007/s11590-012-0559-4

Persistent URL (handle)

Persistent link

Cite this

@article{860f3cfad7e4435cbe8fd85985d53bb1,

title = "The capacitated team orienteering problem with incomplete service",

abstract = "In this paper we study the capacitated version of the Team Orienteering Problem (TOP), that is the Capacitated TOP (CTOP) and the impact of relaxing the assumption that a customer, if served, must be completely served. We prove that the profit collected by the CTOP with Incomplete Service (CTOP-IS) may be as large as twice the profit collected by the CTOP. A computational study is also performed to evaluate the average increase of the profit due to allowing incomplete service. The results show that the increase of the profit strongly depends on the specific instance. On the tested instances the profit increase ranges between 0 and 50 %. We complete the computational study with the increase of the profit of the CTOP due to split deliveries, that is multiple visits to the same customer, and to split deliveries combined with incomplete service.",

keywords = "Capacitated Team Orienteering Problem, Exact algorithms, Incomplete service, Split deliveries",

author = "Claudia Archetti and Nicola Bianchessi and Speranza, {M. Grazia}",

year = "2013",

month = oct,

day = "1",

doi = "10.1007/s11590-012-0559-4",

language = "English",

volume = "7",

pages = "1405--1417",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "7",

}

TY - JOUR

T1 - The capacitated team orienteering problem with incomplete service

AU - Archetti, Claudia

AU - Bianchessi, Nicola

AU - Speranza, M. Grazia

PY - 2013/10/1

Y1 - 2013/10/1

N2 - In this paper we study the capacitated version of the Team Orienteering Problem (TOP), that is the Capacitated TOP (CTOP) and the impact of relaxing the assumption that a customer, if served, must be completely served. We prove that the profit collected by the CTOP with Incomplete Service (CTOP-IS) may be as large as twice the profit collected by the CTOP. A computational study is also performed to evaluate the average increase of the profit due to allowing incomplete service. The results show that the increase of the profit strongly depends on the specific instance. On the tested instances the profit increase ranges between 0 and 50 %. We complete the computational study with the increase of the profit of the CTOP due to split deliveries, that is multiple visits to the same customer, and to split deliveries combined with incomplete service.

AB - In this paper we study the capacitated version of the Team Orienteering Problem (TOP), that is the Capacitated TOP (CTOP) and the impact of relaxing the assumption that a customer, if served, must be completely served. We prove that the profit collected by the CTOP with Incomplete Service (CTOP-IS) may be as large as twice the profit collected by the CTOP. A computational study is also performed to evaluate the average increase of the profit due to allowing incomplete service. The results show that the increase of the profit strongly depends on the specific instance. On the tested instances the profit increase ranges between 0 and 50 %. We complete the computational study with the increase of the profit of the CTOP due to split deliveries, that is multiple visits to the same customer, and to split deliveries combined with incomplete service.

KW - Capacitated Team Orienteering Problem

KW - Exact algorithms

KW - Incomplete service

KW - Split deliveries

UR - http://www.scopus.com/inward/record.url?scp=84884669427&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84884669427&partnerID=8YFLogxK

U2 - 10.1007/s11590-012-0559-4

DO - 10.1007/s11590-012-0559-4

M3 - Article

AN - SCOPUS:84884669427

SN - 1862-4472

VL - 7

SP - 1405

EP - 1417

JO - Optimization Letters

JF - Optimization Letters

IS - 7

ER -

The capacitated team orienteering problem with incomplete service

Abstract

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this