Scenario-based CVaR Approach to Strategic Decision Support in One-way Station-based Carsharing Systems

By Kai Zhang, Yuichi Takano, Yuzhu Wang, and Akiko Yoshise

The number of private cars continues to increase in many countries, leading to higher rates of traffic congestion. In response, carsharing has garnered widespread interest in recent years as a potential solution to reduce overall dependency on private cars. Existing carsharing systems mainly fall into two categories: one-way and two-way (i.e., round-trip) types [2]. In one-way systems, users can pick up and return cars at different sites, while users in two-way systems must return rented cars to the site at which they were initially claimed. One-way systems are generally more convenient for users because one-way drives occupy a large percentage of total trips [1, 5]. Furthermore, station-based and free-floating systems differ due to their parking spot restrictions [2]; the former forces people to park vehicles at stations with limited parking spaces, whereas the latter allows users to park cars anywhere within an operation area. One-way station-based carsharing has recently soared in popularity worldwide. However, operators still face significant challenges in the design and management of their systems.

We focus on the strategic design of one-way station-based carsharing systems from the vantage point of the system operator. Previous research mainly addressed strategic problems that are based on the traditional risk-neutral, two-stage stochastic programming model by considering the expectation value as the preference criterion [2-4]. However, the resulting decisions may be poor under certain realizations of random data. For non-repetitive decision-making problems—such as location planning and network design—a risk-averse approach would provide more robust solutions [9]. In this study we thus analyze the downside risk, which refers to the financial risk of the actual return being lower than the expected return. Our objective is to maximize the return and minimize the risk. Therefore, we propose a two-stage, risk-averse stochastic mixed-integer nonlinear programming model—in which the conditional value-at-risk (CVaR) is specified as the risk measure—to optimize strategic decisions that involve station locations, station capacities, and fleet sizes for one-way station-based carsharing systems.

CVaR was first proposed by R. Tyrrell Rockafellar and Stan Uryasev as a downside risk measure to quantify tail losses [11]. Unlike the traditional value-at-risk (VaR) risk measure, CVaR has more attractive mathematical properties (e.g., subadditivity and convexity) [10, 12]. As such, the financial industry has gradually begun to adopt CVaR in recent years.

Practical applications usually consider the following mean-CVaR model [7] to minimize risk and maximize return (or minimize loss) in the decision-making process:

\[\min_{x, \alpha}\{\lambda \mathbb{E}[\mathcal{L}(\boldsymbol{x,y})]+(1-\lambda)\mathcal{F}_\beta(\boldsymbol{x},\alpha)\}.\tag1\]

Here, \(\lambda \in [0,1]\) is a weight value, \(\mathbb{E}[\cdot]\) is the expectation function, and \(\mathcal{L}(\boldsymbol{x,y})\) is a loss function with respect to decision vector \(\boldsymbol{x} \in \mathbb{R}^n\) and uncertain vector \(\boldsymbol{y} \in \mathbb{R}^m\). \(\mathcal{F}_\beta(\boldsymbol{x}, \alpha)\) is the auxiliary function [9] to calculate CVaR and can be written as

\[\mathcal{F}_{\beta}(\boldsymbol{x}, \alpha)=\alpha + \frac{1}{1-\beta} \int_{\boldsymbol{y}\in\mathbb{R}^m} [\mathcal{L}(\boldsymbol{x},\boldsymbol{y})-\alpha]_+ p(\boldsymbol{y})\textrm{d}\boldsymbol{y} \approx \alpha + \frac{1}{(1-\beta)|S|}\sum_{s\in S}[ \mathcal{L}(\boldsymbol{x},\boldsymbol{y}^s)-\alpha]_+,\tag2\]

where \(\beta\) is the confidence level; \(\alpha \in \mathbb{R}\) is an auxiliary variable; \([x]_+=\max\{x,0\}\), where \(x \in \mathbb{R}\); \(p(\boldsymbol{y})\) is the probability density function associated with \(\boldsymbol{y}\); and \(\boldsymbol{y}^s\) is the realization of \(\boldsymbol{y}\) for \(s\) in the scenario set \(S\).

The loss function in our model depends on operating costs and trip revenue. The capital costs, like station and vehicle costs, are restricted by available budget. The number of parking spaces falls within the maximum capacity at each potential location site, and the movement of vehicles follows the flow conservation. In addition, we ensure that there are enough vehicles and parking spaces for the served trips.

Figure 1. Efficient frontiers of mean return and conditional value-at-risk (CVaR). 1a. \(\beta=90\) percent. 1b. \(\beta=95\) percent. 1c. \(\beta=99\) percent. Figure adapted from [13].

To verify our model, we performed computational experiments based on data from Toyota’s harmonious mobility network (Ha:mo) RIDE in Japan (a one-way station-based system). There are 55 stations with different capacities in the Ha:mo RIDE system. We assumed that these stations’ sites were the potential location sites and regarded the current station capacities as upper limits on the number of parking spaces.

We solved the strategic decision model directly with the Gurobi Optimizer and generated efficient frontiers for the 90, 95, and 99 percent confidence levels by using different weight values (see Figure 1). This figure also displays the optimal results, including the total number of parking spaces, the number of vehicles, and the demand satisfaction rate for different weight values. It is obvious from the efficient frontiers that high risks accompany high returns. The main approach to achieving higher returns appears to involve increasing the number of parking spaces or vehicles, which improves the satisfied demand ratio. By considering different confidence levels, we found that a higher confidence level quantifies more serious risk and reduces the return to a certain degree. Furthermore, providing 86 parking spaces and purchasing 34 vehicles in the carsharing system seems sufficient, as having more parking spaces or vehicles increases risk, not return.

