Capacitated Vehicle Routing Problem with a Zone Tariff

ABSTRACT High demand and volume fluctuations, constrained transportation capacity, and weak network effects compel retailers to rely on external logistic service providers (LSPs) instead of operating their own transportation fleet. This outsourcing process requires retailers to propose tours to LSPs that then carry out the store deliveries. LSPs typically bill their service using a tariff with a zone structure representing geographical positions. The transportation costs depend on the zones visited and the delivery volume, which is subject to volume discounts. Further, LSPs apply detour limits to prevent excessive travel distances. Zone tariffs are a standard pricing scheme to ease transportation planning in the industry. Despite its high practical relevance, the literature in this field is limited, and a general model and solution approach are lacking. Our work closes this gap by providing the first comprehensive model for the Capacitated Vehicle Routing Problem with a Zone Tariff (C‐VRP‐ZT) and by developing a generally applicable exact solution method. The developed Branch‐and‐Check (BAC) framework includes valid inequalities and multiple acceleration techniques. We prove the computational efficiency of our approach using benchmark instances and derive managerial insights. We analyze different tariff structures concerning central characteristics such as the zone layout and order consolidation. Our results show how the tariff characteristics impact the cost of retailers and the margins of LSPs. We further solve a real‐world application in retailing and analyze the cost/revenue split between a retailer and an LSP. These results provide insights into the threshold when a retailer should outsource its transportation process.