The customer-centric, multi-commodity vehicle routing problem with split delivery

• We introduce the Customer-centric, Multi-commodity Vehicle Routing Problem with Split Delivery.
• We propose two mathematical models of the problem and compare.
• Several optimality conditions are proved.
• A hybrid metaheuristic is proposed and used to solve large scale problems.

In this paper, we present the Customer-centric, Multi-commodity Vehicle Routing Problem with Split Delivery (CMVRPSD) whose objective is to minimize total waiting time of customers in distributing multiple types of commodities by multiple capacitated vehicles. It is assumed that a customer's demand can be fulfilled by more than one vehicle. Two classes of decisions are involved in this problem: routing vehicles to customers and quantifying commodities to load and unload. The CMVRPSD can be applied to distributing commodities in customer-oriented distribution problems for both peacetime and disaster situations. The problem is formulated in two Mixed-Integer Linear Programming (MILP) models, and a heuristic method is proposed by adapting and synthesizing Simulated Annealing (SA) and Variable Neighborhood Search (VNS) for large-scale problems. Experimental results show that the proposed hybrid algorithm outperforms other applicable algorithms such as SA, VNS, and Nearest Neighborhood heuristic.