This paper addresses a rich integrated combinatorial optimization problem designated by Production Routing Problem (PRP) inspired by the real-world case study. The PRP involves coordinating production and distribution decisions over a finite planning horizon, divided into periods, for multiple products characterized by heterogeneous attributes, such as weight, size, and number of components. This PRP incorporates several constraints, including sequence-dependent setups, safety stocks and limited production capacity, multi-period routing, and customers with multiple time windows and deadlines. The objective is to minimize the total cost, which comprises setup costs, inventory holding, and transportation expenses. This integration of production and distribution decisions introduces temporal and spatial interdependencies which make the problem NP-hard. To tackle this problem, we propose a hybrid approach that combines a Variable Neighborhood Search metaheuristic with an embedded Integer Programming model. The proposed approach is evaluated through extensive computational experiments on benchmark instances, demonstrating its effectiveness in solving the PRP and handling its inherent combinatorial complexity.