Empirical Analysis of Multi-Depot Vehicle Routing with Time Windows in Nigerian Urban Freight Distribution

Urban freight distribution in Nigerian metropolitan areas is complicated by road network congestion, informal market structures, and heterogeneous customer delivery windows that challenge standard routing models. This study empirically analyses the multi-depot vehicle routing problem with time windows (MDVRPTW) using data from a consumer goods distribution network operating across Abuja and its satellite towns in the Federal Capital Territory. A mathematical formulation of the MDVRPTW is presented, and a metaheuristic solution approach combining adaptive large neighbourhood search with a local 3-opt improvement procedure is developed and implemented. Computational experiments are conducted using a proprietary dataset of 287 delivery orders across 14 zones served from three depots, with time window data derived from observed customer business hours. The proposed metaheuristic is benchmarked against a commercial solver and a simulated annealing baseline on objective function value and computational runtime. Results demonstrate that the proposed approach achieves solutions within 3.8 percent of the commercial solver's optimum on average while reducing computation time by 91 percent, making it viable for real-time operational use. Sensitivity analysis reveals that tightening customer time windows by 20 percent increases average route cost by 17 percent, quantifying the economic value of flexible delivery windows. The study identifies three depot locations where consolidation would reduce total distribution cost by 14 percent without service level degradation. Findings fill an empirical gap in VRPTW research conducted within sub-Saharan African urban contexts. Keywords: vehicle routing, time windows, urban freight, Abuja, metaheuristic