Solving a real case of rich vehicle routing problem with zone-dependent transportation costs

This paper addresses the pressing distribution challenge encountered by a company tasked with supplying goods to public schools across Andalusia, Spain's largest region. With a database comprising 7811 potential customers spread across 8 provinces, the company operates a diverse fleet of vehicles from a central depot. Complicating matters, customers possess varying access restrictions based on vehicle size, may require service from multiple vehicles, and are subject to time windows for delivery. The central aim is to minimize the company's transportation costs, uniquely influenced not by distance traveled but by the provinces traversed. In this paper, we introduce the Rich Vehicle Routing Problem with zone-dependent transportation cost. To tackle this novel problem, we formulate a rigorous mathematical model. Our approach emphasizes practical application, focusing on the development and validation of algorithms tailored to address real-world constraints. By implementing and testing a combination of GRASP heuristic and tabu search algorithms, validated against actual operational data, we achieve a substantial reduction in transportation costs and vehicle utilization. Ultimately, our methodology facilitates a more sustainable and efficient allocation of the company's resources, addressing the complexities of real-world distribution challenges.