Clustering algorithms for consolidation of customer orders into vehicle shipments

The consolidation of shipments into loads arises in a number of applications, including household moving, truckload trucking, rail and container operations. The capacitated clustering problem (CCP) is one of the underlying optimization problems for the efficient consolidation of customer orders to vehicle shipments. In this paper we develop optimization-based heuristic algorithms for the CCP, extending procedures developed by Mulvey and Beck, as well as algorithms developed by Fisher and Jaikumar, for the generalized assignment problem. In this paper, iterative methods are proposed that avoid the specification of "seed" customers required by other algorithms, and which are shown to produce better solutions than existing heuristics. Lagrangian relaxations are used to develop rigorous bounds, which demonstrate the effectiveness of relatively simple heuristics.