Bid price controls for car rental network revenue management

Abstract

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.

INTRODUCTION

Revenue management (RM), also called yield management, originated in the airline industry in the 1970s, and has been widely adopted across various industries, including airlines, cruise lines, hotels, car rental, and manufacturing (Talluri & van Ryzin, 2004). See Klein et al. (2020) for a review of the recent developments and applications of RM. For car rentals, one of the successes of RM is that it saved National Car Rental from bankruptcy, turning losses into profits in 1994 (Geraghty & Johnson, 1997). Nowadays, the majority of car rental operators are equipped with RM systems. Carroll and Grimes (1995) describe the RM system implemented in Hertz and report an average revenue increase of

$1\sim 5\%$

per rental. Recently, Guillen et al. (2019) provide a detailed account of the RM system developed for Europe Car. See Oliveira et al. (2017) for a recent review on the development of car rental fleet and RM.

Despite its prevalence in practice, car rental RM has received limited attention in the literature compared with the airline RM that has been studied extensively (Talluri & van Ryzin, 2004). While sharing some characteristics with airlines, such as limited capacity (i.e., resource scarcity) and limited inventory lifetime (i.e., perishability), car rental is also characterized by length of rental (LoR) and mobility of cars among stations, which implies that car rental systems combine the features of advance bookings of airline RM (see, e.g., Talluri & van Ryzin, 1998) and the capacity allocation of queuing networks (see, e.g., Balseiro et al., 2021; Gans & Savin, 2007; George & Xia, 2010; Savin et al., 2005). Note that hotel RM also features advance booking and multiday length of stay, and the usage of a hotel room is similar to the round‐trip; see, for example, Li and Pang (2017) for a discussion on the equivalence of the booking limit control for a hotel and a single car rental station with only round‐trips. Hence, the mobility of cars is a unique feature of the car rental network compared with other hospitality industries such as airlines and hotels. A typical car rental booking request must specify where and when to pick up and return the car, which implies that a car rental product is characterized by the combination of origin, destination, pick‐up time, and LoR. Hence car rental demands for inventories in different locations and days are spatially and intertemporally correlated. The car rental network RM system can be viewed as a stochastic network with advance booking control and therefore has much more complex dynamics than conventional airline RM systems, introducing significant modeling and computational challenges.

Bid price, also referred to as shadow price, is a key economic concept in RM to measure the opportunity cost of a resource. Bid price controls are a class of policies that use the optimal or approximate bid prices of the resources for a product to control its capacity. Bid price policies have been recognized as a powerful tool in RM; see Talluri and van Ryzin (2004) and the references therein. Under bid price control, a booking request for a product as a combination of multiple resources is accepted only if all the associated resources are available and the revenue from this request is greater than the sum of the bid prices associated with the resources of the product (Talluri & van Ryzin, 1998). Such an idea is appealing in practice since it is intuitive and easy to implement once the bid prices are available. However, computing the optimal bid prices can be challenging for network RM problems in light of the high dimensionality of the state space and the lack of analytical tractability, which leads to the research focus on developing efficient heuristics.

An efficient method commonly used in dynamic resource allocation problems is the Lagrangian relaxation (LR) approach. The core idea of the LR approach is to relax the constraints that link different resources through Lagrangian multipliers and then obtain the optimal Lagrangian multipliers as well as the optimal decisions by solving the dual problem. The LR approach was first proposed by Jiang (2006) to solve the probabilistic nonlinear program (PNLP) model for airline network RM. For a dynamic capacity allocation model in airline network RM, Topaloglu (2009) proposes an LR approach that decouples the acceptance decisions for each product over the resources that it uses through product‐ and time‐dependent Lagrange multipliers. Kunnumkal and Talluri (2016) further show that the optimal Lagrangian multipliers can be obtained through a linear programming formulation of the decomposed dynamic programs (DPs). For a spoke‐and‐hub mobility service (e.g., ride hailing) network, Balseiro et al. (2021) propose an LR approach with a single Lagrangian multiplier that relaxes the total capacity constraint to decompose the network problem into multiple single‐station problems with each station (spoke) using dynamic pricing to relocate cars between the spoke and the hub. These LR approaches, though similar in spirit in terms of assigning bid prices to resources to relax resource constraints and decompose a high‐dimensional problem into multiple single‐dimensional problems, do not readily apply to the car rental network RM problems, which need to simultaneously account for the spatial and intertemporal linkages of resources. Our paper aims to fill this gap by introducing an LR approach that captures the aforementioned key operational characteristics of car rental network RM.

More specifically, we consider the bid price control problem for a car rental network. Booking requests arrive sequentially during each day, which is formulated as a discrete‐time point process as an approximation of the Poisson arrival process. Each booking requests a car and specifies the locations (i.e., the origin and destination stations) and dates to pick up and return the car. It can be either round‐trip or one‐way. The bookings are restricted to a maximum booking window (the latest pick‐up day from the current day) and a maximum LoR. The rental price for each product is given, with the average daily rental rate varying across products. Upon arrival of each booking request, the operator decides whether to accept the booking.

We formulate the car rental RM problem into an infinite‐horizon cyclic stochastic DP that accounts for the cyclic and stochastic nature of the arrival process of booking requests and the characteristics of car rental products. The goal is to optimize the capacity allocation policy to maximize the expected total discounted revenue. The underlying Markov decision process is described with a set of state variables that represent the number of idle cars for each station and each of the future days that are within the regular booking and rental time window. The regular booking and rental window rolls forward when a new day starts. In car rental, a booking may affect the resources across two stations and over multiple rental days, and its dynamics can be seen as a combination of an advance booking process and a closed queueing network. A booking of a multiday one‐way rental occupies a unit of car of the original station from the pick‐up day onwards and then transfers the car to the destination station, which requires tracking the changes of all states over the rolling time window of all bookings and rentals. The state space of the model grows exponentially as the dimensionality increases.

To tackle the curse of dimensionality, we propose an LR approach to decompose the resources over days and across stations by decoupling the decisions for each booking (product) via Lagrangian multipliers. Inspired by Topaloglu (2009) and Kunnumkal and Talluri (2016), we introduce the product‐ and time‐dependent Lagrangian multipliers to decompose the DP into multiple single‐station and single‐day problems. Intuitively, such a decomposition can be viewed as if there existed a virtual station such that all bookings were independent transactions between the virtual station and individual stations. We show that each decomposed problem with respect to a rental day for a station can be formulated as a finite‐horizon single‐resource DP. For days beyond the current booking and rental time window, it suffices to use a single state variable to describe the dynamics of the system with a rolling time window, and the problem can be formulated as an infinite horizon one‐dimensional DP. Given a set of Lagrangian multipliers, the expected total discounted revenue of the whole system is the sum of the expected total discounted revenue from all stations plus the expected total discounted net profit of the virtual station. We show that weak duality holds.

We characterize the structural properties for the optimal value functions of the decomposed problems. In particular, we show that the decomposed value functions are monotone and convex in the Lagrangian multipliers and the expected total discounted revenue is also convex in the Lagrangian multipliers, ensuring that the Lagrangian dual problem is a convex program. The dual problem provides a mechanism to relink the decomposed problems through these optimal Lagrangian multipliers and provide the tightest bound under LR. We show that there exists an optimal set of Lagrangian multipliers, among which those related to the same product sum to the corresponding rental price. We also show that the dual problem can be solved with a subgradient‐based algorithm. The bid prices based on the optimal Lagrangian multipliers serve as an approximation of the optimal bid prices, which allows us to define a bid price control policy.

The product‐ and time‐dependent approach, though analytically appealing, requires computing a large number of Lagrangian multipliers that grow exponentially with the problem size, leading to limited scalability for large networks. To increase the scalability, we propose a second LR approach that only requires the Lagrangian multiplies to be station‐ and leadtime dependent, which allows us to significantly reduce the number of Lagrangian multipliers. We further restrict the Lagrangian multipliers to be either leadtime dependent or station dependent, leading to two other simplified LR approaches. The subgradient method also applies to these three variants.

We then perform a numerical study to examine the performances of the proposed LR‐based bid price policies against other commonly used heuristics in network RM, including the deterministic linear program (DLP), the PNLP, and the randomized linear program (RLP). The numerical results indicate that the proposed bid price policies outperform the alternative policies in most instances. The second approach, though slightly worse in terms of revenue, is much faster, as expected, making it a strong alternative to the first approach. The third approach yields comparable performance to the second one for small instances, but is outperformed by the latter for larger instances. The last approach has the weakest performance.

To facilitate the understanding of operational characteristics of car rental systems, we provide an empirical case study on a regional car rental network of a major operator. We summarize the characteristics of the bookings among major stations in the network. More specifically, we report the summary statistics for the round‐trip and one‐way bookings between stations, the cumulative bookings for different booking windows, the distribution among LoRs, and the bookings pattern over time. We implement the proposed LR‐based bid price policies and other alternative heuristics using the empirical data. The results confirm the robustness of the superior performance of the proposed LR approaches.

The contributions of our paper to the literature are threefold. First, to the best of our knowledge, this is the first paper that addresses the bid price control problem for a dynamic car rental network RM using the LR approaches. Second, we further advance the developments of LR‐based bid price policies for car rental network RM problems. Although our product‐ and time‐dependent LR approach follows the spirit of Topaloglu (2009) and Kunnumkal and Talluri (2016) for airline RM problems, the analysis and algorithm development are much more sophisticated in a car rental network, which is essentially a stochastic queueing network with advance booking control. To improve the scalability of the LR heuristic, we propose three simpler variants that require much smaller numbers of Lagrangian multipliers. Our numerical study shows that the proposed bid price policies significantly outperform other commonly used heuristics in most of the tested instances. Third, we use real‐world data to provide a case study to validate the model and the performance of the proposed bid price policies, providing more practical insights into car rental RM.

The remainder of this paper is organized as follows. Section 2 reviews the related literature. Section 3 formulates the problem as a stochastic DP. Section 4 introduces the LR approach with product‐ and time‐dependent Lagrangian multipliers, which decomposes the network problem into a number of single‐station single‐day subproblems. Section 5 discusses the Lagrangian dual problem and proposes a subgradient algorithm, followed by the introduction of three simpler variants. Section 6 provides a numerical study to compare their performance against three network‐based bid price policies. Section 7 implements the model and the bid price policies in a case study with the empirical data. Section 8 concludes the paper. We extend the model to dynamic pricing and staff‐operated shuttling problems, which, along with the technical proofs and full details of the case study, are included in the Supporting Information. Throughout this paper, let

${\mathbb{Z}}_0^{+}$

be the set of nonnegative integers. For any nonnegative integers

$i\le j$

, let

$[i;j]$

denote the running indices

$\{i,\text{…},j\}$

.

RELATED LITERATURE

Our paper is related to two bodies of literature: optimal control of rental or mobility service systems and capacity allocation in network RM.

In the first body of literature, the rental or mobility service systems are modeled as queueing systems. For example, Savin et al. (2005) study capacity management in rental businesses with two customer bases. They formulate a continuous time DP and show that the optimal control policy can be characterized with thresholds. Gans and Savin (2007) further extend this analysis for rental systems to integrate pricing and capacity rationing decisions. George and Xia (2010) formulate a car rental system as a stationary stochastic closed queueing network and provide a performance analysis for fleet sizing and service availability. Balseiro et al. (2021) study dynamic pricing of resource relocation in a hub‐and‐spoke network with an application to ride hailing. Assuming zero‐transit time for each trip, they formulate the problem as an infinite‐horizon DP and develop an LR method to solve it. Of note, none of these models consider advance bookings.

Our study is also related to the field of airline network RM and, more specifically, to the capacity allocation problem. See Talluri and van Ryzin (2004) for an excellent review of early contributions. As a result of its limited tractability, most of the studies focus on developing efficient algorithms. Specifically, this literature includes three streams of development.

The first stream of network RM research focuses on static heuristics. A simple heuristic involves formulating the problem as a DLP and using the dual prices of the capacity constraints as the bid prices (Talluri & van Ryzin, 2004). Dynamic bid prices can be generated through reoptimization. Other similar variants include the PNLP (Li & Pang, 2017; Talluri & van Ryzin, 1998, 2004), the RLP (Talluri & van Ryzin, 2004), and the stochastic program (SP) (Haensel et al., 2012).

The second stream of network RM research adopts approximate dynamic programming methods to approximate the optimal value functions of DPs with some parameterized functions. A representative work is Adelman (2007), who approximates the value functions using an affine combination of basis functions and solves the dual of the resulting linear program with column generation to obtain time‐dependent bid prices. He shows that the proposed bid price control policy significantly outperforms DLP. More recently, Kunnumkal and Talluri (2016) propose a piecewise linear approximation to the value function, and develop an efficient separation algorithm to generate constraints “on the fly” to solve the resulting linear program.

