A Sweep-Heuristic Based Formulation for the Vehicle Routing Problem with Cross Docking

Abstract

Cross-docking is a warehousing strategy in logistics used by process industries manufacturing products with high proportions of distribution costs. It is described as the process of moving goods from suppliers to customers through a cross-dock terminal without a long-term storage in this facility. The vehicle routing problem with cross-docking (VRPCD) consists of fulfilling a set of transportation requests using a fleet of homogeneous vehicles to sequentially accomplish the pickup and delivery tasks. Between those operations, there is a consolidation process of incoming shipments at the cross-dock. This work introduces a monolithic formulation for the VRPCD that determines pickup/delivery routes and schedules simultaneously with the truck scheduling at the terminal. To derive a more efficient formulation, a constraint set mimicking the widely known sweep algorithm was incorporated into the rigorous model. The resulting formulation based on the sweep-heuristic can find near-optimal solutions to large problems at very acceptable CPU times.