Figure 2 illustrates the optimal location and capacity of stations for different values of \(\lambda\), given \(\beta=95\) percent. The size of each circle represents the number of parking spaces, and each map contains the optimal number of stations, number of parking spaces, and required fleet size in the upper right corner. Stations that are equipped with more parking spaces are mainly located at spots with high demand, such as Toyota factories and railway stations. However, the weight values easily affect these hot spots; that is, the number of parking spaces will increase when the model pays more attention to the return. In comparison, the solutions seem more robust for some small stations. There are 13 common small stations, marked with red circles in Figure 2, at which location and capacity are the same.

Figure 2. Optimal station locations and capacities for \(\beta=95\) percent. 2a. \(\lambda=0\). 2b. \(\lambda=0.5\). 2c. \(\lambda=1\). Figure adapted from [13].

We also developed an evaluation method that is similar to the holdout validation method that machine learning practitioners use to verify the prospective benefits of introducing risk, i.e., whether the strategic decisions from a risk-averse model are better. Interestingly, we obtain the maximal returns for most of the test data when the model considers risk. Strategic decisions that are based on a single criterion are more likely to cause poor performance under demand uncertainty, which indicates the necessity of introducing the risk term. By weighting the return against risk, the carsharing system operator may earn higher returns in the future.

Finally, we presented two solution methods to efficiently handle the problem: the branch-and-cut algorithm and scenario decomposition algorithm. The former algorithm mainly focuses on the nonlinear CVaR function, while the latter pays attention to the stochastic problem’s special block-angular structure. We compared our approaches with the Benders decomposition algorithm developed by Mengshi Lu, Zhihao Chen, and Siqian Shen [8] and found that their algorithm performed unsatisfactorily on our model. In contrast, the branch-and-cut algorithm and scenario decomposition method effectively solve small- and medium-scale problems. Furthermore, the scenario decomposition is able to cope with large-scale problems that cannot be solved with the direct usage of a solver or the branch-and-cut algorithm.

References
[1] Barth, M., & Shaheen, S.A. (2002). Shared-use vehicle systems: Framework for classifying carsharing, station cars, and combined approaches. Transp. Res. Rec.: J. Transp. Res. Board, 1791(1), 105-112.
[2] Boyacı, B., Zografos, K.G., & Geroliminis, N. (2015). An optimization framework for the development of efficient one-way car-sharing systems. Eur. J. Oper. Res., 240, 718-733.
[3] Brandstätter, G., Kahr, M., & Leitner, M. (2017). Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand. Transp. Res. Part B: Methodol., 104, 17-35.
[4] Çalık, H., & Fortz, B. (2019). A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty. Transp. Res. Part B: Methodol., 125, 121-150.
[5] De Almeida Correia, G.H., Jorge, D.R., & Antunes, D.M. (2014). The added value of accounting for users’ flexibility and information on the potential of a station-based one-way car-sharing system: An application in Lisbon, Portugal. J. Intell. Transp. Syst.: Technol. Planning Oper., 18(3), 299-308.
[6] Krokhmal, P., Uryasev, S., & Palmquist, J. (2001). Portfolio optimization with conditional value-at-risk objective and constraints. J. Risk, 4(2), 43-68.
[7] Künzi-Bay, A., & Mayer, J. (2006). Computational aspects of minimizing conditional value-at-risk. Comput. Manag. Sci., 3, 3-27.
[8] Lu, M., Chen, Z., & Shen, S. (2018). Optimizing the profitability and quality of service in carshare systems under demand uncertainty. Manuf. Serv. Oper. Manag., 20(2), 162-180.
[9] Noyan, N. (2012). Risk-averse two-stage stochastic programming with an application to disaster management. Comput. Oper. Res., 39(3), 541-559.
[10] Pflug, G.C. (2000). Some remarks on the value-at-risk and the conditional value-at-risk. In S.P. Uryasev (Ed.), Probabilistic constrained optimization (pp. 272-281). Boston, MA: Springer.
[11] Rockafellar, R.T., & Uryasev, S. (2000). Optimization of conditional value-at-risk. J. Risk, 2(3), 21-41.
[12] Takano, Y., Nanjo, K., Sukegawa, N., & Mizuno, S. (2014). Cutting plane algorithms for mean-CVaR portfolio optimization with nonconvex transaction costs. Comput. Manag. Sci., 12, 319-340.
[13] Zhang, K., Takano, Y., Wang, Y., & Yoshise, A. (2021). Optimizing the strategic decisions for one-way station-based carsharing systems: A mean-CVaR approach. IEEE Access, 9, 79816-79828.

	Kai Zhang is a Ph.D. candidate in the Graduate School of Systems and Information Engineering at the University of Tsukuba. His research interests include mathematical optimization and its application to transportation systems.
	Yuichi Takano is an associate professor with the Faculty of Engineering, Information and Systems at the University of Tsukuba. His primary research interest is mathematical optimization and its application to financial engineering and machine learning.
	Yuzhu Wang is a Ph.D. candidate in the Graduate School of Systems and Information Engineering at the University of Tsukuba. His research interests focus on conic optimization problems, approximations of the semidefinite cone, and algorithms for the solution of large-scale semidefinite optimization problems.
	Akiko Yoshise is a professor with the Faculty of Engineering, Information and Systems and an executive officer at the University of Tsukuba. Her research interests focus on mathematical optimization, especially conic optimization, and its applications to service science. She received the INFORMS Computing Society Prize in 1992 and the Frederick W. Lanchester Prize in 1993.