The third stream of network RM research decomposes a network problem into multiple single‐resource problems that are more tractable, and then uses the single‐leg models to generate bid prices for each individual resource. A powerful decomposition approach is based on LR. Jiang (2006) applies the LR approach to a PNLP formulation of the airline network RM problem. Topaloglu (2009) appears to be the first to apply the LR approach to the dynamic airline network RM problem, assigning Lagrangian multipliers for the constraints that associate decisions of all legs of the same itinerary to break the interdependency between resources. He shows that the approximate value function is the sum of the value functions obtained from the decomposed problems for the corresponding resources and provides an upper bound for the optimal value function. The bid prices derived from the approximate value function are time‐ and capacity dependent. The numerical study shows that the proposed bid price policy outperforms not only the DLP‐based bid price policy but also that based on the affine linear approximation of Adelman (2007). In a similar fashion, alternative Lagrangian decomposition approaches have been developed (see, e.g., Kunnumkal & Topaloglu, 2010a, 2010b and the references therein). It is interesting to note that there exists a close connection between the approximate linear programming and LR approaches. Tong and Topaloglu (2014) show that the LR approach of Kunnumkal and Topaloglu (2010b) results in the same bid prices as those from the affine approximation of Adelman (2007). Kunnumkal and Talluri (2016) also find that the piecewise linear approximation and the LR in Topaloglu (2009) lead to the same linear program. Both studies observe that the LR approach is more computationally efficient than approximate linear programs.

Compared with airline network RM, car rental RM has a significantly larger state space as a result of the features of LoRs and mobility of inventories among stations that require one to account for both the spatial‐ and intertemporal linkages of resources. Schmidt (2009) proposes DLP and PNLP formulations to generate bid price heuristics for car rental network booking control problems. Haensel et al. (2012) propose a two‐stage SP formulation to generate heuristic booking limit policies. Both papers restrict the models to a single booking and rental time window, and thus ignore the effects of current decisions on the future beyond the current booking and rental time window. More recently, Guerriero and Olivito (2014) incorporate one‐way rentals into booking controls and propose a DLP method for both booking limit and bid price control policies. They also present a DP formulation of the problem over a finite time window, but no attempt is made to solve it. To the best of our knowledge, the only studies on dynamic capacity control policies in a car rental setting are Steinhardt and Gönsch (2012) and Li and Pang (2017). However, both of these are restricted to the single‐station problem. Specifically, Steinhardt and Gönsch (2012) simultaneously consider bid price control and product upgrade decisions, and then formulate the problem as a finite horizon DP and solve it via the standard decomposition approaches (see, e.g., Talluri & van Ryzin, 2004). Li and Pang (2017) appear to be the first to directly address the dynamic booking limit control for car rental RM problem. They first formulate the problem as an infinite‐horizon stochastic DP with a rolling‐over booking and rental time window, and then propose a decomposition approach to decomposing the problem into multiple single‐day problems by treating a product of multiday LoR as a set of independent products of only single‐day LoR. Our paper extends this literature to car rental network RM problems.

THE MODEL

Problem description

Consider a car rental network with S rental stations distributed across different geographic locations, indexed by

$s\in [1;S]$

, and a fleet of identical rental cars. The total number of cars operating in the network, the fleet size, is fixed at C.

The car rental network is operated under a typical point‐to‐point model such that customers can book in advance or on the spot, and pick up rental cars from and return them to any of the stations. A typical booking request specifies the pick‐up station (origin o), return station (destination d), leadtime of pick‐up day (n), and LoR (ℓ). A car rental booking quadruple

$(o,d,n,\ell )$

can be viewed as a product, indexed by k for notational convenience. In particular, the product is a round‐trip rental if

$o=d$

and a one‐way rental otherwise. Customers are allowed to make a booking at most N days before the pick‐up day with the maximum L days of LoR. Cars are picked up at the beginning of a day and returned at the end of the last day of their rental period. Cars returned in any given day cannot be picked up in the same day but are available from the next day. All cars are returned on time according to the LoR specified in the booking request.

For convenience, let

${\mathcal{K}}_{RT}^s$

denote the set of round‐trip rentals at station s, and

${\mathcal{K}}_{RT}={\cup }_s{\mathcal{K}}_{RT}^s$

denote the set of all round‐trip rentals in the network. Let

${\mathcal{K}}_{OW}$

be the set of all one‐way rentals. In particular, for one‐way rentals, let

${\mathcal{K}}_{OB}^s$

denote the set of outbound rentals from station s and

${\mathcal{K}}_{IB}^s$

the set of inbound rentals to station s. Clearly,

${\mathcal{K}}_{OW}={\cup }_s{\mathcal{K}}_{IB}^s={\cup }_s{\mathcal{K}}_{OB}^s$

. The set of all products available for booking is

$\mathcal{K}={\mathcal{K}}_{RT}\bigcup {\mathcal{K}}_{OW}$

.

For simplicity, we restrict our analysis to the setting with only one fare class for each product. Our model can be readily generalized to the setting with multiple fare classes for each product, as in the classic capacity allocation models in airline RM (see, e.g., Feng & Xiao, 2000, and Talluri & van Ryzin, 2004, and references therein). In addition, we only consider one type of car (car group), as an upgrade/substitution is beyond the scope of this work. Let

$r^k$

be the rental price for product k. On arrival of a booking request, the revenue manager needs to determine whether to accept or reject it. Note that a booking request can be accepted only when there is at least one available car in the origin station on all its rental days; that is, overbooking is not allowed. If the booking of product k is accepted, the customer pays

$r^k$

upfront; otherwise, the booking is rejected and the customer leaves without service.

In car rental operations, it is possible to perform staff‐operated shuttling to rebalance the car distribution within the network, which may incur significant additional operating costs. Our model does not account for the shuttling decision. Instead, we take full advantage of one‐way rentals, which allow us to use bid price control to maximize revenue while redistributing the fleet. Nevertheless, in the Supporting Information, we provide an extended model to address staff‐operated shuttling.

Stochastic dynamic programming formulation

The problem alluded to in the previous section can be formulated as a stochastic DP. We consider an infinite time horizon with a rolling time window of

$N+L+1$

 days.

To account for the temporal variations and seasonality of car rental demand, we consider a demand cycle of

$\mathcal{T}$

days. Depending on the economic and geographic characteristics of the region where the car rental network is operated (e.g., metropolitan area vs. tourist destinations), the demand cycle can be on a weekly, seasonally, or yearly basis. To avoid confusion, we call each day in a cycle a season to highlight the seasonality of car rental demand. Let

$\tau \in [1;\mathcal{T}]$

be the index of the season in a cycle. Each day is divided into T discrete decision epochs with index

$t\in [1;T]$

. Both τ and t are arranged in the descending order.

Customer requests arrive according to inhomogeneous Poisson processes. Consider a discrete approximation to the Poisson arrivals by assuming that the time interval of each epoch is small enough such that there is at most one customer arrival in each epoch. The probability of a customer arrival in epoch t of season τ, or

$(\tau ,t)$

, for product

$k=(o,d,n,\ell )$

is

${\lambda }_{\tau ,t}^k$

.

The system state can be represented by an

$S\times (N+L+1)$

matrix

$\mathbf{x}={({\mathbf{x}}^s,s=1,\text{…},S)}^{\mathrm{T}}$

, where

${\mathbf{x}}^s=(x_0^s,\text{…},x_{N+L}^s)$

is the row vector for station s, with

$x_m^s$

being the number of available cars in station s on day

$m=0,1,\text{…},N+L$

from the current day. Let

${\mathbf{x}}_m={(x_m^1,\text{…},x_m^S)}^{\prime }$

be the number of cars available across the stations on day m. Note that

${\sum }_{s=1}^S{x}_{N+L}^s=C$

since all the current bookings would have been completed before that day. The state space of the system is

1

A round‐trip booking of

$(s,s,n,l)$

, if accepted, leads to a state transition for station s,

2

Similarly, a one‐way booking of

$(o,d,n,\ell ),d\ne o$

, if accepted, leads to the following state transitions for both origin and destination stations while the states of other stations remain unchanged.

3

For notational convenience, we define an

$S\times (N+L+1)$

‐dimensional unit matrix

${\mathbf{e}}^k$

for each product k. For a round‐trip rental

$k=(s,s,n,\ell )$

,

${\mathbf{e}}^k={(\mathbf{0},\text{…},\mathbf{0},{\mathbf{e}}^{k,s},\mathbf{0},\text{…},\mathbf{0})}^{\prime }$

, where 0 is the all‐zeros row vector and

${\mathbf{e}}^{k,s}=(0,\text{…}0,1,1,\text{…},1,0,\text{…},0)$

is the s‐th row vector with the

$(n+1)$

‐th to

$(n+\ell -1)$

‐th components being ones and the rest being zeros. For a one‐way rental

$k=(o,d,n,\ell )$

,

${\mathbf{e}}^k={(\mathbf{0}\text{…},\mathbf{0},{\mathbf{e}}^{k,o},\mathbf{0},,\text{…},\mathbf{0},-{\mathbf{e}}^{k,d},\mathbf{0},\text{…},\mathbf{0})}^{\prime }$

, where

${\mathbf{e}}^{k,o}=(0,\text{…},0,1,\text{…},1)$

is the o‐th row vector (for the origin station) with the first n elements being zeros and the rest being ones and

${\mathbf{e}}^{k,d}=(0,\text{…},0,1,\text{…},1)$

is the d‐th row vector (for the destination station) with the first

$n+\ell -1$

elements being zeros and the rest being ones. Since a round‐trip rental can be viewed as a one‐way rental returned to the same station, we have

${\mathbf{e}}^{k,s}={\mathbf{e}}^{k,o}-{\mathbf{e}}^{k,d}$

when

$o=d=s$

.

Let

$u_{\tau ,t}^k\in \{0,1\}$

denote the booking decision for a request of product k arriving at time

$(\tau ,t)$

with

$u_{\tau ,t}^k=1$

if the booking is accepted, and

$u_{\tau ,t}^k=0$

otherwise. The system state transits as

$$\stackrel{\sim }{\mathbf{x}}=\mathbf{x}-u_{\tau ,t}^k{\mathbf{e}}^k.$$

4

Note that the booking decision is subject to the availability of cars on the corresponding rental days. Given the state x, the constraint set for the booking decision

$u_{\tau ,t}^k$

for product k is

5

Following Li and Pang (2017), we assume that the objective of the revenue manager is to maximize the expected total discounted revenue over an infinite horizon with a daily discount factor

$\gamma \in (0,1)$

. Let

$V_{\tau ,t}(\mathbf{x})$

denote the expected total discounted revenue starting in state x from time

$(\tau ,t)$

onwards under the optimal policy. The optimality equations for

$V_{\tau ,t}$

are as follows. For all

$\tau \in [1;\mathcal{T}],t\in [1;T]$

,

6a

6b

where

$V_{0,T}=V_{\mathcal{T},T}$

. We have introduced an auxiliary epoch (τ, 0) to represent the end of day τ; it becomes the first epoch of the following day

$(\tau -1,T)$

after the time window rolls forward. The recursions of (6a) control the bookings arriving in each decision epoch within a day; the recursions (6b) calculate the expected total discounted revenue from the following day.

The infinite‐horizon cyclic dynamic programming formulation (6) accounts for not only variations of booking demand over time within a day and across days but also the rolling time window nature of the car rental operations. It captures the salient features of car rental network RM: advance bookings, LoRs, and mobility of cars among stations. It is related to some existing models in the literature as follows.

For

$S=1$

, the model reduces to the single‐station problem with only round‐trips, as studied by Li and Pang (2017), who propose an infinite‐horizon cyclic DP under booking limit controls. In particular, when

$L=1$

(i.e., all cars are picked up and returned on the same day), the model (6) can be decomposed into multiple single‐resource problems, each corresponding to a specific future day, which is similar to the single‐leg capacity allocation model in airline RM (see, e.g., Talluri & van Ryzin, 2004). When

$N=0$

(i.e., there is only one station with only round‐trips and only same‐day bookings are allowed), the model is similar to the admission control problem of rental service systems in Savin et al. (2005), who formulate the problem as an infinite‐horizon DP with Poisson arrivals and exponentially distributed service times.

For

$S>1$

, when

$L=1$

, the model does not reduce to the network capacity allocation model in airline RM (see, e.g., Talluri & van Ryzin, 2004) as the rental cars are moving between stations in the network, which still requires the rolling time window to track the movement of cars. When

$N=0$

