An Integer Linear Programming Model for the Heterogeneous Fixed Fleet Vehicle Routing Problems with Multiple Products and Split Deliveries

This study aims to propose a model to minimize the total transportation cost in Heterogeneous Fixed Fleet Vehicle Routing Problems with Multi-products and Split Deliveries. This type of vehicle routing problem is commonly encountered in manufacturing companies that produce various products (with different sizes or weights) and distribute them continuously to retail stores and other customers using a heterogeneous fleet of vehicles. In these problems, different types of vehicles with varying loading capacities are available in limited numbers, each with its own fixed and variable (travel) costs.Despite their high importance, vehicle routing problems that involve a heterogeneous fleet, multiple products, and split deliveries have not been extensively studied.

A pure integer linear programming model is developed to address the problem. The proposed model aims to minimize the total transportation cost, including fixed costs, variable (travel) costs, and stopping costs at destinations. The model selects several vehicles from the fleet and determines the products to be loaded in each one. It then establishes the route for each vehicle and specifies which products each vehicle delivers to which customer. An innovative modeling technique is employed to determine the sequence in which vehicles meet customers.

The computational results from solving 32 instances of random problems using the proposed method demonstrate its effectiveness. For small-scale problems (up to 15 customers), the method can achieve optimal solutions within a reasonable time frame (ranging from 1 to 2000 seconds, depending on the problem size). For medium-scale problems (20 to 30 customers), it can find acceptable solutions within 3600 seconds. Additionally, for larger-scale problems (up to 50 customers), feasible solutions were obtained and improved over time within a one-hour limit (3600 seconds). Among the problem parameters, the number of customers has the greatest impact on the problem-solving time, followed by the number of product types and the number of vehicles.

The results of this study indicate that the proposed model is an effective approach for optimizing transportation costs in vehicle routing problems characterized by split deliveries, multiple products, and heterogeneous fleets. The model proves to be a robust and efficient solution for small to medium-scale problems, significantly enhancing operational efficiency and reducing transportation costs for manufacturing companies. It is anticipated that developing meta-heuristic models based on the proposed mathematical programming framework will not only accelerate problem-solving but also facilitate the attainment of near-optimal and satisfactory solutions for larger-scale issues.