A novel multi-compartment vehicle routing problem with time windows : reconfigurable vehicles and dynamic compartments

Kurzfassung/Abstract

This paper introduces a novel variant of the Multi-Compartment Vehicle Routing Problem with Time Windows, inspired by real-world grocery distribution needs for efficient temperature-controlled deliveries. The proposed model incorporates a heterogeneous fleet of fresh and frozen vehicles equipped with modular frigoboxes featuring dynamic compartments, allowing flexible temperature and capacity adjustments, as well as mixed-reconfigurable vehicles that enable capacity reallocation across compartments. These features support the simultaneous transportation of fresh and frozen products, enhancing adaptability to multi-temperature demands. A new flow-based mixed-integer linear programming formulation is presented, along with a multi-start variable neighborhood search heuristic that integrates problem-specific operators to jointly optimize vehicle selection, compartment configuration, and routing. A new benchmark dataset evaluates the model under varying product types, reconfiguration settings, and fleet compositions. Computational results show that the heuristic effectively balances solution quality and runtime, and sensitivity analyses highlight the operational benefits of mixed-reconfigurable vehicles and dynamic compartments.