, the model can be seen as a specific closed queueing network; see, for example, George and Xia (2010) for a single‐class model for a car rental system with a homogeneous Poisson arrival process and random LoRs. They provide a performance analysis for a stationary system to address the optimal fleet sizing problem. When

$N=0,L=1,\mathcal{T}=1$

, and the network is of the spoke‐and‐hub type (i.e., each car can only travel between a spoke and a hub), the model reduces to the setting studied by Balseiro et al. (2021), who propose an LR approach to reallocating vehicles through dynamic pricing to maximize long‐run average profit.

These special cases demonstrate the generality of our model. They also imply that it is the LoR and the mobility of rental cars in the network that drive the rolling time window of the system. The need to account for advance booking and fleet rebalancing at the same time makes car rental RM much more challenging. It is also clear that, because of the queueing feature (i.e., the LoR), it is natural and convenient to consider an infinite horizon for the car rental system (see, e.g., Balseiro et al., 2021; Gans & Savin, 2007; Li & Pang, 2017; Savin et al., 2005). Remark 1 Finite‐Horizon Formulation

One can readily reformulate the problem as a finite‐horizon DP. To this end, it suffices to replace

$V_{1,0}(\mathbf{x})$

by a proper terminal value function that can account for the effects of the terminal state x that will be carried over to the future. Then it suffices to use the recursions (6a) to represent the optimality equations for the finite‐horizon DP.

Given any x at time

$(\tau ,t)$

, the optimal booking control for product k can be specified as

7

where

$V_{\tau ,t-1}(\mathbf{x})-V_{\tau ,t-1}(\mathbf{x}-{\mathbf{e}}^k)$

is the optimal bid price of the resources for product k. As computing the optimal bid prices requires computing the value function

$V_{\tau ,t}(\mathbf{x})$

, which is in general intractable, an effective approach is to develop heuristic algorithms to estimate the bid price for each resource.

We next provide an illustrative running example that will be used throughout this paper. Example 1 Running Example

Consider a car rental network with two stations (

$S=2$

) and two cars (

$C=2$

). Upon arrival, each customer can book a car either for the current day or the next (

$N=1$

) with a rental of either one day or two (

$L=2$

). Each day has two booking epochs (

$T=2$

) and the length of demand cycle is one day (

$\mathcal{T}=1$

). The arrival probabilities for round‐trips are higher than those for one‐way trips since the round‐trip demand tends to be higher than the one‐way demand. Station 1 is a more popular location with higher round‐trip and inbound demand than Station 2. Further, the daily rental price decreases with the LoR (given r as the product rental price) and one‐way rentals are more expensive than round‐trips. Table 1 summarizes the product details. Figure 1a illustrates the network and products. The arrows with solid lines stand for the products originating from Station 1 and the arrows with dashed lines represent the products originating from Station 2. Figure 1b visualizes how the time horizon rolls forward over time.

TABLE 1

Products for the running example

k	o	d	n	l	λ	r	k	o	d	n	l	λ	r
1	1	1	0	1	0.11	60	9	2	2	0	1	0.06	50
2	1	1	0	2	0.11	100	10	2	2	0	2	0.06	85
3	1	1	1	1	0.11	60	11	2	2	1	1	0.06	50
4	1	1	1	2	0.11	100	12	2	2	1	2	0.06	85
5	1	2	0	1	0.01	85	13	2	1	0	1	0.02	85
6	1	2	0	2	0.01	150	14	2	1	0	2	0.02	150
7	1	2	1	1	0.01	85	15	2	1	1	1	0.02	85
8	1	2	1	2	0.01	150	16	2	1	1	2	0.02	150

FIGURE 1

The running example

LR DECOMPOSITION

There are two types of interdependencies in the system that drive the high dimensionality: a spatial interdependency (the linkage between stations due to one‐way rentals) and a temporal interdependency (the linkage between rental days due to multiday LoRs). The decomposition approach proposed by Li and Pang (2017) for a single‐station car rental RM model only accounts for the intertemporal dependency while the typical LR approach in airline RM (e.g., Topaloglu, 2009) can account for the spatial interdependency. The core idea of LR approaches is to decouple the admission decision for each product via a set of Lagrangian multipliers corresponding to the resources used by the product. Topaloglu (2009) proposes an LR approach with product‐ and time‐dependent Lagrangian multipliers. We adopt such an approach to decompose the car rental network RM problem into single‐station single‐day (i.e., single‐resource) subproblems.

To illustrate the idea of the LR approach, we introduce a virtual station

$\overline{s}$

with unlimited capacity. For a one‐way rental

$(o,d,n,\ell )$

, we split it into three trips as

$(o,\overline{s},n,0)\to (\overline{s},\overline{s},n,\ell )\to (\overline{s},d,n+\ell ,0)$

. The first trip is a one‐way rental from station o to

$\overline{s}$

, the second trip is a round‐trip rental of ℓ days from and to

$\overline{s}$

, and the last trip is another one‐way rental, from

$\overline{s}$

to station d. All rental revenue is collected by the virtual station. For the outbound station, it essentially reduces the inventory by one for all the days in station o from n onwards. See Figure 2 for an illustration. The virtual station plays the same role of infinite‐server nodes (in representing rental time) as in the queueing network literature (see, e.g., George & Xia, 2010). Since customers traveling between rental stations utilize the cars in parallel and independently, traveling processes can be viewed as infinite‐server nodes.

FIGURE 2

Decomposition with a virtual station

We then introduce a set of ancillary decision variables. For any one‐way booking

$k=(o,d,n,\ell )\in {\mathcal{K}}_{OW}$

, let

$u_{\tau ,t}^{k,m}\in \{0,1\}$

,

$m\in [n;N+L]$

, be the binary decision at time

$(\tau ,t)$

to decide whether or not to release a car on day m from the origin station o (i.e., the first trip), and

${\widehat{u}}_{\tau ,t}^{k,m}\in \{0,1\}$

,

$m\in [n+\ell ;N+L]$

, be the binary decision at time

$(\tau ,t)$

to decide whether or not to accept a car on day m for the destination station d (i.e., the last trip). Denote now by

$u_{\tau ,t}^k$

the binary decision at time

$(\tau ,t)$

for the virtual station to decide whether or not to accept the second trip. Clearly, a one‐way booking k is accepted at time

$(\tau ,t)$

if and only if

$u_{\tau ,t}^k=u_{\tau ,t}^{k,n}=\cdots .=u_{\tau ,t}^{k,N+L}={\widehat{u}}_{\tau ,t}^{k,n+\ell }=\cdots ={\widehat{u}}_{\tau ,t}^{k,N+L}=1$

. Similarly, for any round‐trip booking

$k=(s,s,n,\ell )\in {\mathcal{K}}_{RT}$

at station s, let

$u_{\tau ,t}^{k,m}\in \{0,1\}$

,

$m\in [n;n+\ell -1]$

, be the binary decision at time

$(\tau ,t)$

to decide whether or not to release a car on day m. A round‐trip booking k is accepted at time

$(\tau ,t)$

if and only if

$u_{\tau ,t}^k=u_{\tau ,t}^{k,n}=\cdots .=u_{\tau ,t}^{k,n+\ell -1}=1$

. That is, deciding whether a product can be accepted is equivalent to deciding whether each of the involved resources should be accepted simultaneously. Thus, relaxing the binding constraints for the ancillary decision variables allows us to decompose the problem into single‐resource problems.

Denote by

${\mathbf{u}}_{\tau ,t}^k$

the vector of actions to take at time

$(\tau ,t)$

for a product‐k booking request:

8

For any x and k, define the action set

9

Using the above ancillary decision variables, DP (6) can be rewritten as

10a

10b

10c

10d

10e

where

${\mathbf{e}}_m^s$

is an

$S\times (N+L+1)$

matrix with one at component

$(s,m)$

and zeros elsewhere.

The Lagrangian multipliers for constraints (10b) to (10d) are denoted by

$w_{\tau ,t}^{k,m},{\widehat{w}}_{\tau ,t}^{k,m}$

, and

$w_{\tau ,t}^{k,m}$

, respectively. Define three sets of products for station s and day m as

11

Each set includes all the round‐trip/outbound/inbound rentals, which, if accepted, will change the state on day m in station s. Note that

${\mathcal{K}}_{IB}^{s,0}\equiv \varnothing ,{\mathcal{K}}_{RT}^{s,N+L}\equiv \varnothing ,\forall s$

. Let

${\mathcal{K}}^{s,m}={\mathcal{K}}_{RT}^{s,m}\cup {\mathcal{K}}_{OB}^{s,m}\cup {\mathcal{K}}_{IB}^{s,m}$

. For instance, in Running Example 1, we have

${\mathcal{K}}_{RT}^{1,0}=\{1,2\},{\mathcal{K}}_{RT}^{1,1}=\{2,3,4\},{\mathcal{K}}_{OB}^{1,0}=\{5,6\},{\mathcal{K}}_{OB}^{1,1}=\{5,6,7,8\},{\mathcal{K}}_{IB}^{1,1}=\{13\}$

.

Define the set of Lagrangian multipliers as

$\mathbf{w}=({\mathbf{w}}^1,\text{…},{\mathbf{w}}^s,\text{…},{\mathbf{w}}^S)$

, where

$${\mathbf{w}}^s=({\mathbf{w}}_1^s,\text{…},{\mathbf{w}}_{\tau }^s,\text{…},{\mathbf{w}}_{\mathcal{T}}^s),$$

12

13

with

${\mathbf{w}}_{\tau ,t}^{s,m}=(w_{\tau ,t}^{k,m},\forall k\in {\mathcal{K}}_{RT}^{s,m}\cup {\mathcal{K}}_{OB}^{s,m})\cup ({\widehat{w}}_{\tau ,t}^{k,m},\forall k\in {\mathcal{K}}_{IB}^{s,m})$

. For each triple

$(s,\tau ,t)$

, the number of Lagrangian multipliers for round‐trips is

${\sum }_{n=0}^N{\sum }_{\ell =1}^L\ell$

, that for outbound trips is

${\sum }_{n=0}^N{\sum }_{\ell =1}^L(N+L+1-n)$

, and that for inbound trips is

${\sum }_{n=0}^N{\sum }_{\ell =1}^L(N+L+1-n-\ell )$

, which implies that there are

$S\times \mathcal{T}\times T\times L(N+1)(N+2L+2)$

Lagrangian multipliers in total. For instance, in Running Example 1, there are 112 Lagrangian multipliers.

In particular, for each round‐trip booking

$k=(s,s,n,\ell )$

,

$w_{\tau ,t}^{k,m}$

is the Lagrangian multiplier (a compensation for a unit of resource at station s) on day

$m\in [n;n+\ell -1]$

. For each one‐way booking

$k=(o,d,n,\ell )$

,

$w_{\tau ,t}^{k,m}$

is the Lagrangian multiplier (a compensation for a unit of resource at the origin station o) on day

$m\in [n;N+L]$

, and

${\widehat{w}}_{\tau ,t}^{k,m}$

is the Lagrangian multiplier (a charge for the destination station d) on day

$m\in [n+l;N+L]$

. Note that, from day

$N+L$

onwards, the inventory level of each station is tracked by the common variable

${\mathbf{x}}_{N+L}$

, which only changes with the accepted one‐way bookings on the current day. As a result, the Lagrangian multipliers

$w_{\tau ,t}^{k,N+L}$

and

${\widehat{w}}_{\tau ,t}^{k,N+L}$

are used to capture the aggregate effects of the current outbound and inbound bookings on the inventory levels for day

$N+L$

and onwards. They can be interpreted as the aggregate compensation (charge) to the origin (destination) for the capacity losses (gains) for day

$N+L$

and onwards due to the outbound (inbound) bookings made at time

$(\tau ,t)$

.

The key idea of LR is to relax the constraints (10b) to (10d), which results in the Lagrangian problem with the value function

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

satisfying the Bellman equations for any given w:

14a

14b

The following proposition shows that the value function

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

constitutes an upper bound of

$V_{\tau ,t}(x)$

for any given x and w, which can be interpreted as a weak duality property. Proposition 1 Weak Duality

For any

$(\mathbf{w},\mathbf{x})$

,

$V_{\tau ,t}(\mathbf{x})\le V_{\tau ,t}(\mathbf{w},\mathbf{x})$

for all τ and t.

We next show that

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

can be decomposed into single‐resource problems. Consider a particular station s and a rental day into the future (called the service day hereafter). Suppose we stand on the service day and look back to identify all the bookings that will, once accepted, change the car availability on this day. For round‐trips, the earliest bookings for such may be made

$N+L-1$

days ago and the latest bookings may be made on the service day. Therefore, all bookings made on the service day need to be counted, regardless of their LoR. For the day prior to the service day, two types of bookings are included. The first type picks up cars on the service day with any LoR, while the second type picks up cars 1 day before the service day with

