The split delivery capacitated team orienteering problem

Journal Article


In this article, we study the capacitated team orienteering problem where split deliveries are allowed. A set of potential customers is given, each associated with a demand and a profit. The set of customers to be served by a fleet of capacitated vehicles has to be identified in such a way that the profit collected is maximized, while satisfying constraints on the maximum time duration of each route and the vehicle capacity constraints. When split deliveries are allowed, each customer may be served by more than one vehicle. We show that the profit collected by allowing split deliveries may be as large as twice the profit collected under the constraint that each customer has to be served by one vehicle at most. We then present a branch‐and‐price exact algorithm and a hybrid heuristic. We show the effectiveness of the proposed approaches on benchmark instances and on a new set of instances that allow us to computationally evaluate the impact of split deliveries. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 16–33 2014

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.