Integrated planning systems can be used to better coordinate processes and better align decisions within supply chains. A system integrating the three key processes production, inventory, and distribution is given by the Production Routing Problem (PRP). A single plant with capacity constraints produces a single product and distributes it by a restricted number of homogeneous vehicles to meet retailers’ demand. Due to periodic routing decisions combined with inventory and production decisions, the PRP is difficult to solve. To overcome this issue, a set partitioning formulation based on predetermined routes is used. To generate the set of routes, clusters are built using several clustering methods. Different clustering techniques are analyzed and a new heuristic approach is provided. For each of the generated clusters, a Traveling Salesman Problem (TSP) is solved. To avoid solving unnecessarily large TSPs, an upper bound on the route length is provided, based on vehicle capacity and demand patterns. In this study, classical clustering methods are considered as well as a demand-oriented and a new clustering method that incorporates inventory information. Additionally, an improvement strategy is implemented that identifies and removes unnecessarily visited retailers. For further improvement, a Local Search with respect to the vehicle load is applied. Computational tests are performed on benchmark instances from the literature to evaluate the heuristic and analyze the impact of the different proposed clustering techniques. The results suggest that considering demand and inventory information as well as increasing vehicle utilization is reasonable.