$l\ge 2$

. In general, for bookings made m days ahead of the service day, those with

$n+\ell -1\ge m$

are included.

It is more straightforward to identify these bookings for one‐way rentals. For outbound rentals, such bookings include all of those with a pick‐up day on or prior to the service day, while for inbound rentals, such bookings include all of those with a return date prior to the service day.

Denote by

$(m,\tau ,t)$

the decision epoch t on day m of season τ, and by

$(m^{\prime },{\tau }^{\prime },t^{\prime })<(m,\tau ,t)$

an epoch after

$(m,\tau ,t)$

(i.e., closer to the service day). Let

$v_{\tau ,t}^{s,m}({\mathbf{w}}^s,x)$

be the value function for station s in epoch

$(m,\tau ,t)$

when there are x cars still available. The optimal revenue functions for this single resource satisfy the following Bellman equations:

15a

15b

with

$v_{0,T}^{s,m}=v_{\mathcal{T},T}^{s,m}$

and the terminal value

$v_{\tau ,0}^{s,0}({\mathbf{w}}^s,x)=0$

.

The state variable x takes values from the set

$\mathcal{C}=\{0,1,\text{…},C-1,C\}$

. We have augmented the state to include

${\mathbf{w}}^s$

, to highlight that the value function

$v_{\tau ,t}^{s,m}$

is dependent on the Lagrangian multipliers. It is worth mentioning that

$v_{\tau ,t}^{s,m}({\mathbf{w}}^s,x)$

only depends on those Lagrangian multipliers defined for the remaining booking epochs. In particular, in the last epoch,

$v_{\tau ,0}^{s,0}$

does not depend on any Lagrangian multiplier.

The problem (15) can be seen as a single‐leg capacity allocation model in the airline RM literature (see, e.g., Talluri & van Ryzin, 2004). Clearly, given the state

$({\mathbf{w}}^s,x)$

in time

$(m,\tau ,t)$

, it is optimal to accept a round‐trip booking request for product

$k\in {\mathcal{K}}_{RT}^{s,m}$

if and only if

$w_{\tau ,t}^{k,m}\ge v_{\tau ,t-1}^{s,m}({\mathbf{w}}^s,x)-v_{\tau ,t-1}^{s,m}({\mathbf{w}}^s,x-1)$

. Similarly, it is optimal to accept an outbound booking request for product

$k\in {\mathcal{K}}_{OB}^{s,m}$

if and only if

$w_{\tau ,t}^{k,m}\ge v_{\tau ,t-1}^{s,m}({\mathbf{w}}^s,x)-v_{\tau ,t-1}^{s,m}({\mathbf{w}}^s,x-1)$

, and it is optimal to accept an inbound booking request for product

$k\in {\mathcal{K}}_{IB}^{s,m}$

if and only if

${\widehat{w}}_{\tau ,t}^{k,m}\le v_{\tau ,t-1}^{s,m}({\mathbf{w}}^s,x+1)-v_{\tau ,t-1}^{s,m}({\mathbf{w}}^s,x)$

.

From day

$N+L$

onwards, though beyond the regular booking and rental time window, the inventory level of each station may be influenced by the one‐way rentals within the regular time window. Without causing any confusion, let

$v_{\tau ,t}^{s,N+L}({\mathbf{w}}^s,x)$

denote the expected total discounted revenue (calculated with the corresponding Lagrangian

${\mathbf{w}}^s$

) for station s from

$N+L$

onwards, starting with the inventory level x at time t in season τ. The optimal revenue functions

$v_{\tau ,t}^{s,N+L}({\mathbf{w}}^s,x)$

satisfy the following Bellman equations:

16a

16b

where

$v_{0,T}^{s,N+L}=v_{\mathcal{T},T}^{s,N+L}$

.

Note that the recursion (16a) is similar to (15a), except that x denotes the common inventory level of station s from day

$N+L$

onwards. The recursion (16b) differs from (15b) because the timeline rolls into another regular booking and rental time window at the end of the current day; therefore, the expected total discounted revenue consists of the expected total discounted revenue in the regular time window,

$v_{\tau -1,T}^{s,N+L-1}({\mathbf{w}}^s,x)$

, plus the total discounted revenue from day

$N+L$

onwards,

$v_{\tau -1,T}^{s,N+L}({\mathbf{w}}^s,x)$

. That is, in light of the mobility of cars, the capacity of each station on a specific future day varies over time even before its selling season begins. Such a salient feature differentiates car rental network RM models from airline network RM ones (e.g., Topaloglu, 2009), where the capacity of each flight is fixed at the beginning of its selling season.

Our approach decomposes the network problem for each station into

$(N+L+1)$

single‐dimensional problems. The problems for the first

$N+L$

days are single‐resource problems, each corresponding to a day within the booking and rental time window. Because of this cyclic structure, it suffices to solve the finite‐horizon DP (15) to obtain the optimal values of these single‐resource problems. The last problem is the aggregate model for day

$N+L$

onwards, and, because of the rolling window, the value function is obtained by solving the infinite horizon DP (16).

The single‐dimensional problems have the following structural properties. Lemma 1 Structural Properties

For any

$s,m,\tau ,t$

and

${\mathbf{w}}^s$

,

$v_{\tau ,t}^{s,m}({\mathbf{w}}^s,x)$

is concave in x and satisfies

$v_{\tau ,t}^{s,m}({\mathbf{w}}^s,x+1)-v_{\tau ,t}^{s,m}({\mathbf{w}}^s,x)\ge v_{\tau ,t-1}^{s,m}({\mathbf{w}}^s,x+1)-v_{\tau ,t-1}^{s,m}({\mathbf{w}}^s,x)$

.

Lemma 1 reveals the two fundamental structural properties in RM: the concavity in inventory levels (which reflects the resource scarcity) and the supermodularity in remaining time and inventory levels (which reflects the time perishability) (Pang et al., 2015). Note that for the finite‐horizon case (i.e.,

$m<N+L$

), the result follows immediately from the RM literature (see, e.g., Pang et al., 2015; Talluri & van Ryzin, 2004). For the infinite‐horizon case (i.e.,

$m=N+L$

), it can be proved by showing that the structural properties are preserved by the backward induction of infinite‐horizon dynamic programming (see, e.g., Bertsekas & Tsitsiklis, 1996). Then the higher the inventory level at any given time or the less the remaining time for any given inventory level, the more likely car rental operator would be to accept a round‐trip or an outbound booking request and reject an inbound booking request.

The following lemma shows that the value functions of the single‐dimensional problems are convex and monotone in the Lagrangian multipliers with limited sensitivities.

Lemma 2 Sensitivity

For any

$s,m,\tau ,t$

, and x,

$v_{\tau ,t}^{s,m}({\mathbf{w}}^s,x)$

is convex in

${\mathbf{w}}^s$

, and is increasing in

$w_{{\tau }^{\prime },t^{\prime }}^{k,m^{\prime }},k\in {\mathcal{K}}_{RT}^{s,m^{\prime }}\cup {\mathcal{K}}_{OB}^{o,m^{\prime }}$

, decreasing in

${\widehat{w}}_{{\tau }^{\prime },t^{\prime }}^{k,m^{\prime }},k\in {\mathcal{K}}_{IB}^{d,m^{\prime }}$

for all booking epochs

$(m^{\prime },{\tau }^{\prime },t^{\prime })\le (m,\tau ,t)$

.

The next proposition shows that the value function

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

can be represented via the value functions of the single‐resource problems.

Proposition 2 Decomposition

For all τ and t, the value function

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

satisfies:

17

where

18

We next provide the intuition for the decomposition representation for the optimal LR revenue function (17) using the idea of virtual stations. Through LR, we decompose the dynamic network into a set of separated single‐station single‐day units. The bookings that associate resources across stations and across different days are decomposed as individual transactions with the virtual station. The Lagrangian multiplier for each resource serves as the compensation for occupying a unit of capacity of this resource or the charge for receiving an additional unit of capacity (for the inbound cars), while the actual rental prices

$r^k$

are collected by the virtual station. As a result, the expected total discounted revenue

$V_{\tau ,t}$

is the sum of the expected total discounted net compensations for each resource (corresponding to each day) from the current day onwards over all stations (the first term in (17)), and the expected total discounted net profit collected by the virtual station (the remaining terms in (17)). More specifically,

${\sum }_{t^{\prime }=1}^t{H}_{\tau ,t^{\prime }}(\mathbf{w})$

is the total expected profit collected by the virtual station in the rest of current day (of season τ),

${\sum }_{{\tau }^{\prime }=1}^{\tau -1}{\gamma }^{\tau -{\tau }^{\prime }}{\sum }_{t^{\prime }=1}^t{H}_{{\tau }^{\prime },t^{\prime }}(\mathbf{w})$

is the total expected discounted profit collected by the virtual station from the next day toward the end of the current demand cycle, while

$\frac{{\gamma }^{\tau }}{1-{\gamma }^{\mathcal{T}}}{\sum }_{{\tau }^{\prime }=1}^{\mathcal{T}}{\gamma }^{\mathcal{T}-{\tau }^{\prime }}{\sum }_{t^{\prime }=1}^T{H}_{{\tau }^{\prime },t^{\prime }}(\mathbf{w})$

is the total expected discounted profit collected by the virtual station from the beginning of next demand cycle onwards. Such a treatment allows us to reduce the dimensionality of the dynamic network problem, while capturing the intrinsic relationships among individual resources across stations and days. Besides computational tractability, the analytical structural properties of the decomposed single‐resource problems ensure that the intuition built on the single‐leg RM models remains true for the network problem.

LAGRANGIAN DUAL PROBLEM

The weak duality property implies that there may exist a positive gap between the relaxed value function

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

and the true optimal value function

$V_{\tau ,t}(\mathbf{x})$

. The second step of the LR approach is to solve the dual problem by choosing the Lagrangian multipliers to reduce this duality gap. In what follows, we first propose a subgradient‐based method to find the optimal product‐ and time‐dependent Lagrangian multipliers for the dual problem of the Lagrangian

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

. The computation effort for the dual problem depends on the number of products and the length of the booking window. To reduce the computational burden, one needs to make a trade‐off between the number of Lagrangian multipliers and the duality gap. To this end, we propose three variants of LR‐based bid price policies that can significantly improve computational efficiency.

Product‐ and time‐dependent Lagrangian multipliers (LR1)

The optimal Lagrangian multipliers can be chosen by solving the convex Lagrangian dual problem:

$$\begin{array}{c}\hfill V_{\tau ,t}^{\ast }(\mathbf{x})=\underset{\mathbf{w}}{\min }\{V_{\tau ,t}(\mathbf{w},\mathbf{x})\}.\end{array}$$

19

Clearly, the optimal value of the dual problem (19),

$V_{\tau ,t}^{\ast }(\mathbf{x})$

, provides the tightest upper bound for the optimal revenue function in the original problem under LR. We next show that the dual problem is a convex program. Proposition 3 Lagrangian Convexity

For all

$\tau ,t$

, and x,

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

is convex in w.

The convexity of

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

in w ensures that the dual problem (19) is a convex optimization program. Its solution, denoted by

$\stackrel{*}{\mathbf{w}}$

, can then be used to construct bid price control policies. The following proposition characterizes the optimal Lagrangian multipliers of problem (19).

Proposition 4 Optimal Lagrangian Multipliers

There exist optimal Lagrangian multipliers to the dual problem (19) satisfying the following relationships for all τ and t:

20

Proposition 4 shows that the optimal Lagrangian multipliers for resources of product k can be obtained by decoupling its price

$r^k$

, which implies that the optimal LR essentially decomposes the dynamic network problem by slicing the price of each product and then assigning each slice to the corresponding resource. Recall that the Lagrangian multipliers can be interpreted as the compensations and charges between the individual physical stations and the virtual station, and the rental prices can be viewed as aggregate payments for the bookings consisting of resources of multiple stations and over time. Hence, the terms of

$H_{\tau ,t}$

can be interpreted as the net profits received by the virtual station at any time

$(\tau ,t)$

, or equivalently, the penalties for not receiving enough compensation for the return or outbound trips and being charged too much for the inbound trips from each station's perspective, which allows us to capture the intrinsic linkages between resources across stations and over time. The binding conditions of (20) show that the optimal Lagrangian multipliers balance the compensations and charges for individual resources and the aggregate rental price for a bundle of resources so that the net profits of the virtual station remain zeros, which implies that the optimal design of LR by allocating Lagrangian multipliers to each individual resource must be fair between the physical stations as a network and the virtual station.

Under the optimal Lagrangian multipliers, the decomposition representation (17) reduces to

