Evaluating two new heuristics for constructing customer clusters in a VRPTW with multiple service workers

The vehicle routing problem with time windows and multiple service workers is a novel approach allowing to efficiently deliver goods to customers in congested cities with limited parking space. Two steps have to be performed in order to solve this problem. First, each customer has to be assigned to a cluster. Thereafter, delivery routes from a central depot to these clusters are constructed. Hence, in this context, a cluster is denoted by a common parking location and a group of customers that is compiled sensibly in terms of location and time windows. This paper discusses the requirements for creating customer clusters that allow efficient routes. It proposes a set of representative benchmark instances for the combined clustering and routing problem. Finally, two cluster construction heuristics are introduced and systematically compared using a deterministic route construction heuristic.