A Clustering-Based Decomposition Framework for Solving the Feeder Vehicle Routing Problem

Abstract

The rapid expansion of e-commerce has made home delivery an essential service for both customers and businesses. However, parcel delivery operations are increasingly challenged by traffic restrictions, high operational costs, and limited resource availability. A promising strategy for addressing these challenges is the simultaneous use of a heterogeneous fleet, comprising trucks and motorcycles, in distribution operations. Despite its potential advantages, the planning of such hybrid delivery systems is highly complex, as their structural characteristics and operational constraints give rise to large-scale optimization models that are difficult to solve within a reasonable computational time. To overcome this limitation, this study proposes a matheuristic approach for the problem under consideration. The proposed method first decomposes the original problem into smaller subproblems using clustering techniques. Each subproblem is then solved by means of a mathematical optimization model, and the resulting solutions are integrated to construct the final delivery plan. Computational experiments on a set of standard benchmark instances demonstrate that the proposed strategy achieves an average reduction of 32.51% in the objective function value compared with traditional delivery methods.