VEHICLE ROUTING WITH COMPARTMENTS UNDER PRODUCT INCOMPATIBILITY CONSTRAINTS

Abstract

This study focuses on a distribution problem involving incompatible products which cannot be stored in a compartment of a vehicle. To satisfy different types of customer demand at minimum logistics cost the products are stored in different compartments of fleet vehicles which requires the problem to be modeled as a multiple-compartment vehicle routing problem (MCVRP). While there is an extensive literature on the vehicle routing problem (VRP) and its numerous variants there are fewer research papers on the MCVRP. Firstly a novel taxonomic framework for the VRP literature is proposed in this study. Secondly new mathematical models are proposed for the basic MCVRP together with its multiple-trip and split-delivery extensions for obtaining exact solutions for small-size instances. Finally heuristic algorithms are developed for larger instances of the three problem variants. To test the performance of our heuristics against optimum solutions for larger instances a lower bounding scheme is also proposed. The results of the computational experiments are reported indicating validity and a promising performance of an approach.