We consider a car rental network revenue management (RM) problem, accounting for the key operational characteristics of car rental services such as the varying length of rentals and mobility of inventories, which imply the intertemporal and spatial correlations of rental demands for inventories across different locations and days. The problem is formulated as an infinite-horizon cyclic stochastic dynamic program to account for the time-varying and cyclic nature of car rental businesses. To tackle the curse of dimensionality, we propose a Lagrangian relaxation (LR) approach with product- and time-dependent Lagrangian multipliers to decomposing the dynamic network problem into multiple single-station single-day subproblems. We show that the Lagrangian dual problem is a convex program and then develop a subgradient-based algorithm to solve the dual problem and derive an LR-based bid price policy. To improve the scalability of the LR approach, we further propose three simpler LR-based bid price policy variants with either location-dependent or leadtime-dependent Lagrangian multipliers, or both. Our numerical study indicates that the LR-based bid price policies can outperform some commonly used heuristics. Using a set of real-world booking data, we provide a case study in which we empirically demonstrate the operational characteristics of car rental services, calibrate the arrival process of booking requests using a Poisson regression model, and demonstrate that the LR-based bid price policies indeed outperform other heuristics consistently in both in-sample and out-of-sample horizons.