We consider an important generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. This fixed cost could reflect payment for toll roads, investment in new facilities, the need for certifications and other costly investments. The certifications and contributions impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company. Different versions for defining the edge sets are discussed and formulated. A MIP-formulation of the problem is presented, and a solution method based on branch-and-price-and-cut is applied to the problem. The computational results show that instances with up to 50 customers can be solved in reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX. It also seems that instances get more difficult when the penalized edge sets form a spanning tree, compared to when they are randomly scattered.