$$\begin{array}{c}\hfill \begin{array}{c}\hfill V_{\tau ,t}(\stackrel{*}{\mathbf{w}},\mathbf{x})=\sum _{s=1}^S\sum _{m=0}^{N+L}{v}_{\tau ,t}^{s,m}({\stackrel{*}{\mathbf{w}}}^s,x_m^s).\end{array}\end{array}$$

21

The convex Lagrangian dual (19) can be solved through standard subgradient optimization; see Jiang (2006) and Topaloglu (2009) for its applications to airline RM problems. To develop a subgradient‐based algorithm, we need to derive a subgradient of the value functions.

For notational convenience, we introduce the matrix form for the Bellman equations (15a) and (16a). For each station s, denote by

${\mathbf{U}}_{\tau ,t}^{s,m}$

a

$|\mathcal{C}|\times |{\mathcal{K}}^{s,m}|$

‐dimensional matrix for the weighted optimal actions under the Lagrangian multipliers

${\mathbf{w}}^s$

in epoch

$(m,\tau ,t)$

. Specifically, the

$(x,k)$

‐th element is

$-{\lambda }_{\tau ,t}^k{u}^k$

, with

$u^k$

being the optimal action for product k in state x. We further denote by

${\mathbf{P}}_{\tau ,t}^{s,m}$

a

$|\mathcal{C}|\times |\mathcal{C}|$

‐dimensional matrix as one‐step state transition probabilities in epoch

$(m,\tau ,t)$

under the optimal policy. Its

$(x,\stackrel{\sim }{x})$

element is given by:

22

Let

${\mathbf{v}}_{\tau ,t}^{s,m}({\mathbf{w}}^s)$

denote the vector

$\{v_{\tau ,t}^{s,m}({\mathbf{w}}^s,x):x\in \mathcal{C}\}$

. The recursions (15a) and (16a) are

23

Let

$\varphi (\tau ,j)=[1+(\tau -j-1)\mathrm{mod}\mathcal{T}]$

be the season of j days after τ. For brevity, the subgradients of

$v_{\tau ,t}^{s,m}({\mathbf{w}}^s,x)$

at

${\mathbf{w}}^s$

are provided in Lemma EC.1 in the Supporting Information. A subgradient of

$V_{\tau ,t}(\mathbf{w},\mathbf{x})$

can then be readily derived from (17) and (EC‐1) to (EC‐3). For simplicity, we provide only the expressions for the subgradient of value function

$V_{\mathcal{T},T}(\mathbf{w},\mathbf{x})$

. Note that each

${\mathbf{w}}_{\tau ,t}^{s,m}$

is involved in the single‐resource value functions

${\mathbf{v}}_{\mathcal{T},T}^{s,m+j}$

where

$j\in \mathcal{J}(\tau )=\{j:j\in [0;N+L-1-m],\tau =\varphi (\mathcal{T},j)\}$

, and the value function

${\mathbf{v}}_{\varphi (\tau ,-N-L+m),T}^{s,N+L}$

. The subgradient vector at

${\mathbf{w}}_{\tau ,t}^{s,m}$

is

24

where the first two terms are from (EC‐1) and (EC‐2), respectively. The last term

${\mathrm{\Psi }}_{\tau ,t}^{s,m}$

is a vector for all

$k\in {\mathcal{K}}^{s,m}$

and its components are defined by

25

The subgradient‐based Algorithm 1 is described in EC.3 of the Supporting Information. The initial values of the Lagrangian multipliers are chosen based on Proposition 4. More specifically, for a round‐trip booking

$k=(s,s,n,l)$

, we let

$w_{\tau ,t}^{k,m}=r^k/l,\forall n\le m\le n+\ell -1$

. For a one‐way booking

$k=(o,d,n,\ell )$

, we let

$w_{\tau ,t}^{k,m}=r^k/(N+L-n+1),\forall n\le m\le N+L$

and

${\widehat{w}}_{\tau ,t}^{k,m}=0,\forall n+\ell \le m\le N+L$

. The initial step size is set as the average price over all products and thus

${\theta }^{(0)}={\sum }_{k\in \mathcal{K}}{r}^k/|\mathcal{K}|$

.

The optimal dual function

$V_{\tau ,t}(\stackrel{*}{\mathbf{w}},\mathbf{x})$

provides an approximate value function to the optimal value function

$V_{\tau ,t}(\mathbf{x})$

. The optimal bid price

${\mathrm{\Delta }}^k{V}_{\tau ,t-1}(\mathbf{x})=V_{\tau ,t-1}(\mathbf{x})-V_{\tau ,t-1}(\mathbf{x}-{\mathbf{e}}^k)$

for a product k can then be approximated by

${\mathrm{\Delta }}^k{V}_{\tau ,t-1}(\stackrel{*}{\mathbf{w}},\mathbf{x})=V_{\tau ,t-1}(\stackrel{*}{\mathbf{w}},\mathbf{x})-V_{\tau ,t-1}(\stackrel{*}{\mathbf{w}},\mathbf{x}-{\mathbf{e}}^k)$

. A heuristic policy, defined as LR1, is then developed such that a booking for product k at state

$\mathbf{x}$

and time

$(\tau ,t)$

is accepted if and only if

$\mathbf{x}-{\mathbf{e}}^k\ge \mathbf{0}$

and

$$r^k\ge V_{\tau ,t-1}(\stackrel{*}{\mathbf{w}},\mathbf{x})-V_{\tau ,t-1}(\stackrel{*}{\mathbf{w}},\mathbf{x}-{\mathbf{e}}^k).$$

26

Applying (17) and (20), the condition (26) can be expressed equivalently as follows:

27

28

Station‐ and leadtime‐dependent Lagrangian multipliers (LR2)

Although the optimal solution to the dual problem (19) has an appealing analytical structure, as demonstrated by Proposition 4, it remains challenging to compute. An effective way to reduce the number of Lagrangian multipliers is to associate Lagrangian multipliers directly with each rental day in each station. Since the fleet size in the car rental network is fixed, we let the Lagrangian multipliers depend only on the leadtime for each station. More specifically, let

${\overline{w}}^{s,m}$

be the Lagrangian multipliers for one unit of car in station s on day m. We have

$w_{\tau ,t}^{k,m}={\widehat{w}}_{\tau ,t}^{k,m}\equiv {\overline{w}}^{s,m},\forall k\in {\mathcal{K}}^{s,m},\tau \in [1;\mathcal{T}],t\in [1;T]$

. As a result, the total number of Lagrangian multipliers reduces to

$S\times (N+L+1)$

. For convenience, we term such an approach LR2. In Running Example 1, there are only eight Lagrangian multipliers under LR2.

It follows immediately from (3) that

$V_{\tau ,t}(\overline{\mathbf{w}},\mathbf{x})$

is convex in

$\overline{\mathbf{w}}$

, which implies that we can employ the subgradient method (i.e., Algorithm 1) to compute the optimal dual solution. The subgradient at

${\overline{w}}^{s,m}$

is

$$\begin{array}{c}\hfill {\overline{g}}^{s,m}=\sum _{\tau =1}^{\mathcal{T}}\sum _{t=1}^T\sum _{k\in {\mathcal{K}}^{s,m}}{\mathbf{g}}_{\tau ,t}^{s,m}(k),\end{array}$$

29

where

${\mathbf{g}}_{\tau ,t}^{s,m}(k)$

refers to its component for product k.

Leadtime‐dependent Lagrangian multipliers (LR3)

We can further reduce the number of Lagrangian multipliers by removing the station dependence in LR2. Let

${\overline{w}}^m$

be the Lagrangian multipliers for one unit of car in any station on day m. We have

${\overline{w}}^{s,m}\equiv {\overline{w}}^m,\forall s\in [1;S]$

. As a result, the number of Lagrangian multipliers reduces to

$N+L+1$

. We term such an approach LR3. In Running Example 1, the number of Lagrangian multipliers under LR3 reduces to three. The subgradient method (Algorithm 1) can be used to compute the optimal dual solution, with the subgradient at

${\overline{w}}^m$

given by

${\overline{g}}^m={\sum }_{s=1}^S{\overline{g}}^{s,m}$

.

Station‐dependent Lagrangian multipliers (LR4)

An alternative way to further reduce the number of Lagrangian multipliers is to remove the leadtime dependence in LR2. Let

${\overline{w}}^s$

be the Lagrangian multipliers for one unit of car on any day in station s. We have

${\overline{w}}^{s,m}\equiv {\overline{w}}^s,\forall m\in [0;N+L]$

. As a result, the number of Lagrangian multipliers reduces to S. We term such an approach LR4. In Running Example 1, the number of Lagrangian multipliers under LR4 reduces to two. The subgradient method (Algorithm 1) can also be used to compute the optimal dual solution, with the subgradient at

${\overline{w}}^s$

given by

${\overline{g}}^s={\sum }_{m=0}^{N+L}{\overline{g}}^{s,m}$

.

Revenue performance comparison for the running example

We next apply the above LR approaches to Running Example 1 and compare them to the optimal policy derived from the original DP (6). To this end, we first obtain the best bid prices of the dual problem under each LR‐based bid price policy as well as the optimal DP policy, and then apply them to a simulated sample of 500 randomly generated demand replications over a 90‐day time horizon. Assuming at the beginning that each station has one car available and there are no outstanding bookings, we calculate the total discounted revenue achieved under each policy. A discount factor of 0.9 has been used to calculate the present value of the revenue on the future days. Table 2 outlines the optimal Lagrangian multipliers under each approach. For brevity, we only present selected results for LR1; the full results are included in Table EC.1 of the Supporting Information. It is obvious that the optimal Lagrangian multipliers under LR1 satisfy Proposition 4. For LR2 and LR3, the Lagrangian multipliers decline over time, reflecting the perishability of capacity. For LR4, the Lagrangian multiplier value is higher for station 1, reflecting the higher demand in this station. The performance results are reported in Table 3, where we can observe that LR1 and LR2 have revenue performance that is slightly lower than the optimum but much better than that of LR3 and LR4, while the computation effort, represented by the number of iterations, under LR1 is almost twice that under LR2 and significantly greater than that of LR3 and LR4.

TABLE 2

Optimal Lagrangian multipliers for the running example

(a) LR1 (for selected products at $t=1$ )									(b) LR2/3/4
k		$w_{1,1}^{k,m}$				${\widehat{w}}_{1,1}^{k,m}$					LR2	LR3	LR4
	$m\to$	0	1	2	3	1	2	3	s	m	${\overline{w}}^{s,m}$	${\overline{w}}^m$	${\overline{w}}^s$
1		60.0							1	0	60.0	65.6	51.2
2		75.9	24.2						1	1	59.5	48.1	51.2
3			59.9						1	2	40.5	31.4	51.2
4			64.3	35.7					1	3	21.8	26.6	51.2
5		23.6	24.2	35.6	30.6	7.4	9.2	12.4	2	0	52.4	65.6	48.0
6		64.0	41.4	35.6	30.6		9.2	12.4	2	1	51.9	48.1	48.0
7			40.3	35.6	30.6		9.2	12.4	2	2	33.1	31.4	48.0
8			74.4	52.1	35.8			12.4	2	3	26.4	26.6	48.0

TABLE 3

Running example results

Optimal dual values				No. iterations				Revenue
LR1	LR2	LR3	LR4	LR1	LR2	LR3	LR4	Optimum	LR1	LR2	LR3	LR4
772	915	936	1008	3943	1962	109	111	731	728	728	709	669

NUMERICAL STUDY

We next provide a numerical study to systematically assess the performances of the proposed LR approaches and compare them to three commonly used heuristics in the network RM literature—DLP, PNLP, and RLP. Detailed descriptions of these heuristics are provided in Section EC.4 in the Supporting Information.

Problem instances

We first introduce the demand‐to‐supply ratio to represent the relative fleet size of the network:

$$\begin{array}{c}\hfill \begin{array}{c}\hfill \rho =\frac{{\sum }_{s=1}^S{\sum }_{m=0}^{N+L}{\sum }_{k\in {\mathcal{K}}_{RT}^{s,m}\cup {\mathcal{K}}_{OB}^{s,m}}{\sum }_{\tau =1}^{\mathcal{T}}{\sum }_{t=1}^T{\lambda }_{\tau ,t}^k}{C\mathcal{T}},\end{array}\end{array}$$

30

where the numerator denotes the expected number of booking requests in a cycle and the denominator denotes the maximum potential supply in the cycle. All round‐trips and outbound rentals are considered while inbound rentals are excluded to avoid double‐counting of one‐way rentals.

