Premium
Incomplete service and split deliveries in a routing problem with profits
Author(s) -
Archetti Claudia,
Bianchessi Nicola,
Speranza M. Grazia,
Hertz Alain
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21529
Subject(s) - orienteering , heuristics , computer science , vehicle routing problem , mathematical optimization , operations research , profit (economics) , constraint (computer aided design) , service (business) , routing (electronic design automation) , mathematics , business , computer network , economics , microeconomics , marketing , geometry
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. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 135–145 2014