TABU SEARCH AND THE VEHICLE ROUTING PROBLEM: TRANSPORTATION COST OPTIMIZATION IN A SCENARIO WITH MULTI-DEPOT HETEROGENEOUS FLEET AND SPLIT DELIVERY

This study develops and implements a Tabu Search (TS) algorithm to address the Multi-Depot Vehicle Routing Problem with Time Windows, Capacities, and Split Deliveries (MD-VRPTWCD) to minimize transportation costs for an e-commerce business distributing candle-making supplies. The problem involves serving 67 customers from four distinct depots, utilizing a heterogeneous fleet of three types of trucks, each with unique weight capacities and cost structures. The algorithm achieves a 19.1% reduction in total transportation costs despite utilizing more trucks and increasing overall mileage compared to the company's previous greedy heuristic approach. The new solution prioritizes smaller, more efficient trucks, resulting in a higher average weight utilization (69.3% up from 61.7%). Sensitivity analysis with alternative lighter truck types indicated that the current fleet composition was optimal for the company's operational context. The study suggests future integration with 3D bin packing techniques to further enhance vehicle loading efficiency.