In a vendor-managed inventory setting a supplier decides on the timing and size of an inventory replenishment at its customers. If the supplier outsources the transportation to a Logistics Service Provider (LSP) it is often the case that a fixed transportation fee is charged for each replenishment. In the traditional Joint Replenishment Problem one assumes that the supplier pays a fixed cost for visiting a customer. Hence, there is no incentive for the supplier to schedule replenishments of nearby customers in the same period. This results in higher transportation costs for the LSP and potential capacity shortages at the LSP. In the long run these higher transportation costs will be reflected in the transportation fees paid by the supplier. To lower costs for both parties the traditional Joint Replenishment Problem needs to be extended by taking transportation considerations into account. To solve the extended JRP subsets of customers are created and their transportation cost is approximated in a Branch-and-Cut-and-Price framework. The extended JRP formulation and solution approach is validated on test instances from the literature.