A Genetic Algorithm for the Multi-compartment Vehicle Routing Problem with Stochastic Demands and Flexible Compartment Sizes

The multi-compartment vehicle routing problem (MC-VRP) consists of designing a set of routes to perform the collection of different product types from customer locations with minimal costs. The MC-VRP arises in several practical situations, such as selective waste collection or different color of glass collection. Compartment sizes can be either set as fixed or as flexible. Often in practice, the collection quantity from customers is stochastic in nature, that is, the exact value is not available during route planning and is known only once the vehicles are at the customers’ locations. Our work introduces the MC-VRP with stochastic customer demands and with flexible compartment sizes. We propose a genetic algorithm (GA) to solve this problem and investigate the benefits of setting the compartment sizes to be flexible instead of fixed with pre-defined sizes. By using flexible compartment sizes, the GA shows an overall average improvement of 7.8%, compared to the state-of-the-art approach for fixed compartment sizes.