Product-oriented split delivery in the multi-compartment vehicle routing problem

This paper addresses split delivery in the multi-compartment vehicle routing problem in which the possibility of splitting delivery depends on the product type. For certain product types, split delivery is not allowed but for other ones is permitted under a certain condition. The arrival time consistency is considered as split delivery condition. If the difference between vehicle arrival times to the customer does not exceed a certain limit, the consistency of arrival time is established and split delivery is allowed. A mathematical model is developed to describe the proposed problem and used to solve small sized instances. To solve large sized instances, an adaptive large neighborhood search and a matheuristic based on fixing a part of customer to route assignment variables are developed. Computational experiments are performed on the multi-compartment vehicle routing problem with and without product-oriented split delivery. The effect of capacity and compartments per vehicle on delivery mode is investigated. The results demonstrate that the matheuristic outperforms the adaptive large neighborhood search in term of quality and computational time. Furthermore, delivery mode does not have a significant effect on the proposed algorithms’ computational time and the number of vehicles is more affected by delivery mode than distance travelled.