Optimal Transportation Planning for a Do-It-Yourself Retailer with a Zone-Based Tariff

This article describes the development of a decision support tool for a Rich Vehicle Routing Problem (R-VRP) of a major do-it-yourself (DIY) retailer supplying its stores across Europe from multiple depots. The retailer uses external logistic service providers (LSPs) for the delivery to its stores and has two modes to choose from. In the first mode, the retailer proposes delivery tours to LSPs for execution. These tours are billed according to a nonlinear tariff with volume discounts depending on the delivery zones visited and the load carried. The LSPs accept the retailer’s tour proposal only if tour duration and distance restrictions are kept. The latter is ensured by a relative detour limit. In the second mode, the retailer assigns single shipments to common carriers that consolidate them with shipments from other customers and bill this based on load and destination. The resulting problem represents an open VRP with two delivery modes, carrier selection and a heterogeneous fleet. Multiple delivery modes are standard in DIY retailing and constitute a general industry problem. The literature on VRPs and current software applications in the industry predominantly considers modeling and solution approaches that rely on linear distance costs, neglecting that nonlinear zone-based tariffs with volume discounts are standard in the freight forwarding business. Our work addresses this issue by developing a decision support tool for the retailer based on an exact algorithm for solving R-VRPs with a nonlinear zone-based tariff scheme and a relative detour limit. The tool is based on an innovative three-component set partitioning algorithm working on a complete set of feasible tours to solve the problem. We show that our approach optimally solves the daily distribution problem of the industry partner with up to 150 stores. Furthermore, implementing the tool enables more comprehensive and structured planning for the retailer and an average of 8% transportation cost savings, translating to total savings of more than €1 million per year for this specific retailer compared with the status quo.