A MILP-Based Very Large-Scale Neighborhood Search for the Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery

The Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is a challenging NP-hard optimization problem, in which each of several customers demands both delivery and pickup operations and must be visited once by a single vehicle from a fleet. In this article, we present a Very Large-Scale Neighborhood Search (VLSN) to tackle the VRPSPD with heterogeneous fleets, whereby different large neighborhood structures are employed within a simple descent method. We use benchmark instances from literature and present very competitive results, improving several of the best-known solutions and consistently outperforming current state-of-the-art algorithms.