A Distributed Cluster-Based Approach for Pick-Up Services

This paper deals with the routing problem of pick-up and delivery services considering time windows and capacitated vehicles. In order to consider large real problems, this paper proposes a distributed vehicle routing problem (VRP) with time windows, based on cluster first, route second methods. First, by using a graph partitioning solved by local integer linear programing problems, the vehicles autonomously generate a number of clusters equal to the number of available vehicles. Second, each vehicle solves a traveling salesman problem with time windows to compute its route in the assigned cluster. The method can be applied by the vehicles for both planning the workday of the pick-up services and adapting the routing plan to manage the ongoing requests. Some benchmark problems are generated and solved by the distributed algorithm and compared with the solution obtained by the exact approach. Moreover, a real case study involving a courier service shows the efficiency of the solution method.