The demand‐to‐supply ratio is related to the fleet utilization rate or average fleet utilization, which is commonly used in the car rental industry as a key operational performance indicator. The fleet utilization rate is based on the number of rental days that vehicles are rented compared with the total amount of time that vehicles are available for rent, which typically varies between 50% and 90%. For example, Avis reported that its average fleet utilization was about 70% in 2021 (Avis Budget Group, 2022), while Hertz reported that its fleet utilization rate increased from 53% in 2020 to 77% in 2021 (Hertz, 2022). Bui and Irwin (2021) report that, in 2021, rental demand and prices were soaring while the market was short of inventory. These facts indicate that though actual demand could be much higher, the realized utilization rate could be significantly lower due to the mismatch between demand and supply, which may cause significant lost sales. The demand‐to‐supply ratio can be viewed as the theoretical upper bound of the actual utilization rate, if all demand could be fully met. Hence, to test the performance of the bid price heuristics in different market environments, we vary the demand‐to‐supply ratio between 80% and 500%.

In addition to the demand‐to‐supply ratio, to thoroughly examine the performance of the proposed LR policies against other heuristics, we generate a number of testing instances in different settings, as summarized in Table 4. The demand is generated according to the actual patterns observed in practice. Specifically, the booking requests for round‐trips are higher than those for one‐way trips and increase with a shorter booking leadtime and shorter LoR. For instances with three seasons, the demand in the middle and low seasons are 80% and 60% of that in the high season, respectively. The rental rates per day decline with the LoR, and they are higher for one‐way trips than round‐trips. For each instance, we consider either 12 or 24 booking epochs within a day while allowing ρ value to vary between 0.8 and 5.

TABLE 4

Testing instances

Instance	S	N	L	$\mathcal{T}$	T	ρ
1	2	1	2	1	12/24	(0.8,1,2,3,4,5)
2	2	7	4	1	12/24	(0.8,1,2,3,4,5)
3	2	14	7	1	12/24	(0.8,1,2,3,4,5)
4	2	1	2	3	12/24	(0.8,1,2,3,4,5)
5	2	7	4	3	12/24	(0.8,1,2,3,4,5)
6	2	14	7	3	12/24	(0.8,1,2,3,4,5)
7	3	1	2	1	12/24	(0.8,1,2,3,4,5)
8	3	7	4	1	12/24	(0.8,1,2,3,4,5)
9	3	14	7	1	12/24	(0.8,1,2,3,4,5)
10	3	1	2	3	12/24	(0.8,1,2,3,4,5)
11	3	7	4	3	12/24	(0.8,1,2,3,4,5)
12	3	14	7	3	12/24	(0.8,1,2,3,4,5)

We apply Algorithm 1 to compute the optimal dual solutions for the four LR heuristics. For comparison purpose, we adopt the common termination criteria in all the instances, as detailed in Section EC.3 of the Supporting Information. The optimal dual values and run time are reported in Section 6.2. Due to the high dimensionality, it is unrealistic to compute the optimal policy. Hence, we compare the performance of the heuristic bid price policies via simulation. For each instance, we apply these policies to 500 randomly generated demand replications over a 90‐day time horizon. The network‐based heuristics are reoptimized every 9 days over the horizon, while the dual problems for the LR approaches are only solved once at the beginning of the simulation. The discount factor is 0.9. Assuming at the beginning the fleet is evenly distributed within the network and there are no outstanding bookings, we calculate the expected revenue achieved under each policy. The results are reported in Section 6.3. All the experiments are executed with high performance computing clusters consisting of multiple nodes, each with Intel Xeon X5650 CPUs and 24GB RAM.

Optimal dual values and run time of the LR approaches

Since the optimal dual values of the LR approaches provide upper bounds on the expected total revenue, in Table 5 we report the optimal dual values of each LR approach for all instances with

$T=24$

, and the pair‐wise difference (in %) between two LR approaches.

TABLE 5

The upper bounds (optimal dual values) and pair‐wise comparisons of the LR approaches,

$T=24$

Instance						LR2 vs	LR3 vs	LR4 vs	Instance						LR2 vs	LR3 vs	LR4 vs
$(S,N,L,\mathcal{T})$	ρ	LR1	LR2	LR3	LR4	LR1	LR2	LR3	$(S,N,L,\mathcal{T})$	ρ	LR1	LR2	LR3	LR4	LR1	LR2	LR3
(2,1,2,1)	0.8	17801	18060	18884	18462	1.45	4.56	−2.23	(3,1,2,1)	0.8	17795	18182	18898	19288	2.18	3.93	2.06
	1	15759	15851	17075	16396	0.58	7.72	−3.97		1	15567	16365	16996	17260	5.13	3.86	1.56
	2	10403	10389	10839	11206	−0.13	4.33	3.38		2	11197	10679	10953	11902	−4.63	2.56	8.67
	3	7485	6988	7351	7740	−6.65	5.20	5.29		3	8408	7218	7476	8734	−14.16	3.58	16.82
	4	6251	5996	5746	6604	−4.08	−4.16	14.92		4	7314	5717	6437	6399	−21.84	12.60	−0.59
	5	5709	4698	4938	5739	−17.71	5.11	16.21		5	6622	4876	5057	5995	−26.37	3.72	18.54
(2,7,4,1)	0.8	19171	19747	20312	21313	3.01	2.86	4.93	(3,7,4,1)	0.8	20351	21072	21689	23194	3.54	2.93	6.94
	1	17615	18329	18806	19969	4.05	2.60	6.18		1	18653	19457	19951	22360	4.31	2.54	12.07
	2	13328	12658	13017	14840	−5.03	2.84	14.00		2	12265	13263	13484	15914	8.14	1.66	18.03
	3	11512	10115	10329	12586	−12.13	2.11	21.85		3	9366	10307	10503	12899	10.04	1.91	22.82
	4	9904	8110	8295	10772	−18.11	2.27	29.86		4	7371	8269	8406	10662	12.19	1.65	26.83
	5	9480	7449	7579	9920	−21.43	1.75	30.89		5	6578	7603	7687	9855	15.59	1.10	28.21
(2,14,7,1)	0.8	21890	22250	22713	23215	1.65	2.08	2.21	(3,14,7,1)	0.8	23639	24012	24447	24914	1.58	1.81	1.91
	1	20453	21039	21370	23103	2.87	1.57	8.11		1	21852	22584	22998	24930	3.35	1.83	8.40
	2	15088	16042	16312	19931	6.32	1.68	22.18		2	15845	17028	17211	22652	7.46	1.08	31.61
	3	12241	13273	16485	16908	8.43	24.20	2.56		3	12614	13868	14047	18949	9.94	1.29	34.90
	4	10122	11157	11296	14637	10.22	1.25	29.57		4	10282	11520	11684	17743	12.04	1.43	51.86
	5	8972	9900	10004	14429	10.34	1.06	44.23		5	9019	10225	10350	15528	13.36	1.22	50.03
(2,1,2,3)	0.8	14135	14410	15292	14924	1.95	6.12	−2.40	(3,1,2,3)	0.8	14305	14710	15271	15643	2.83	3.82	2.43
	1	12157	12611	13646	13075	3.73	8.21	−4.19		1	12199	12917	13512	13701	5.89	4.60	1.40
	2	7962	7987	8479	8761	0.31	6.17	3.32		2	8727	8331	8555	9376	−4.53	2.68	9.59
	3	6461	6161	6386	6836	−4.65	3.66	7.05		3	7157	6365	6500	7118	−11.07	2.12	9.52
	4	5216	4636	4796	5089	−11.11	3.45	6.09		4	5821	4711	4881	5584	−19.08	3.62	14.40
	5	4391	4127	3955	4494	−6.01	−4.17	13.63		5	5332	4006	4084	4487	−24.88	1.95	9.87
(2,7,4,3)	0.8	15559	16073	16512	17266	3.30	2.73	4.57	(3,7,4,3)	0.8	16500	17200	17626	18706	4.24	2.47	6.13
	1	14113	14697	15115	16033	4.14	2.84	6.07		1	14790	15554	16016	17878	5.16	2.98	11.62
	2	10920	10475	10699	12192	−4.08	2.14	13.96		2	9959	10860	11037	12987	9.04	1.63	17.67
	3	7734	8339	8506	10336	7.81	2.01	21.51		3	7649	8534	8670	10660	11.57	1.59	22.94
	4	8350	7064	7167	8877	−15.40	1.46	23.86		4	6296	7211	7300	9179	14.53	1.23	25.74
	5	7155	5555	5640	7007	−22.36	1.53	24.25		5	8686	5551	5652	7197	−36.08	1.80	27.34
(2,14,7,3)	0.8	17569	18025	18400	18930	2.59	2.08	2.88	(3,14,7,3)	0.8	19057	19400	19779	20259	1.80	1.95	2.42
	1	16581	17138	17374	18940	3.36	1.38	9.01		1	17752	18278	18598	20281	2.96	1.75	9.05
	2	12453	13156	13377	16325	5.64	1.68	22.04		2	13539	13943	14092	18507	2.99	1.06	31.33
	3	9819	10699	10904	13636	8.96	1.92	25.05		3	12831	11247	11385	15338	−12.34	1.23	34.71
	4	8752	9183	9295	11998	4.93	1.22	29.08		4	11462	9509	9628	13186	−17.04	1.25	36.96
	5	7684	7894	7978	11466	2.74	1.06	43.72		5	10842	8154	8240	12292	−24.79	1.05	49.17

Table 5 shows that, first, LR1 does not always produce the tightest upper bounds, given the negative percentage of numbers comparing the upper bound of LR2 against that of LR1 in the same instance. In those instances, Algorithm 1 for LR1 stops after the first 100 iterations; it does not find any improvement of the dual values before reaching the termination criteria. In the other instances, more iterations are completed and LR1 always leads to the tightest upper bounds. Second, among the simpler variants, LR2 always produces tighter upper bounds than LR3 except in two instances, where Algorithm 1 for the former stops much earlier than that for the latter. Third, in all but five instances, LR3 produces tighter upper bounds than LR4, and the gap between them could be up to 51.9%. In addition, similar results for the optimal dual values are also observed for

$T=12$

, which can be found in Table EC.2 of the Supporting Information.

Table 6 summarizes the total CPU time and the time per iteration that Algorithm 1 takes for instances with

$T=24$

using each LR approach. We can observe that LR1 is much slower than the three variants due to the much greater number of Lagrangian multipliers. In most of the larger instances, LR1 uses up the budget of 3600 s. Among the three variants LR2 takes longer than LR3, which in turn takes longer than LR4. There are few exceptions due to the different number of iterations completed before Algorithm 1 terminates. Nevertheless, in most instances, they spend just a few minutes. Regarding the CPU time per iteration, it shows that LR2, LR3, and LR4 are quicker per iteration than LR1, and the time taken by these three simpler variants is just a fraction of that for the LR1 approach in the largest instances, while there is no obvious difference among the three simpler variants. Further, for all the LR approaches, the CPU time per iteration increases with the problem size, but the magnitude is much larger for LR1. Indeed, the time per iteration is at most 3.17 s for LR2, LR3, and LR4, but can be up to 68.26 s for LR1. It is interesting to note that the time per iteration generally decreases in ρ. This is because a larger ρ translates to a smaller fleet size C, which in turn implies smaller matrices

$\mathbf{P}$

and

$\mathbf{F}$

, and thus a lower complexity in their multiplications. The results for

$T=12$

are robust and can be found in Table EC.3 of the Supporting Information. The results confirm that the scalability is improved significantly by the simpler variants.

TABLE 6

The total CPU time and the time per iteration of the LR approaches,

$T=24$

Instance		CPU(s) Total a				CPU(s)/iteration				Instance		CPU(s) Total				CPU(s)/Iteration
$(S,N,L,\mathcal{T})$	ρ	LR1	LR2	LR3	LR4	LR1	LR2	LR3	LR4	$(S,N,L,\mathcal{T})$	ρ	LR1	LR2	LR3	LR4	LR1	LR2	LR3	LR4
(2,1,2,1)	0.8	2	3	2	2	0.02	0.02	0.02	0.01	(3,1,2,1)	0.8	4	12	2	4	0.04	0.02	0.02	0.02
	1	1	8	1	2	0.01	0.01	0.01	0.01		1	535	2	2	7	0.03	0.02	0.01	0.01
	2	0	4	1	0	0.00	0.00	0.00	0.00		2	1	1	1	0	0.01	0.00	0.00	0.00
	3	0	1	0	0	0.00	0.00	0.00	0.00		3	0	0	0	1	0.00	0.00	0.00	0.01
	4	0	0	0	0	0.00	0.00	0.00	0.00		4	0	0	0	1	0.00	0.00	0.00	0.01
	5	0	0	0	0	0.00	0.00	0.00	0.00		5	1	1	0	0	0.01	0.00	0.00	0.00
