Data di Pubblicazione:
2013
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.
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.
Tipologia CRIS:
1.1 Articolo in rivista
Elenco autori:
Archetti, Claudia; Bianchessi, Nicola; Speranza, Maria Grazia
Link alla scheda completa:
Pubblicato in: