A sweep-heuristic based formulation for the vehicle routing problem with cross-docking

Cross-docking is a warehousing strategy in logistics used by process industries making 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 model based on the sweep heuristic can find near-optimal solutions to large problems at very acceptable CPU times.

► This work introduces a pair of monolithic formulations for the vehicle routing problem with cross-docking.
► Both determine pickup/delivery routes and schedules simultaneously with the truck scheduling at the cross-dock terminal.
► One of the formulations includes a constraint set that mimics the sweep-heuristic algorithm.
► The sweep-based approach can solve large problems in acceptable CPU times.