The Vehicle Routing Problem with Split Delivery and Heterogeneous Trucks and Commodities: A Case Study

The vehicle routing problem (VRP) is that of finding the optimal routes for a number of vehicles (trucks) to serve a set of customers, with the goal of minimizing the total transportation cost. Due to the different sizes and nature of customer orders and different capacities of trucks, an order might be split onto more than one truck. The problem then becomes not only of finding the optimal routes, but further of how to divide the orders between trucks. In this paper, the VRP with split strategy, considering heterogeneous fleet and orders is approached. The problem was first formulated as a mixed integer programming model (MILP) with a total transportation cost minimization objective. Due to the complexity of the problem, a two-phase solution algorithm was further proposed to solve the problem. The algorithm first constructs the routes sequentially based on the savings function, then it employs a 2-opt algorithm to improve the routes. The algorithm was applied to solve the problem for a fast moving consumer goods (FMCG) distribution company. Results indicated that the algorithm is able to minimize the number of required trucks and satisfy all customer orders, while minimizing the transportation cost.