We consider a novel variant of the heterogeneous vehicle routing problem (VRP) in which each customer has different availability time windows for every vehicle. In particular, this covers our motivating application of planning daily delivery tours for a single vehicle, where customers can be available at different times each day. The existing literature on heterogeneous VRPs typically distinguishes properties of the vehicle fleet such as costs or capacities, but apparently, windows of customers have only been regarded in a homogeneous fashion thus far. To solve the problem, we employ a branch-and-price framework based on a set partitioning formulation together with a parallelizable labeling algorithm. The heterogeneous time window structure yields notable computational gains by allowing to decompose the pricing problem as well as to utilize a customer-vehicle assignment branching rule. We show that this branching rule leads to more balanced search trees than the usual arc flow branching, and demonstrate its efficiency in numerical experiments.