We study the strategic problem of a logistics service provider managing a (possibly heterogeneous) fleet of vehicles to serve a city in the presence of access restrictions. We model the problem as an area partitioning problem in which a rectangular service area has to be divided into sectors, each served by a single vehicle. The length of the routes, which depends on the dimension of the sectors and on customer density in the area, is calculated using a continuous approximation. The aim is to partition the area and to determine the type of vehicles to use in order to minimize the sum of ownership or leasing, transportation and labor costs. We formulate the problem as a mixed integer linear problem and as a dynamic program. We develop efficient algorithms to obtain an optimal solution and present some structural properties regarding the optimal partition of the service area and the set of vehicle types to use. We also derive some interesting insights, namely we show that in some cases traffic restrictions may actually increase the number of vehicles on the streets, and we study the benefits of operating a heterogeneous fleet of vehicles.