A model‐based heuristic for a three‐dimensional loading vehicle routing problem with split pickups and time windows

Abstract

The increase in waste products and product returns has prompted logistics service providers (LSPs) to manage reverse logistics more efficiently. This paper investigates an integrated vehicle routing problem with split pickups and three‐dimensional loading arising in real‐life logistics operations, as identified through a survey of Belgian LSPs. We propose a mixed integer linear programming (MILP) formulation that accounts for a comprehensive set of real‐life constraints such as split pickups, time windows, maximum working duration, box stability, and reachability. This box stability definition includes a minimum contact area for each corner of the bottom face of stacked boxes, and the reachability definition ensures that boxes cannot be loaded beyond the distance reachable by the driver's arm. We analyze the impact of these constraints on the MILP. The MILP is tested on small instances, but the computational times quickly explode as the problem is ‐hard. We thus extend the insert‐and‐fix (I&F) heuristic to simultaneously handle routing and loading constraints. Numerical experiments show that the I&F is effective in solving larger instances than the MILP alone, reducing costs by 13.71% on average and reaching optimality for eight additional instances. The I&F is also effective in minimizing the number of rented vehicles.