A Novel mixed integer linear programming model to solve multiple trip vehicle routing problem

Abstract

The complexity of the development of mathematical models for vehicle routing problems increases with the addition of more variables and constraints. In this study, a mathematical model was developed for a multiple-trip vehicle routing problem by relaxing the constraints of the single-trip model. The novelty has brought to the study through a simple three-index formulation developed for the multiple-trip vehicle routing problem, with a fewer number of constraints. The model was developed using the mixed integer linear programming (MILP) technique considering a heterogeneous fleet of vehicles, time window, pickups, capacity constraints and single deport. Three-index formulation without a trip index and a new integer variable for the number of trips assigned to a vehicle in a given time unit are introduced into the model. Since most of the past studies considered the number of vehicles available for the routing plane with a separate index, this study reduces complexity and facilitates an easy- solving approach. Hence, it reduces the difficulty of determining vehicle utilization rates and provides managerial implications through identifying under-utilized resources. The model was tested and solved using a real-world data set from a small-scale enterprise in Sri Lanka by applying the Branch and Cut algorithm. Time and distance matrices and vehicle capacities were fed to the model. The output of the experimental analysis showed a clear reduction in the distance traveled and the number of vehicles used compared with the method adopted by the enterprise. It shows that the proposed method can be applied to real-world cases to reduce transportation costs and the complexity of vehicle scheduling. This study contributes to the existing knowledge gap through the proposed mathematical model.