Pickup and delivery network segmentation using contiguous geographic clustering

This paper addresses the problem of partitioning a local service region into nonoverlapping work areas in which pickups and deliveries are made throughout the day. For a fleet of homogeneous vehicles, a given set of customers, and expected demand for service, the objective is to find the least number of work areas or clusters that satisfy a variety of geometric and capacity constraints. Using rectangles as the basic shape, each cluster must have an aspect ratio that falls within certain bounds, as well as meet load and time requirements dictated by the capacity of a vehicle and the working hours in a day, respectively. The latter requirement presents a unique hurdle because travel times are a function of the actual routes followed by the drivers, and are not known, even in a probabilistic sense, until the clusters are formed. A novel aspect of the paper is the method proposed for dealing with this uncertainty. The problem is modelled using a compact set-covering formulation and is solved with an adaptive column generation heuristic. Because it is not possible to efficiently represent all the constraints in algebraic form, thus allowing a Dantzig-Wolfe decomposition, a constructive approach was taken. The first step involved generating a subset of attractive clusters from seed customers scattered throughout the service region and then iteratively pricing them out to obtain a relaxed solution to the set-covering model. To find integer solutions, a three-phase variable fixing scheme was designed with the aim of balancing solution quality with runtimes. The full methodology was tested on six data sets provided by an internationally known express package carrier. The results showed that vehicle reductions averaging 7.6% could be realized by adopting the configurations derived from the proposed approach.