Solving a Vehicle Routing Problem in the Context of a Large Food Company

Efficient logistical planning is crucial for food distribution companies, particularly under complex operational constraints such as vehicle capacity limits, heterogeneous fleets, customer time windows, and product perishability. These constraints are captured by the Heterogeneous Fleet Vehicle Routing Problem with Time Windows (HFVRPTW), a variant of the classical Vehicle Routing Problem (VRP). Although numerous studies have addressed VRP variants, validating optimization models in real-world contexts remains a critical challenge, since employing simplified or benchmark instances may not fully capture the complexity of practical logistics operations.

This study adapts and implements an Integer Linear Programming (ILP) formulation to solve the HFVRPTW in a large food distribution company's operational setting. The model is tailored to the company's logistical characteristics and evaluated via a direct comparison with manually generated routing plans, enabling an assessment of both solution quality and practical viability.

After a careful review of different ILP models, the one proposed by Braysy et al. [2008] was selected, as it was specifically designed for the HFVRPTW and had its relevance established in subsequent research. The model was adapted with key modifications: corrections in time window inequalities, redefinition of a big-M coefficient to avoid numerical infeasibilities, and relaxation of the implicit assumption of a complete graph. Real operational data extracted from company reports contained 99,428 records: customer data, including geographic coordinates, order demands (320.32 kg to 18,337.37 kg), unloading service times, and delivery time windows; fleet data, featuring 10 distinct vehicle capacities (2.5 t to 28 t). Real road network distances and travel times within a 50 km depot radius were computed using OpenRouteService. The system was developed in Python 3.12, solved using Gurobi 12.0, and integrated with Folium for interactive geospatial route visualization.

Empirical validation across 15 test instances (10, 15, and 20 customers/vehicles) demonstrated the consistent superiority of the ILP model over manual dispatching in every scenario. The optimization produced progressive average total distance reductions of 7.35%, 29.54%, and 31.01% for 10, 15, and 20 customers, respectively, reaching individual savings of up to 51.01%. Moreover, the model substantially optimized fleet utilization, requiring up to four fewer vehicles in specific cases. Regarding computational time, the exact model consistently outperformed the manual approach for 10-customer (avg.: 8.1 sec vs. 24.0 min) and 15-customer instances (avg.: 31.4 min vs. 41.0 min). For larger instances (20 customers), the solver often reached the time limit (210 min), but solutions superior to manual planning were identified early during execution. By eliminating continuous manual labor and human error, the adapted ILP approach has shown its scalability and practical relevance as a decision-supporting tool for industrial logistics automation.