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. [10.1002/net.21529]
Incomplete service and split deliveries in a routing problem with profits
N. Bianchessi;
2014
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
split_top_incomplete_final_r1.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
298.35 kB
Formato
Adobe PDF
|
298.35 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.