In this article, we study a variant of the capacitated team orienteering problem, that is the problem where a fleet of vehicles, each with a constraint on the time available, is given to serve profitable customers with the objective of maximizing the collected profit. We study the variant where customers may be only partially served (incomplete service) and, if beneficial, also by more than one vehicle (split deliveries). We will analyze the maximum theoretical increase of the profit due to the incomplete service and to the split deliveries. We also computationally measure such increase on a set of instances, by means of an exact algorithm on small/medium size instances and of two heuristics on instances of larger size.
Incomplete service and split deliveries in a routing problem with profits / C. Archetti, N. Bianchessi, M.G. Speranza, A. Hertz. - In: NETWORKS. - ISSN 0028-3045. - 63:2(2014), pp. 135-145.
|Titolo:||Incomplete service and split deliveries in a routing problem with profits|
|Parole Chiave:||routing problems with profits; worst-case analysis; branch-and-price algorithm; tabu search; split delivery|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
Settore MAT/09 - Ricerca Operativa
|Data di pubblicazione:||2014|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1002/net.21529|
|Appare nelle tipologie:||01 - Articolo su periodico|