Abstract
The Heterogeneous Capacitated Vehicle Routing Problem (HCVRP) is a fundamental extension of the classical Vehicle Routing Problem in which customer demands must be satisfied using a fleet of vehicles with varying capacities and costs. In this paper, a novel and intuitive decomposition-based formulation for HCVRP is presented that decomposes the problem into two tractable subproblems: (i) a route generation and an optimal customer sequencing problem and (ii) a vehicle route assignment problem. In the first stage, all feasible customer combinations are constructed as routes, and for each route an optimization problem is solved to identify the optimal customer sequence that results in the minimum distance travelled. In the second stage, the optimal routes are selected, and vehicles are assigned using a mixed integer linear programming (MILP) formulation that minimizes the fixed cost of vehicle utilisation and total transportation costs, ensuring demand satisfaction for all customers while meeting vehicle capacity limitations. Computational results demonstrate that the decomposition strategy preserves optimality while significantly reducing solution time.