Integrating commercial and residential pickup and delivery networks: A case study

This paper presents a strategic analysis of the network design problem faced by pickup and delivery companies operating in metropolitan areas and serving two or more classes of customers. The focus is on a division that treats commercial and residential customers separately, a situation motivated by their respective geographic densities and the size and frequency of their demand. In constructing driver work areas, it is necessary to take into account expected demand, vehicle capacity, time on the road, and the aspect ratio of the individual territories. This leads to a capacitated clustering problem with side constraints that has been the subject of intense research over the last decade.Based on a previously developed column generation algorithm, a case study was conducted involving several scenarios that integrate the two networks to determine the extent of the resulting benefits. To no surprise, the analysis showed that a significant reduction in fleet size can be achieved when the two networks are either partially or fully combined. It also showed that small reductions with respect to current practice are possible when they are separately maintained with the added benefit that the geometry of the resultant clusters satisfies certain desirable properties with respect to their contours and aspect ratios.

► Comprehensive study evaluating network designs for different classes of customers.
► Sophisticated column generation algorithm used to determine near-optimal configurations.
► Results validated using data for three representative cities in the U.S.
► Substantial savings to the sponsoring company, identified.
► Extensive computational results presented.