(2,7,4,1)	0.8	3600	123	51	30	0.44	0.26	0.26	0.26	(3,7,4,1)	0.8	3600	1190	112	45	1.13	0.40	0.40	0.40
	1	3600	32	51	24	0.30	0.15	0.15	0.16		1	3600	52	35	28	0.87	0.23	0.23	0.23
	2	15	5	6	4	0.15	0.02	0.02	0.02		2	3600	14	5	5	0.54	0.03	0.03	0.03
	3	12	2	1	3	0.12	0.01	0.01	0.01		3	3600	9	3	3	0.48	0.01	0.01	0.01
	4	10	1	1	1	0.10	0.00	0.01	0.01		4	3600	8	2	1	0.46	0.01	0.01	0.01
	5	10	1	1	0	0.10	0.00	0.00	0.00		5	3600	3	2	2	0.45	0.01	0.01	0.01
(2,14,7,1)	0.8	523	1473	558	699	5.13	2.10	2.11	2.11	(3,14,7,1)	0.8	1618	3174	846	637	15.86	3.17	3.17	3.17
	1	3602	456	156	524	3.72	1.09	1.09	1.10		1	3608	771	316	585	12.98	1.67	1.67	1.70
	2	3602	30	58	28	2.41	0.16	0.16	0.16		2	3609	80	111	68	9.94	0.25	0.25	0.26
	3	3601	11	6	10	1.79	0.06	0.06	0.06		3	3605	117	48	14	8.90	0.10	0.10	0.11
	4	3600	26	27	6	1.66	0.03	0.03	0.03		4	3607	74	24	5	8.67	0.05	0.05	0.05
	5	3601	22	10	1	1.60	0.02	0.02	0.01		5	3605	77	25	4	8.40	0.04	0.03	0.04
(2,1,2,3)	0.8	4	5	5	5	0.04	0.01	0.02	0.02	(3,1,2,3)	0.8	9	18	3	4	0.09	0.03	0.03	0.02
	1	595	4	5	3	0.03	0.01	0.01	0.01		1	3600	5	9	3	0.07	0.01	0.01	0.01
	2	2	1	0	0	0.02	0.00	0.00	0.00		2	4	1	1	0	0.04	0.00	0.01	0.00
	3	1	1	0	1	0.01	0.00	0.00	0.00		3	4	1	0	1	0.04	0.00	0.00	0.00
	4	1	1	0	0	0.01	0.01	0.00	0.00		4	3	3	0	0	0.03	0.00	0.00	0.00
	5	1	0	0	0	0.01	0.00	0.00	0.00		5	3	1	1	0	0.03	0.00	0.00	0.00
(2,7,4,3)	0.8	3600	39	127	31	1.03	0.20	0.20	0.21	(3,7,4,3)	0.8	3601	1212	216	503	3.70	0.30	0.30	0.30
	1	3600	29	26	13	0.90	0.11	0.11	0.10		1	3604	42	35	20	4.49	0.17	0.17	0.16
	2	73	15	4	6	0.72	0.02	0.02	0.02		2	3600	11	5	7	3.06	0.04	0.03	0.04
	3	3600	3	2	2	0.56	0.01	0.01	0.01		3	3603	15	2	3	2.83	0.02	0.01	0.02
	4	82	1	8	2	0.80	0.01	0.01	0.01		4	3601	11	3	3	2.71	0.02	0.01	0.01
	5	58	3	1	2	0.57	0.01	0.00	0.01		5	289	11	5	1	2.83	0.01	0.01	0.01
(2,14,7,3)	0.8	3604	1776	236	444	16.53	1.30	1.32	1.31	(3,14,7,3)	0.8	3624	3194	822	725	62.48	1.95	2.01	2.00
	1	3611	230	107	161	12.37	0.71	0.72	0.72		1	3618	1698	214	308	68.26	1.10	1.12	1.14
	2	3608	41	96	17	10.93	0.13	0.14	0.14		2	3639	91	97	26	56.86	0.22	0.22	0.22
	3	3603	28	35	8	10.26	0.06	0.06	0.06		3	3632	109	45	14	64.86	0.11	0.11	0.11
	4	3606	12	12	8	9.99	0.04	0.04	0.04		4	3610	130	91	14	52.32	0.08	0.08	0.07
	5	3609	50	21	2	9.81	0.03	0.03	0.02		5	3613	126	33	5	63.39	0.06	0.06	0.05

^a

Where the total CPU time is more than 3600s, the extra time is used to complete the last iteration before the algorithm is terminated.

Revenue performance of alternative bid price policies

Table 7 reports the revenue performance under the bid price policies for all instances with

$T=24$

, and the percentage extra revenue under LR1 compared with other policies. A positive (negative) value indicates stronger (weaker) performance of LR1 than the other policy. We note the following key findings. First, LR1 performs strongly and consistently across the board, outperforming the three network‐based heuristics in almost all the instances, except for PNLP in few smaller problems where the capacity is highly constrained. Second, among the network policies PNLP yields the strongest performance, followed at some distance by RLP and then DLP. Third, among the LR‐based policies, LR1 is clearly the strongest, but could still be outperformed by other variants occasionally. There is no clear ranking of the revenue performance of LR2 and LR3. The latter is stronger for instances with the smallest N and L, but the former is stronger otherwise. Nevertheless, both outperform the network policies in most instances. LR4 is clearly the weakest and its performance is problem dependent. When ρ is large, LR4 is strong in few cases but poor in general, and sometimes it is the worst policy even relative to the network‐based heuristics.

TABLE 7

The revenue of alternative bid price policies and percentage extra revenue under LR1,

$T=24$

Instance									LR1 vs	LR1 vs	LR1 vs	LR1 vs	LR1 vs	LR1 vs
$(S,N,L,\mathcal{T})$	ρ	DLP	PNLP	RLP	LR1	LR2	LR3	LR4	DLP	PNLP	RLP	LR2	LR3	LR4
(2,1,2,1)	0.8	17427	17200	17392	17762	17602	17768	17608	1.92	3.27	2.13	0.91	−0.03	0.87
	1	15304	15153	15096	15697	15399	15624	15536	2.57	3.59	3.98	1.94	0.47	1.04
	2	9058	9235	8932	9597	9265	9539	9054	5.95	3.92	7.45	3.58	0.61	6.00
	3	6113	6025	5728	6408	6209	6124	6305	4.83	6.36	11.87	3.21	4.64	1.63
	4	4793	4916	4460	4961	4623	4765	3993	3.51	0.92	11.23	7.31	4.11	24.24
	5	4149	4237	3831	4188	4228	4063	3329	0.94	−1.16	9.32	−0.95	3.08	25.80
(2,7,4,1)	0.8	18038	18315	18051	18663	18500	18585	18609	3.46	1.90	3.39	0.88	0.42	0.29
	1	16207	16543	16050	16960	16841	16786	16763	4.65	2.52	5.67	0.71	1.04	1.18
	2	10269	10268	10306	10834	10743	10739	10285	5.50	5.51	5.12	0.85	0.88	5.34
	3	8146	8048	8033	8377	8325	8220	8510	2.84	4.09	4.28	0.62	1.91	−1.56
	4	6325	6351	6058	6536	6454	6405	6438	3.34	2.91	7.89	1.27	2.05	1.52
	5	5691	5942	5534	5955	5948	5757	5872	4.64	0.22	7.61	0.12	3.44	1.41
(2,14,7,1)	0.8	20698	21094	20739	21344	21281	21229	21097	3.12	1.19	2.92	0.30	0.54	1.17
	1	18785	19401	18892	19718	19657	19577	19420	4.97	1.63	4.37	0.31	0.72	1.53
	2	12743	13335	12347	13915	13674	13673	13605	9.20	4.35	12.70	1.76	1.77	2.28
	3	9888	10314	9886	11013	10762	10557	10593	11.38	6.78	11.40	2.33	4.32	3.96
	4	8118	8313	8145	8914	8684	8432	8531	9.81	7.23	9.44	2.65	5.72	4.49
	5	7212	7164	7145	7717	7412	7320	7445	7.00	7.72	8.01	4.11	5.42	3.65
(2,1,2,3)	0.8	13643	13472	13439	13834	13741	13850	13797	1.40	2.69	2.94	0.68	−0.12	0.27
	1	11795	11697	11673	12073	11865	11998	11968	2.36	3.21	3.43	1.75	0.63	0.88
	2	6723	6907	6746	7191	6905	7144	6938	6.96	4.11	6.60	4.14	0.66	3.65
	3	5128	5094	5085	5312	5201	5240	5283	3.59	4.28	4.46	2.13	1.37	0.55
	4	3892	4006	3722	3984	3938	3927	4007	2.32	−0.55	7.04	1.17	1.45	−0.57
	5	3170	3234	2858	3206	3097	3111	2576	1.14	−0.87	12.18	3.52	3.05	24.46
(2,7,4,3)	0.8	14172	14431	14239	14724	14605	14653	14678	3.90	2.03	3.41	0.81	0.48	0.31
	1	12508	12780	12453	13099	13003	12969	12955	4.72	2.50	5.19	0.74	1.00	1.11
	2	8074	8198	8168	8586	8499	8471	8136	6.34	4.73	5.12	1.02	1.36	5.53
	3	6372	6292	6343	6663	6556	6467	6698	4.57	5.90	5.04	1.63	3.03	−0.52
	4	5243	5357	5155	5464	5422	5332	5521	4.22	2.00	5.99	0.77	2.48	−1.03
	5	3928	4171	3900	4190	4154	4030	4229	6.67	0.46	7.44	0.87	3.97	−0.92
(2,14,7,3)	0.8	16108	16468	16179	16680	16630	16582	16471	3.55	1.29	3.10	0.30	0.59	1.27
	1	14762	15349	14906	15563	15528	15471	15373	5.43	1.39	4.41	0.23	0.59	1.24
	2	10066	10529	9795	10966	10794	10805	10762	8.94	4.15	11.96	1.59	1.49	1.90
	3	7588	7926	7623	8440	8293	8165	8138	11.23	6.48	10.72	1.77	3.37	3.71
	4	6375	6577	6470	7006	6849	6716	6763	9.90	6.52	8.28	2.29	4.32	3.59
	5	5444	5497	5414	5832	5602	5548	5606	7.13	6.09	7.72	4.11	5.12	4.03
(3,1,2,1)	0.8	16824	17045	16750	17231	17035	17396	16941	2.42	1.09	2.87	1.15	−0.95	1.71
	1	14577	15001	14641	15189	14849	15321	14914	4.20	1.25	3.74	2.29	−0.86	1.84
	2	8659	8981	8769	9275	9179	9420	8779	7.11	3.27	5.77	1.05	−1.54	5.65
	3	5831	6006	5604	6108	6060	6148	5612	4.75	1.70	8.99	0.79	−0.65	8.84
	4	4512	4805	4260	4751	4387	4515	4740	5.30	−1.12	11.53	8.30	5.23	0.23
	5	3840	4043	3512	4005	3759	3948	3378	4.30	−0.94	14.04	6.54	1.44	18.56
(3,7,4,1)	0.8	18729	19284	18946	19508	19357	19482	19379	4.16	1.16	2.97	0.78	0.13	0.67
	1	16574	17311	16747	17470	17375	17496	17401	5.41	0.92	4.32	0.55	−0.15	0.40
	2	10152	10718	10172	10897	10841	10856	10687	7.34	1.67	7.13	0.52	0.38	1.97
	3	7575	7948	7572	8120	7944	7937	8135	7.19	2.16	7.24	2.22	2.31	−0.18
	4	5748	6164	5827	6294	6075	6037	6236	9.50	2.11	8.01	3.60	4.26	0.93
	5	5206	5593	5262	5714	5475	5371	5489	9.76	2.16	8.59	4.37	6.39	4.10
(3,14,7,1)	0.8	21840	22473	22044	22635	22596	22530	22473	3.64	0.72	2.68	0.17	0.47	0.72
	1	19579	20454	19776	20688	20626	20606	20456	5.66	1.14	4.61	0.30	0.40	1.13
	2	13019	13988	13067	14336	14225	14216	14034	10.12	2.49	9.71	0.78	0.84	2.15
	3	9731	10589	9793	10957	10839	10719	10714	12.60	3.48	11.89	1.09	2.22	2.27
	4	7657	8332	7756	8657	8419	8281	7989	13.06	3.90	11.62	2.83	4.54	8.36
	5	6663	7154	6640	7471	7107	7049	6955	12.13	4.43	12.52	5.12	5.99	7.42
