A GRASP for a Multi-Depot Multi-Commodity Pickup and Delivery Problem with Time Windows and Heterogeneous Fleet in the Bottled Beverage Industry

Abstract: A pickup and delivery vehicle routing problem from a real-world bottled-beverage distribution company is addressed. The problem consists of deciding how to load every trailer, how to configure the vehicles in terms of the trailers, and how to rout the vehicles, so as to minimize routing and fixed costs. The problem includes several features such as time windows on both customers and vehicles, multiple depots, multiple product delivery, split delivery, heterogeneous fleet, and dock capacity, to name a few. To solve this problem a GRASP-based heuristic is proposed. Problem decomposition, vehicle composition and route construction mechanisms, and local search procedures for different types of neighborhoods are developed. The heuristic is empirically assessed over a wide set of instances. Empirical results show that the proposed method obtains solutions of better quality than those reported by the company.