To mitigate the negative effect of freight vehicles on urban areas, many cities have implemented road accessibility restrictions, including limited traffic zones, which restrict access to specific areas during certain times of the day. Implementing these zones creates a trade-off between the delivery cost and time, even under the assumption of equal traversal time and travel cost. Consequently, the planners in charge of vehicle routing need to work with graphs containing information on all Pareto-optimal paths. Inspired by these changes in city logistics and the resulting computational challenges, we study the vehicle routing problem with access restrictions, where some streets are closed to traffic within a given time period. We formulate this problem using workday variables and propose two branch and price algorithms based on the underlying road network and multi-graph. The results of our computational experiments demonstrate the effectiveness of the proposed algorithms, solving instances with up to 100 nodes and 33 customers, and underline the importance of considering alternative paths in reducing costs.