A Variable Neighborhood Search for the Fleet Size and Mix Vehicle Routing Problem with Simultaneous Pickup and Delivery

In this study, a variable neighborhood search (VNS) is proposed to address the Fleet Size and Mix Vehicle Routing Problem with Simultaneous Pickup and Delivery (FSMSPD). Initially, solutions are generated using an adaptation of the Clarke-Wright Savings (CWS) algorithm, followed by an intelligent repairing heuristic that includes intra-and inter-route moves to optimize both fleet composition and solution quality. Subsequently, a variable neighborhood search (VNS) is employed, incorporating the repairing heuristic to explore solution neighborhoods while ensuring feasibility. The methodology aims to minimize routing costs while effectively considering vehicle capabilities and SPD constraints. Computational experiments on small instances generated by the authors show that the proposed methodology is effective compared to a commercial solver. Additionally, we use benchmark instances from the literature and compare our results with those obtained by a state-of-the-art algorithm. Our approach demonstrates competitive results.