Split Delivery Vehicle Routing Problem for Transportation - A Case Study

Nguyen Khoi Pham, Anh H. G. Nguyen

Abstract: The Split Delivery Vehicle Routing Problem (SDVRP) is a modification of the classical Vehicle Routing Problem (VRP), which aims to establish optimal routes for a fleet of vehicles serving customers with multiple delivery splits. In this study, we develop an exact solution MILP model for solving the SDVRP with a specific case study of a company operating a sugar factory in Bien Hoa, Dong Nai, Vietnam. This study contributes a MILP SDVRP model to help the company to construct a delivery system with the optimal delivery routes for their vehicle fleet with the objective to minimize the total distance traveled. The computational results prove that the proposed MILP is superior in solving a large number of customer problems and produces optimal solutions which is much better than the current system of the company. Moreover, the proposed MILP also outperforms an existing method in a publication for solving the same problem. The numerical results emphasize the contribution of our proposed MILP in both practical and academic aspects.

Keywords: Mixed integer linear programming, Split delivery, Vehicle routing problem, Transportation