(3,1,2,3)	0.8	12926	13157	12967	13292	13184	13426	13049	2.83	1.03	2.51	0.82	−1.00	1.86
	1	11229	11441	11195	11624	11407	11681	11437	3.52	1.60	3.83	1.90	−0.49	1.64
	2	6462	6769	6624	6952	6886	7070	6812	7.58	2.70	4.95	0.96	−1.67	2.06
	3	4833	5070	4898	5132	5039	5180	5150	6.19	1.22	4.78	1.85	−0.93	−0.35
	4	3562	3713	3464	3746	3696	3748	3333	5.17	0.89	8.14	1.35	−0.05	12.39
	5	2948	3090	2911	3128	2937	3125	3120	6.11	1.23	7.45	6.50	0.10	0.26
(3,7,4,3)	0.8	14671	15138	14861	15296	15188	15275	15220	4.26	1.04	2.93	0.71	0.14	0.50
	1	12662	13254	12852	13373	13307	13398	13287	5.62	0.90	4.05	0.50	−0.19	0.65
	2	7847	8314	7942	8478	8443	8427	8320	8.04	1.97	6.75	0.41	0.61	1.90
	3	5920	6253	5967	6410	6276	6242	6402	8.28	2.51	7.42	2.14	2.69	0.12
	4	4813	5153	4893	5259	5065	5027	5237	9.27	2.06	7.48	3.83	4.62	0.42
	5	3482	3786	3592	3770	3738	3665	3762	8.27	−0.42	4.96	0.86	2.86	0.21
(3,14,7,3)	0.8	16881	17312	17032	17547	17498	17409	17312	3.95	1.36	3.02	0.28	0.79	1.36
	1	15166	15919	15492	16076	16040	16015	15922	6.00	0.99	3.77	0.22	0.38	0.97
	2	10118	10911	10174	11133	11100	11082	10956	10.03	2.03	9.43	0.30	0.46	1.62
	3	7454	8153	7569	8354	8330	8238	8261	12.07	2.47	10.37	0.29	1.41	1.13
	4	6014	6560	6056	6711	6648	6525	6658	11.59	2.30	10.82	0.95	2.85	0.80
	5	4929	5390	4987	5502	5307	5269	5167	10.63	2.08	10.33	3.67	4.42	6.48

The results for

$T=12$

are presented in Table EC.4 of the Supporting Information. Similar patterns are observed among the LR policies, even though the difference between them slightly reduces. The advantage of the LR policies is less distinct over the network‐based policies. This is not surprising as the network‐based policies only consider the overall demand on each rental day rather than the arrival process, and thus their performance tends to improve with less granular arrival processes.

Importantly, the results in both tables indicate that the superiority of LR1 over the network heuristics increases first in ρ, and then tends to decrease after a certain point. When ρ is small, there are many cars in the network and much demand can be accepted regardless of the booking control policy. With the fleet decreasing, the outcomes of good and bad decisions become more distinct and thus the difference between them increases. When the fleet size is too small, few bookings can be accepted, resulting in less revenue difference between the policies.

In summary, LR1 yields the strongest revenue performance but suffers longer computational time. LR2 has the right balance between the revenue performance and the scalability, especially for large problems. LR3 is a strong contender for smaller problems while LR4 is not a reliable policy.

CASE STUDY

To examine the potential performance of the proposed LR approaches over the alternative network heuristics in real‐world applications, we next provide a case study based on a sample of booking data in a car rental network of a major service operator in the United Kingdom. For simplicity, we restrict our focus to the regional network around London. The data used in this case include the booking requests received by the car rental operator within the 5‐month period from May to September in 2011. We use the empirical data in the first 3 months to calibrate the arrival processes as a Poisson regression model and implement the proposed policies with the estimated arrival probabilities. The problem parameters are

$S=3,N=14,L=7,\mathcal{T}=7,T=77$

, for the network with three stations, up to 14 days of advance booking, maximum 7 days of LoR, a weekly demand cycle of 7 days, and 77 time slots within each day. Thus, there are 5,093,550 Lagrangian multipliers for LR1, 66 for LR2, 22 for LR3, and 3 for LR4. The full details of the empirical case and parameter calibration can be found in Section EC.6 of the Supporting Information, which includes an in‐depth analysis on the value of one‐way rentals and the effect of the initial fleet distribution. In what follows, we focus on comparing the performance of the proposed LR approaches and the alternative network heuristics.

We examine five different demand‐to‐supply ratios such that

$\rho \in \{0.6,0.8,1.0,1.2,1.4\}$

, and assume that the fleet is evenly distributed among the stations and there are no accepted bookings at the beginning of the tested period. Table 8 reports the total revenue over the 5‐month period under each policy and the percentage extra revenue due to LR1 over each alternative. Table 9 shows the results of two important performance indicators for car rental businesses: revenue per car per day and fleet utilization. Note that the network‐based heuristics are still reoptimized every 9 days and the Lagrangian dual problems are solved just once. As shown in both tables, LR1, closely followed by LR2, can outperform the network‐based heuristics except in the lowest ρ scenario in which RLP yields a respectful performance. Meanwhile, LR3 and LR4 deliver mixed results. RLP is the strongest among the network policies, but is closely followed by PNLP and DLP. Similar to the results in the numerical study, the superiority of LR1 over three network‐based heuristics first increases with the demand‐to‐supply ratio and then decreases. Furthermore, LR1 and LR2 clearly achieve the highest fleet utilization and revenue per car per day for the scenarios

$\rho =0.8,1.0,1.2$

.

TABLE 8

Total revenue

								LR1 vs	LR1 vs	LR1 vs	LR1 vs	LR1 vs	LR1 vs
ρ	DLP	PNLP	RLP	LR1	LR2	LR3	LR4	DLP	PNLP	RLP	LR2	LR3	LR4
0.6	554394	538438	565129	558171	545756	545431	544089	0.68	3.66	−1.23	2.27	2.34	2.59
0.8	520203	499995	520673	532457	529679	522395	499995	2.36	6.49	2.26	0.52	1.93	6.49
1.0	462450	465633	465794	484160	482346	474647	466687	4.69	3.98	3.94	0.38	2.00	3.74
1.2	412939	414647	415678	430596	423719	416220	415697	4.28	3.85	3.59	1.62	3.45	3.58
1.4	374623	374747	375461	385160	378712	373919	373573	2.81	2.78	2.58	1.70	3.01	3.10

TABLE 9

Revenue per car per day and the fleet utilization

		Revenue per car per day							Fleet utilization
ρ	C	DLP	PNLP	RLP	LR1	LR2	LR3	LR4	DLP	PNLP	RLP	LR1	LR2	LR3	LR4
0.6	151	24.08	23.38	24.54	24.24	23.70	23.69	23.63	0.58	0.56	0.59	0.58	0.57	0.57	0.57
0.8	113	30.12	28.95	30.15	30.83	30.67	30.25	28.95	0.72	0.69	0.72	0.74	0.74	0.73	0.69
1.0	90	33.47	33.70	33.71	35.04	34.91	34.35	33.78	0.79	0.80	0.78	0.84	0.84	0.82	0.81
1.2	75	35.87	36.01	36.10	37.40	36.80	36.15	36.11	0.81	0.84	0.81	0.88	0.87	0.86	0.86
1.4	65	37.96	37.97	38.05	39.03	38.38	37.89	37.85	0.83	0.87	0.83	0.90	0.90	0.89	0.90

Figure 3 shows the cumulative revenue (for

$\rho =1$

) over the 5‐month period under each policy. Both LR1 and LR2 outperform the network policies in both the calibration period and the hold‐out period. LR3 is the next, but with a clear gap. There is no significant difference between LR4 and the network heuristics.

FIGURE 3

Cumulative revenue for

$\rho =1$

To assess the impact of more frequent reoptimization of the network bid price policies, we repeat the analysis by resolving DLP/PNLP/RLP twice as frequently (every 5 days). Similarly, we re‐solve the Lagrangian dual problems for the four LR approaches five times. In other words, they are solved at time T on day 0, 35, 70, 105, and 140 for the state then occupied. Figure 4 presents the percentage revenue changes (the actual revenue results are shown in Table EC.9 in the Supporting Information), showing that more frequent optimization of the network models does not necessarily lead to better performance. Indeed, in some cases based on the network heuristics, revenue actually reduces. The benefit of more frequent reoptimization is marginal for LR1, but is more noticeable for LR2, LR3, and LR4, which suggests that more frequent reoptimization can reduce, but not obliterate, the performance gap between these network heuristics and LR1.

FIGURE 4

Percentage revenue changes with more frequent reoptimization

To examine the robustness of the 1‐h time limit termination criterion, we have repeated the case study with 10‐h time limit. Our results indicate that there is almost no improvement when ρ is small, and when ρ is relatively large the extra revenue due to the longer computing time is always less than 0.44%. These observations suggest that it suffices to control the computation time within 1 h per instance.

CONCLUSIONS

Because of its complexity, RM in car rental is intrinsically challenging. A typical car rental network simultaneously possesses the characteristics of passenger airlines, such as demand sparsity, limited capacity (resource scarcity), and finite advance booking horizons (perishability), and the characteristics of hotel services, such as variations of LoR. The mobility of inventories due to one‐way rentals in the network differentiates car rental from hotel services. A basic booking request needs to specify when and where to pick‐up and return the car, which implies that the product in car rental should be characterized by the combination of origin, destination, pick‐up time, and LoR. Such a product can be seen as a bundle of resources; that is, the available cars each day in a particular station. These operational characteristics are further verified in the case study with a sample of real booking data from a regional car rental network in the United Kingdom.

In this paper, we formulate the RM problem of a car rental network as a cyclic stochastic DP with a rolling booking and rental time horizon, capturing the key characteristics of car rental operations. The underlying Markov decision process has a state space with the dimensionality equal to the number of stations in the network multiplied by the length of the regular booking and rental time window. To tackle the curse of dimensionality, we introduce an LR approach (LR1), which has been successfully applied to airline RM problems (see, e.g., Jiang, 2006; Topaloglu, 2009), to decomposing the car rental network problem into multiple single‐resource problems across stations and over time from the current day into the future. The key idea is to break the intertemporal correlation and the spatial correlation of the demands for capacities in different locations and days by decoupling the booking decision for a product over the resources that it uses via a set of product‐ and time‐dependent Lagrangian multipliers. The Lagrangian multipliers can be viewed as compensations for the round/outbound trips and charges for inbound trips related to each resource. We can then decompose the problem into multiple single‐resource subproblems. We characterize the structural properties of the decomposed problems and show that the value function under LR provides an upper bound for the optimal value function. We show that the dual problem is a convex program and propose a subgradient‐based optimization algorithm to solve it. The optimal dual function provides an approximate value function, which allows us to develop a bid price policy. Such an approach, though analytically appealing, requires computing a very large number of Lagrangian multipliers when the problem size becomes large, which restricts its scalability.

To enhance the scalability of the LR‐based bid price policies, we introduce three simpler LR approaches (LR2, LR3, and LR4) with the significantly reduced numbers of required Lagrangian multipliers. In the numerical study, we compare the performance of the proposed bid price policies and several commonly used heuristics such as DLP, PNLP, and RLP across various parameter settings. Our results show that LR1 outperforms those heuristics in most instances considered. LR2, though slightly worse than LR1, is much faster and therefore is more scalable, making it a great complement to LR1. LR3 is a strong contender for small instances but LR4 performs weakly in general. In the case study, we use the empirical data to calibrate the arrival processes as a Poisson regression model and implement the proposed policies with the estimated arrival probabilities. Both LR1 and LR2 deliver strong and robust performance in these real‐world settings.

We find that the LR approach is an insightful method that allows us to leverage the structural properties of the single resource RM models to construct the control policy for the network. Our development further advances the LR method in the context of car rental network RM. Such an approach can be potentially extended to other mobility services such as car sharing and ride hailing.

Nevertheless, our model has some limitations that raise suggestions for future research. First, our model does not address the uncertainty of LoRs. Like hotel RM, customers may sometimes extend or shorten the LoRs. Addressing random LoRs requires tracing each on‐rent car's rental time and forecasting its return time, which leads to a more sophisticated system. Second, our model only considers a single car group, while in reality consumers may choose different car models, which suggests that modeling consumer choice behavior toward the availability control could be an interesting generalization. Last but not the least, the emergence of on‐demand car sharing business models such as zipcar and car2go that allow customers to rent cars by the hour or the minute provides another interesting research topic for car rental network RM.

Footnotes

ACKNOWLEDGMENTS

The authors are grateful to the department editor, the senior editor, and the anonymous referees for their constructive comments and suggestions. This work is partially supported by the National Natural Science Foundation of China (No. 71973107).

ORCID iD

Dong Li

Zhan Pang

Lixian Qian

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.77 MB