# Addressing the Bike Repositioning Problem in Bike Sharing System: A Two-Stage Stochastic Programming Model

Authors: Qiong Tang; Zhuo Fu; Dezhi Zhang; Hao Guo; Minyi Li
Journal: Scientific Programming
 (2020)

---

## Abstract

In this paper, a bike repositioning problem with stochastic demand is studied. The problem is formulated as a two-stage stochastic programming model to optimize the routing and loading/unloading decisions of the repositioning truck at each station and depot under stochastic demands. The goal of the model is to minimize the expected total sum of the transportation costs, the expected penalty costs at all stations, and the holding cost of the depot. A simulated annealing algorithm is developed to solve the model. Numerical experiments are conducted on a set of instances from 20 to 90 stations to demonstrate the effectiveness of the solution algorithm and the accuracy of the proposed two-stage stochastic model.


---

## Body

## 1. Introduction

Bike sharing system (BSS) as a means of sustainable and carbon-free transportation can effectively solve the “the first and last mile” problem of urban public transportation. BSS has gained increasing popularity in recent years due to the fact that it not only reduces urban pollution emissions and traffic congestion but also is considered as an effective way to improve the health of users [1]. A BSS consists of a depot and several stations, which scatter in different streets of the city. The success of a BSS depends on the availability of bikes. Due to the rental cycling of the user, there are often unbalanced situations at some stations of the system, i.e., there are either surplus or not enough bikes at these stations. In other words, either when there are surplus bikes in a station, they will be wasted as no users will need them, or in some stations where there are not enough bikes, a user’s demand cannot be met. To ensure the availability of bikes at all stations in the system, the BSS needs to employ redistribution trucks to transfer bikes from stations to stations, to balance the number of bikes according to the demand in each station. This problem is commonly defined as the bike repositioning problem (BRP) in the BSS. The main objective of the BRP is to balance the supply and demand of bikes across stations as a mean to improve user satisfaction, while in the meantime, to reduce the transportation cost of redistribution trucks as much as possible. According to the classification of Berbeglia et al. [2], the bike repositioning problem is essentially a many-to-many pickup and delivery problem, and it is first proven to be an NP-hard problem by Benchimol et al. [3].Typically, existing work assumes the redistribution demand at each station in the BSS is deterministic input parameters [4–21]. That is to say, these models heavily rely on that the loading and unloading quantities of redistribution trucks at each station be given in advance. However, this strong assumption generally could not hold in real-world conditions where the demand in urban public transportation commonly contains uncertainty and randomness [22]. As pointed out by Fricker and Gast [23], the effect of the uncertainty in user demand should not be neglected when studying the performance of a BSS. The authors have also demonstrated that incorporating knowledge of future demands can lead to more accurate and robust decisions in repositioning.The other challenge that might not have received enough attention in BRP is the consideration of the holding cost of the depot. In the BRP, bikes transferred from a bike surplus station to another bike deficient station is required to achieve the balance of supply and demand at all bike stations in the BSS to satisfy the user’s demand. This perfect balance of supply and demand after repositioning operation must first ensure the internal balance in the BSS, i.e., the number of bikes at bike surplus stations should be equal to the number of bikes at bike deficient stations. In the actual operation process, some bikes might be lost or damaged after they are put into use. This happens quite often and will likely lead to the inherent imbalance between supply and demand in the BSS. For the bikes which cannot be balanced among the stations in the BSS, they are either picked up from or delivered back to the depot at the cost of increasing holding cost of the depot. Some BRP models have simply assumed the capacity of the depot is sufficient. As such, some bikes can be picked up from the depot to meet the demand of bike deficient stations, and/or some bikes at bike surplus stations can be brought back to the depot, in order to achieve a perfect balance between supply and demand at all stations in the BSS [4–7]. Unfortunately, these existing works have not yet considered the holding cost of the depot in the BRP model.Stochastic programming is a technology to design mathematical programming models with stochastic demand, which helps decision makers to make more accurate decisions when the effect of the randomness of demand cannot be ignored. Although the optimization results obtained from stochastic programming cannot satisfy all future scenarios, they help to achieve better-than-average performance in dealing with stochastic demand.To address the abovementioned concerns, in this paper, we take into account the stochastic nature of the BRP by capturing and modeling the uncertainty of redistribution demand within the system using stochastic programming. In particular, we propose a two-stage stochastic programming model for the bike repositioning problem with stochastic demand (BRPSD). In the first stage, we determine the routing decision, where “here-and-now” decision must be made before the realization of redistribution demand is known. Then, moving to the second stage, we further determine the loading/unloading decisions at each station and depot, where “wait-and-see” decisions are made taking future uncertainty into account. We incorporate the holding cost into the model such that the overall objective of the BRPSD is to determine the best routes of the repositioning truck and the optimal loading/unloading quantities at each station and depot, such that the expected total sum of the transportation costs, the penalty costs at all stations, and holding cost of the depot are minimized.In this paper, stochastic redistribution demands are modeled by a set of discrete scenarios, and a predefined probability of occurrence is given for each scenario. The main contributions of this paper are summarized as follows:(1)
A general scenario-based two-stage stochastic programming model for the bike repositioning problem with stochastic demands (BRPSD) is introduced. The proposed model takes the inventory holding cost of the depot into account in contexts where the loading and unloading activities are allowed in the depot.(2)
An efficient metaheuristic, namely, simulated annealing algorithm is proposed to solve the defined BRPSD.(3)
The necessity of considering redistribution demand as a stochastic demand in the BRPSD is further discussed with numerical experiments.The remainder of this paper is organized as follows. We review the relevant literature in Section2 and describe the mathematical formulation of the problem in Section 3. In section 4, we present the improved simulated annealing algorithm to solve the model. Then, we present experimental results in Section 5 and conclude this paper with discussions on potential future research in Section 6.


## 2. Literature Review

To the best of our knowledge, Benchimol et al. first formalise and address the BRP in [3]. Since then, various models and solution algorithms for the BRP have been discussed over the last decades.We briefly review studies that are related to this paper, including heuristic and metaheuristic solution methods, for solving the deterministic BRP and models for the BRP with stochastic demands.


### 2.1. Heuristic Solution Algorithm for the Deterministic BRP

According to Pal and Zhang [8], the BRP can be categorized into complete and partial repositioning problems according to the rigor of a repositioning that needs to be performed. In the former problem, the constraint for achieving a perfect balance among stations is considered as a hard constraint, and in the latter problem, it is a soft constraint.In the complete repositioning problem, the optimal inventory of each station must be met after the repositioning operation. An iterated local search algorithm was first applied by Cruz et al. [9] to solve the single-vehicle BRP and then used by Bulhões et al. [10] to solve the multivehicle version of the BRP. Later, Pal and Zhang [8] modeled a static BRP in a free-floating bike sharing system and presented a hybrid nested large neighborhood search with a variable neighborhood descent algorithm to tackle the BRP. Dell’Amico et al. [11] developed a destroy and repair metaheuristic algorithm, which makes use of effective constructive heuristic and several local search procedures together for solving the BRP. Overall, the objective of the complete repositioning problem is mainly to pursue the minimum transportation cost by determining routing decisions. It has been a challenge to apply such methods in real-world systems effectively as there are other equally important criteria that have been neglected in these models.In the partial repositioning problem, the ideal inventory of each station is not necessarily achieved after the repositioning operation. Nonetheless, the goal of these problems is not only to pursue the minimum transportation cost by determining routing decisions but also to minimize user dissatisfaction by determining loading and unloading decisions at each station. In the literature, a 3-step math heuristic for the multivehicle BRP is proposed by Forma et al. [6]. In their approach, stations are firstly clustered by a saving heuristic. Then, the routes through the clusters are constructed. Finally, the routing sequence through the stations in each cluster and the sequence through the clusters are determined. The last two steps are formulated as a mixed integer linear model solving by CPLEX. You [12] proposes a two-phase heuristic for the multivehicle BRP under a minimum service requirement over planning. In his proposed model, each stage represents a decision process. In the first phase, loading and unloading decisions for all stations for each time slot are developed by a linear programming model. Then, in the second phase, routing decisions are developed by an iterative approach through two parameter sensitive mathematical models.In addition to the phased heuristic algorithm, many heuristics and metaheuristic solution methods have been presented to solve the deterministic BRP, to name a few, tabu search [5,13], genetic algorithm [14], chemical reaction optimization algorithm [15,16], artificial bee colony algorithm [17], constraint programming [18,19], variable neighborhood search [20], iterated local search [21], large neighborhood search algorithm [7], etc. Nonetheless, the practical applications of these existing approaches remain difficult and often bring in unexpected results. This is because uncertainty about user demands commonly exists in real-world BRPs; however, it is not yet captured by such deterministic models.


### 2.2. The BRP with Stochastic Demands

To the best of our knowledge, limited literature considers stochastic demands in the BRP. Two-stage stochastic programming with recourse models have been successfully used in solving bike repositioning problems as they allow the modeler to represent routing plans and loading and unloading activities together via first- and second-stage decision variables. Dell’Amico et al. [24] appear to be the pioneer paper that proposed a scenario-based two-stage stochastic model for bike repositioning problem, considering redistribution demands of stations as random variables. The authors provide five exact procedures as well as a heuristic algorithm that combines correlation-based constructive procedures with VND local search approach to solve their BRPSD. The heuristic algorithm only considers transportation costs while evaluating the local search move and only accept a feasible solution where the feasibility of the local search move is checked by an efficient strategy.However, the BRPSD differs from our problem in the following three aspects. First, the objective of this model is to minimize the expected total travel distance of the truck and the penalty costs at all stations, while our problem minimizes the expected total travel cost of the truck, the penalty costs at all stations, and the handling cost at the depot. Second, in our problem, we measure the local search move by using not only transportation costs but also the expected total costs. Third, we develop a method to quickly determine the feasible loading and unloading quantities at all stations and depot under any given route. Therefore, it is not necessary to check the feasibility of the solution in the local search.There are also a few recent works that study a variation of the stochastic BRP where the stochastic demand is defined by origin-destination (OD) pair rather than the redistribution of stations. For instance, Maggioni et al. [25] propose two-stage stochastic programming models to determine the optimal number of bikes to assign to each station and the optimal number of transshipped bikes from one station to another station, respectively. They use AMPL and CPLEX to solve the model. Yan et al. [26] apply the time-space network model to determine the optimal locations of bike stations, bike fleet allocation, and bike routing. Their solution algorithm is based on a threshold-accepting-based heuristic.From the abovementioned review of literature, we can see that the current scholars have proposed a rich heuristic algorithm to solve the deterministic BRP. Nonetheless, to the best of our knowledge, there is no work yet that effectively employs a metaheuristic algorithm to solve the BRP with stochastic demand. The study of this paper fills this theoretical gap.


## 2.1. Heuristic Solution Algorithm for the Deterministic BRP

According to Pal and Zhang [8], the BRP can be categorized into complete and partial repositioning problems according to the rigor of a repositioning that needs to be performed. In the former problem, the constraint for achieving a perfect balance among stations is considered as a hard constraint, and in the latter problem, it is a soft constraint.In the complete repositioning problem, the optimal inventory of each station must be met after the repositioning operation. An iterated local search algorithm was first applied by Cruz et al. [9] to solve the single-vehicle BRP and then used by Bulhões et al. [10] to solve the multivehicle version of the BRP. Later, Pal and Zhang [8] modeled a static BRP in a free-floating bike sharing system and presented a hybrid nested large neighborhood search with a variable neighborhood descent algorithm to tackle the BRP. Dell’Amico et al. [11] developed a destroy and repair metaheuristic algorithm, which makes use of effective constructive heuristic and several local search procedures together for solving the BRP. Overall, the objective of the complete repositioning problem is mainly to pursue the minimum transportation cost by determining routing decisions. It has been a challenge to apply such methods in real-world systems effectively as there are other equally important criteria that have been neglected in these models.In the partial repositioning problem, the ideal inventory of each station is not necessarily achieved after the repositioning operation. Nonetheless, the goal of these problems is not only to pursue the minimum transportation cost by determining routing decisions but also to minimize user dissatisfaction by determining loading and unloading decisions at each station. In the literature, a 3-step math heuristic for the multivehicle BRP is proposed by Forma et al. [6]. In their approach, stations are firstly clustered by a saving heuristic. Then, the routes through the clusters are constructed. Finally, the routing sequence through the stations in each cluster and the sequence through the clusters are determined. The last two steps are formulated as a mixed integer linear model solving by CPLEX. You [12] proposes a two-phase heuristic for the multivehicle BRP under a minimum service requirement over planning. In his proposed model, each stage represents a decision process. In the first phase, loading and unloading decisions for all stations for each time slot are developed by a linear programming model. Then, in the second phase, routing decisions are developed by an iterative approach through two parameter sensitive mathematical models.In addition to the phased heuristic algorithm, many heuristics and metaheuristic solution methods have been presented to solve the deterministic BRP, to name a few, tabu search [5,13], genetic algorithm [14], chemical reaction optimization algorithm [15,16], artificial bee colony algorithm [17], constraint programming [18,19], variable neighborhood search [20], iterated local search [21], large neighborhood search algorithm [7], etc. Nonetheless, the practical applications of these existing approaches remain difficult and often bring in unexpected results. This is because uncertainty about user demands commonly exists in real-world BRPs; however, it is not yet captured by such deterministic models.


## 2.2. The BRP with Stochastic Demands

To the best of our knowledge, limited literature considers stochastic demands in the BRP. Two-stage stochastic programming with recourse models have been successfully used in solving bike repositioning problems as they allow the modeler to represent routing plans and loading and unloading activities together via first- and second-stage decision variables. Dell’Amico et al. [24] appear to be the pioneer paper that proposed a scenario-based two-stage stochastic model for bike repositioning problem, considering redistribution demands of stations as random variables. The authors provide five exact procedures as well as a heuristic algorithm that combines correlation-based constructive procedures with VND local search approach to solve their BRPSD. The heuristic algorithm only considers transportation costs while evaluating the local search move and only accept a feasible solution where the feasibility of the local search move is checked by an efficient strategy.However, the BRPSD differs from our problem in the following three aspects. First, the objective of this model is to minimize the expected total travel distance of the truck and the penalty costs at all stations, while our problem minimizes the expected total travel cost of the truck, the penalty costs at all stations, and the handling cost at the depot. Second, in our problem, we measure the local search move by using not only transportation costs but also the expected total costs. Third, we develop a method to quickly determine the feasible loading and unloading quantities at all stations and depot under any given route. Therefore, it is not necessary to check the feasibility of the solution in the local search.There are also a few recent works that study a variation of the stochastic BRP where the stochastic demand is defined by origin-destination (OD) pair rather than the redistribution of stations. For instance, Maggioni et al. [25] propose two-stage stochastic programming models to determine the optimal number of bikes to assign to each station and the optimal number of transshipped bikes from one station to another station, respectively. They use AMPL and CPLEX to solve the model. Yan et al. [26] apply the time-space network model to determine the optimal locations of bike stations, bike fleet allocation, and bike routing. Their solution algorithm is based on a threshold-accepting-based heuristic.From the abovementioned review of literature, we can see that the current scholars have proposed a rich heuristic algorithm to solve the deterministic BRP. Nonetheless, to the best of our knowledge, there is no work yet that effectively employs a metaheuristic algorithm to solve the BRP with stochastic demand. The study of this paper fills this theoretical gap.


## 3. Mathematical Formulation

The bike sharing system studied in this paper comprises a depot and a set of stations. Each station has a redistribution demand for each scenario, indicating the difference between the current inventory level and the optimal inventory level for each scenario. For a certain scenario, if the redistribution demand at a station is positive, the station is defined as a pickup station; if the redistribution demand at a station is negative, then the station is defined as a delivery station and should be supplied with bikes from pickup stations; if the redistribution demand at a station is equal to 0, then the station is called a balanced station. Balanced stations must also be visited.We consider that only a single truck with a given capacity is available in the BSS. The truck collects bikes from pickup stations and transports them to delivery stations. Some bikes can be picked up from or delivered back to the depot, and each station is allowed to be visited only once. In addition, similar to Liu et al. [16], bikes are assumed to be parked anywhere in the BSS; therefore, the station capacity constraint is removed.The decisions regarding the loading and unloading quantities at all stations and the depot in each scenario are made independently, according to the corresponding demand scenario. However, the routing decisions of the truck have to take into consideration all possible demand scenarios. This means that routing decisions are the same for all scenarios. Because the routing decisions to all scenarios are the same but the loading and unloading decisions vary in each scenario; there may exist a shortage or excess of bikes for each station in each scenario. In this context, the following two-stage bike repositioning problem with stochastic demands (BRPSD) naturally arises. In the first stage, the BRPSD aims to construct a route for the truck that starts from and ends at the depot where each station is visited only once. In the second stage, the BRPSD aims to determine the optimal loading and unloading quantities at all stations and the depot to ensure the feasibility of the solution after the given route in the first stage. The objective of the BRPSD is to minimize the sum of the travel costs for the truck (first-stage objective function) and the expected total penalty costs at all stations and holding costs at the depot (second-stage objective function).


### 3.1. Two-Stage Stochastic Programming Model

Our objective is to determine the sequence of all stations to visit to minimize the transportation cost, as well as the loading/unloading decisions in each scenario to minimize the total expected penalty costs and holding costs. We formulate the problem as a two-stage stochastic programming problem. Given the discrete probability distribution of the scenario occurrences, the formulation for the SPBSD addressed in this study is as follows:(1)min∑i∈N0∑j∈N0,i≠jCttijxij+∑ξ∈Ξpξ∑i∈NCdsiξ++siξ−+Chy0iξ+yi0ξ,    subject to(2)∑j∈Nx0j=∑j∈Nxj0=1,(3)∑j∈N0,j≠ixij=1,i∈N,(4)∑j∈N0,j≠ixij=∑j∈N0,j≠ixji,i∈N,(5)qj≥qi+1−M1−xij,∀i,j∈N0,i≠j,(6)yijξ≤Qxij,∀ξ∈Ξ,i∈N0,j∈N0,i≠j,(7)∑j∈No,j≠iyijξ−∑j∈No,j≠iyjiξ=diξ+siξ−−siξ+,∀ξ∈Ξ,i∈N,(8)qi≥0,∀i∈N0,(9)siξ−,siξ+≥0,∀i∈N,ξ∈Ξ,(10)yijξ≥0,∀i,j∈N0,i≠j,ξ∈Ξ,(11)xij∈0,1,∀i,j∈N0,i≠j.The objective function (1) is defined as the weighted sum of the transportation costs and the expected penalty costs at stations and holding costs at the depot over all scenarios. Constraint (2) states that the truck departs from the depot only once and returns to the depot. Constraint (3) ensures that the truck can visit a station only once. Constraint (4) ensures that if the truck visits a station, it must leave that station. Constraint (5) is the subtour elimination constraint [27]. Constraint (6) ensures that the load on the vehicle cannot be greater than the truck capacity. Constraint (7) requires that the number of bikes loaded onto or unloaded from the truck at a given station equals the difference between the truck load before and after the station visits. Constraint (8) ensures the auxiliary variable is nonnegative. Constraints (9)-(10) ensure that the excess/slack quantities of bikes at station and the number of bikes on the truck are nonnegative integers. Constraint (11) defines xij to be a binary variable.


## 3.1. Two-Stage Stochastic Programming Model

Our objective is to determine the sequence of all stations to visit to minimize the transportation cost, as well as the loading/unloading decisions in each scenario to minimize the total expected penalty costs and holding costs. We formulate the problem as a two-stage stochastic programming problem. Given the discrete probability distribution of the scenario occurrences, the formulation for the SPBSD addressed in this study is as follows:(1)min∑i∈N0∑j∈N0,i≠jCttijxij+∑ξ∈Ξpξ∑i∈NCdsiξ++siξ−+Chy0iξ+yi0ξ,    subject to(2)∑j∈Nx0j=∑j∈Nxj0=1,(3)∑j∈N0,j≠ixij=1,i∈N,(4)∑j∈N0,j≠ixij=∑j∈N0,j≠ixji,i∈N,(5)qj≥qi+1−M1−xij,∀i,j∈N0,i≠j,(6)yijξ≤Qxij,∀ξ∈Ξ,i∈N0,j∈N0,i≠j,(7)∑j∈No,j≠iyijξ−∑j∈No,j≠iyjiξ=diξ+siξ−−siξ+,∀ξ∈Ξ,i∈N,(8)qi≥0,∀i∈N0,(9)siξ−,siξ+≥0,∀i∈N,ξ∈Ξ,(10)yijξ≥0,∀i,j∈N0,i≠j,ξ∈Ξ,(11)xij∈0,1,∀i,j∈N0,i≠j.The objective function (1) is defined as the weighted sum of the transportation costs and the expected penalty costs at stations and holding costs at the depot over all scenarios. Constraint (2) states that the truck departs from the depot only once and returns to the depot. Constraint (3) ensures that the truck can visit a station only once. Constraint (4) ensures that if the truck visits a station, it must leave that station. Constraint (5) is the subtour elimination constraint [27]. Constraint (6) ensures that the load on the vehicle cannot be greater than the truck capacity. Constraint (7) requires that the number of bikes loaded onto or unloaded from the truck at a given station equals the difference between the truck load before and after the station visits. Constraint (8) ensures the auxiliary variable is nonnegative. Constraints (9)-(10) ensure that the excess/slack quantities of bikes at station and the number of bikes on the truck are nonnegative integers. Constraint (11) defines xij to be a binary variable.


## 4. Solution Algorithm

When the number of scenarios equals 1, the studied BRPSD reduces to the classical deterministic bike repositioning problems, an NP-hard combinatorial optimization problem. We employ simulated annealing (SA) to solve the studied BRPSD. SA is a metaheuristic algorithm based on local search, which can avoid falling into local optimization by accepting poor solutions with less probability in the process of iteration. It has been successfully applied to a variety of deterministic combinatorial problems [28,29] and stochastic combinatorial problems [30,31].Our proposed algorithm, called SABRPSD, consists of two phases: constructing the initial solution and improving the initial solution by neighborhood search mechanism. The structure of this section is organized as follows. In Section 4.1, we propose the heuristic method to generate an initial solution. During initialization, two main decisions must be made: the routing decision (in Section 4.1.1) and the loading and unloading decision (i.e., inventory decision) (in Section 4.1.2). Then, in Section 4.2, we describe in detail of the local search operators used in this SABRPSD, namely, Swap, Relocate, and 2-opt. After that the main algorithm flow based on the SABRPSD framework is presented in Section 4.3.


### 4.1. Construct Initial Solution

Since the BRPSD is a two-stage decision-making process, the decision-making in this paper is divided into two stages: routing decisions are determined in the first stage, and the loading and unloading decisions are determined in the second stage. The process of constructing the initial solution is as follows, which is roughly divided into two main phases.


#### 4.1.1. Construct the Initial Route for all Scenarios

Since the route in all scenarios is the same, the greedy heuristic algorithm is used to quickly construct the initial route by ignoring the stochastic redistribution demand. In this work, the nearest principle is used to construct the initial route by inserting stations one by one.


#### 4.1.2. Determine Loading and Unloading Decision for Each Scenario

For a given scenarioξ and the corresponding redistribution demand diξ at station i in the scenario, the Second-Stage-Opt procedure uses a simple principle to quickly generate the initial feasible loading and unloading decision and then uses a reoptimize heuristic operator to improve the initial loading and unloading decision. The details of the Second-Stage-Opt procedure are given as follows.Step 1: determine the initial loading and unloading quantities of all stations and the depot. The loading and unloading quantities at each station are defined as the corresponding redistribution demand. Because the demand of the depot is 0, the loading and unloading quantities are also defined as 0. As a result, the initial solution of the BRPSD is generated, including two-stage decisions, namely, the routing decision and the loading and unloading decision. It is obvious that the initial solution is often not feasible.Step 2: adjust the loading and unloading quantities of some stations to achieve a feasible initial solution. If the number of bikes on the truck when it travels directly from stationi to station j in scenarioξyijξ>Qoryijξ<0, then the initial solution is not feasible. In this case, the loading and unloading quantity of station i should be adjusted. Setγ=yijξ−Q,ifyijξ>Qorγ=yijξ, ifyijξ<0, then the loading and unloading quantity of station i is adjusted to subtract γfrom the original quantity.Step 3 (reoptimize): the basic idea of the reoptimize operator is to optimize the solution by a heuristic method that adjusts the loading and unloading quantities between stations and the depot [5,7]. In this paper, some bikes can be collected from the depot to meet the delivery demands of some stations, and also some bikes collected from some stations can be delivered to the depot at the end of the repositioning. In this procedure, there are two cases. In the first case, the truck picks up extra bikes when it starts from the depot and drops them off at some stations. In the second case, the truck picks up more bikes from some stations and drops them off when it ends at the depot.


### 4.2. Neighborhood Structure

In this paper, the local search operator aims at routing decisions. Three kinds of classical operators Swap move, Relocate move, and 2-opt move are used. These operators are also often used in other BRP problems. Each new neighborhood solution is generated by these three moves with equal probability. Note that, after a local search operator is executed, the new solution needs to be improved bySecond-Stage-Opt procedure to obtain the second-stage decision.Swap-N1: randomly select two stations from the route and then exchange themRelocate-N2: randomly select one station, delete it from the current route, and then insert it into another position2-Opt-N3: randomly select two stations, exchange the positions of the two stations, and change the orientation of the route between the two stations


### 4.3. The Proposed SABRPSD

Algorithm1 provides the pseudocodes of the SABRPSD. Parameter T0 denotes the initial temperature; TE is the final temperature; α is the coefficient used to control the cooling; Iiter indicates the number of generated new solutions under a certain temperature; and Maxiter is the max number of the accepted new solutions under a certain temperature. In this section, we use S0 and Sbest to denote the initial solution and the best solution obtained so far, respectively. The best objective value F(Sbest) is set to be the objective function value of the best solution Sbest.Algorithm 1: SABRPSD.
Obtain the initial solutionS0.Set the parameter for the simulated annealing,T0, TE, α, Iiter, MaxiterSetSbest ⟵ S0; Scurrent ⟵ S0; T ⟵ T0.WhileT ≥ TEdom ⟵ 0; n ⟵ 0;Whilem ≤ Iiter ＆ n ≤ MaxiterdoS ⟵ Local search (Scurrent, Nk);Snew ⟵ Second-Stage-Opt (S);Δ ⟵F(Snew) − F(Scurrent);If Δ ≤ 0 thenScurrent ⟵ Snew, n ⟵ n + 1;IfF(Scurrent) ≤ F(Sbest) thenSbest ⟵ Scurrent;endelseIfe−Δ/T≥randomthenScurrent ⟵ Snew, n ⟵ n + 1;endendm ⟵ m + 1;endT ⟵ α ⃞ T;endReturn: SbestAs shown in Algorithm1, in the inner loop of the SABRPSD algorithm, a random new neighborhood solution Snew is initially generated by Local search procedure to improve the first-stage decision and then followed by Second-Stage-Opt procedure to generate the second-stage decision. The stopping criteria for the inner loop are either it has generated Iiter new solutions or accepted Maxiter new solution under the current temperature T. When the current temperature T decreases to TE, the SABRPSD algorithm terminates.


## 4.1. Construct Initial Solution

Since the BRPSD is a two-stage decision-making process, the decision-making in this paper is divided into two stages: routing decisions are determined in the first stage, and the loading and unloading decisions are determined in the second stage. The process of constructing the initial solution is as follows, which is roughly divided into two main phases.


### 4.1.1. Construct the Initial Route for all Scenarios

Since the route in all scenarios is the same, the greedy heuristic algorithm is used to quickly construct the initial route by ignoring the stochastic redistribution demand. In this work, the nearest principle is used to construct the initial route by inserting stations one by one.


### 4.1.2. Determine Loading and Unloading Decision for Each Scenario

For a given scenarioξ and the corresponding redistribution demand diξ at station i in the scenario, the Second-Stage-Opt procedure uses a simple principle to quickly generate the initial feasible loading and unloading decision and then uses a reoptimize heuristic operator to improve the initial loading and unloading decision. The details of the Second-Stage-Opt procedure are given as follows.Step 1: determine the initial loading and unloading quantities of all stations and the depot. The loading and unloading quantities at each station are defined as the corresponding redistribution demand. Because the demand of the depot is 0, the loading and unloading quantities are also defined as 0. As a result, the initial solution of the BRPSD is generated, including two-stage decisions, namely, the routing decision and the loading and unloading decision. It is obvious that the initial solution is often not feasible.Step 2: adjust the loading and unloading quantities of some stations to achieve a feasible initial solution. If the number of bikes on the truck when it travels directly from stationi to station j in scenarioξyijξ>Qoryijξ<0, then the initial solution is not feasible. In this case, the loading and unloading quantity of station i should be adjusted. Setγ=yijξ−Q,ifyijξ>Qorγ=yijξ, ifyijξ<0, then the loading and unloading quantity of station i is adjusted to subtract γfrom the original quantity.Step 3 (reoptimize): the basic idea of the reoptimize operator is to optimize the solution by a heuristic method that adjusts the loading and unloading quantities between stations and the depot [5,7]. In this paper, some bikes can be collected from the depot to meet the delivery demands of some stations, and also some bikes collected from some stations can be delivered to the depot at the end of the repositioning. In this procedure, there are two cases. In the first case, the truck picks up extra bikes when it starts from the depot and drops them off at some stations. In the second case, the truck picks up more bikes from some stations and drops them off when it ends at the depot.


## 4.1.1. Construct the Initial Route for all Scenarios

Since the route in all scenarios is the same, the greedy heuristic algorithm is used to quickly construct the initial route by ignoring the stochastic redistribution demand. In this work, the nearest principle is used to construct the initial route by inserting stations one by one.


## 4.1.2. Determine Loading and Unloading Decision for Each Scenario

For a given scenarioξ and the corresponding redistribution demand diξ at station i in the scenario, the Second-Stage-Opt procedure uses a simple principle to quickly generate the initial feasible loading and unloading decision and then uses a reoptimize heuristic operator to improve the initial loading and unloading decision. The details of the Second-Stage-Opt procedure are given as follows.Step 1: determine the initial loading and unloading quantities of all stations and the depot. The loading and unloading quantities at each station are defined as the corresponding redistribution demand. Because the demand of the depot is 0, the loading and unloading quantities are also defined as 0. As a result, the initial solution of the BRPSD is generated, including two-stage decisions, namely, the routing decision and the loading and unloading decision. It is obvious that the initial solution is often not feasible.Step 2: adjust the loading and unloading quantities of some stations to achieve a feasible initial solution. If the number of bikes on the truck when it travels directly from stationi to station j in scenarioξyijξ>Qoryijξ<0, then the initial solution is not feasible. In this case, the loading and unloading quantity of station i should be adjusted. Setγ=yijξ−Q,ifyijξ>Qorγ=yijξ, ifyijξ<0, then the loading and unloading quantity of station i is adjusted to subtract γfrom the original quantity.Step 3 (reoptimize): the basic idea of the reoptimize operator is to optimize the solution by a heuristic method that adjusts the loading and unloading quantities between stations and the depot [5,7]. In this paper, some bikes can be collected from the depot to meet the delivery demands of some stations, and also some bikes collected from some stations can be delivered to the depot at the end of the repositioning. In this procedure, there are two cases. In the first case, the truck picks up extra bikes when it starts from the depot and drops them off at some stations. In the second case, the truck picks up more bikes from some stations and drops them off when it ends at the depot.


## 4.2. Neighborhood Structure

In this paper, the local search operator aims at routing decisions. Three kinds of classical operators Swap move, Relocate move, and 2-opt move are used. These operators are also often used in other BRP problems. Each new neighborhood solution is generated by these three moves with equal probability. Note that, after a local search operator is executed, the new solution needs to be improved bySecond-Stage-Opt procedure to obtain the second-stage decision.Swap-N1: randomly select two stations from the route and then exchange themRelocate-N2: randomly select one station, delete it from the current route, and then insert it into another position2-Opt-N3: randomly select two stations, exchange the positions of the two stations, and change the orientation of the route between the two stations


## 4.3. The Proposed SABRPSD

Algorithm1 provides the pseudocodes of the SABRPSD. Parameter T0 denotes the initial temperature; TE is the final temperature; α is the coefficient used to control the cooling; Iiter indicates the number of generated new solutions under a certain temperature; and Maxiter is the max number of the accepted new solutions under a certain temperature. In this section, we use S0 and Sbest to denote the initial solution and the best solution obtained so far, respectively. The best objective value F(Sbest) is set to be the objective function value of the best solution Sbest.Algorithm 1: SABRPSD.
Obtain the initial solutionS0.Set the parameter for the simulated annealing,T0, TE, α, Iiter, MaxiterSetSbest ⟵ S0; Scurrent ⟵ S0; T ⟵ T0.WhileT ≥ TEdom ⟵ 0; n ⟵ 0;Whilem ≤ Iiter ＆ n ≤ MaxiterdoS ⟵ Local search (Scurrent, Nk);Snew ⟵ Second-Stage-Opt (S);Δ ⟵F(Snew) − F(Scurrent);If Δ ≤ 0 thenScurrent ⟵ Snew, n ⟵ n + 1;IfF(Scurrent) ≤ F(Sbest) thenSbest ⟵ Scurrent;endelseIfe−Δ/T≥randomthenScurrent ⟵ Snew, n ⟵ n + 1;endendm ⟵ m + 1;endT ⟵ α ⃞ T;endReturn: SbestAs shown in Algorithm1, in the inner loop of the SABRPSD algorithm, a random new neighborhood solution Snew is initially generated by Local search procedure to improve the first-stage decision and then followed by Second-Stage-Opt procedure to generate the second-stage decision. The stopping criteria for the inner loop are either it has generated Iiter new solutions or accepted Maxiter new solution under the current temperature T. When the current temperature T decreases to TE, the SABRPSD algorithm terminates.


## 5. Numerical Examples

In this section, numerical examples are conducted to examine the validity and efficiency of the proposed model and solving algorithm. In addition, the necessity of considering stochastic demands is examined by analyzing the expected value of perfect information (EVPI) and the value of the stochastic solution (VSS).In this study, we consider the instances as in [24] to conduct the numerical experiments (the instances are available at http://www.or.unimore.it/site/home/online-resources). The size of the instances ranges from 20 to 90 stations. There are a total of 20 instances and 30 scenarios for each instance. In any instance, the first station is chosen to be the depot. To better analyze the impact of relevant parameters on the solution of the stochastic model, for a given set N0, station i and station j belong the set N0, and we redefine the parameter transportation time tij as tij = tij/min{tij}.The SABRPSD was coded in Matlab, and all computational experiments were carried out on a computer with an Intel Core i5-4590 CPU @ 3.30 GHz and 4 GB RAM. Each instance was run 10 times, the best and average of the solutions, and the average computing time of 10 runs were used to evaluate the performance of the algorithm solution.The SABRPSD proposed in this study relies on five parameters, namely, the initial temperature T0; the final temperature TE; the coefficient used to control the cooling α; the number of generated solutions under a certain temperature Iiter; and the number of accepted solutions under a certain temperature Maxiter. After some preliminary experiments, the results from the algorithm were obtained by setting T0 = 20, TE = 0.1, α = 0.97, Iiter = 3 ∗ |N0|, and Maxiter = |N0|.


### 5.1. The Performance Comparison between Lingo and SA Algorithm

In terms of the quality of the solution and the calculation efficiency, Tables1–4 show the comparison results obtained by Lingo and SABRPSD under different truck capacity Q, the holding cost Ch, and the number of stations. The CPU (in seconds) indicates the average computing time of the SABRPSD or the computing time for Lingo, respectively. GapBest (%) and GapAvg (%) indicate the performance of the SABRP relative to that of Lingo based on the best and average objective values, respectively. When |N0| ≥ 50, Lingo is not able to obtain any feasible solutions for the problems, and thus, the results are not shown in the tables. It also generally fails to obtain any global optimal solutions within 3600 seconds even for small-size problems (with four exceptions for the results obtained under instance Washington (20)2). From Tables 1–4, we can see that SABRPSD is significantly faster than Lingo in all instances, i.e., it has better time efficiency to solve the BRPSD compared to Lingo. For the various sizes of problems from small to large, the average computing time of the SABRPSD varies from 66.14 s to 70.22 s.Table 1
Comparison of the results between Lingo and SABRPSD (Q = 20 and Ch = 1).
InstanceLingoSABRPSDGapBest (%)GapAvg (%)Optimal valueCPUBest valueAverage valueCPUWashington (20)1639.153600639.16639.1710.150.000.00Washington (20)2576.79159576.79576.7924.580.000.00Chicago (20)1166.243600153.40153.4020.85−7.72−7.72Chicago (20)2115.193600113.46113.4614.04−1.50−1.50Washington (30)1450.193600387.78388.0330.77−13.86−13.81Washington (30)2520.393600403.12405.0925.22−22.53−22.16Chicago (30)1518.023600265.71266.9654.21−48.71−48.47Chicago (30)2204.143600202.21204.1429.48−0.940.00Washington (40)1797.873600634.07638.5244.71−20.53−19.97Washington (40)21036.513600826.68831.6229.94−20.24−19.77Chicago (40)11287.453600424.34424.3452.13−67.04−67.04Chicago (40)2478.013600213.10215.9248.37−55.42−54.83Washington (50)1546.18554.30105.62Washington (50)2603.40611.7277.76Chicago (50)326.32328.5970.84Washington (66)682.51685.62101.87Chicago (66)6243.756494.41122.49Washington (80)1719.65732.09121.20Washington (80)2678.58684.66159.47Washington (90)925.21938.56196.93Avg333566.14−24.15−23.85Table 2
Comparison of the results between Lingo and SABRPSD (Q = 10 and Ch = 1).
InstanceLingoSABRPSDGapBest (%)GapAvg (%)Optimal valueCPUBest valueAverage valueCPUWashington (20)1668.943600662.46662.5012.63−0.97−0.96Washington (20)2576.79663576.79576.7924.630.000.00Chicago (20)1164.143600164.14164.1419.190.000.00Chicago (20)2136.833600135.19135.2216.13−1.20−1.17Washington (30)1447.373600393.75393.7534.19−11.99−11.99Washington (30)2501.143600414.52417.2428.02−17.28−16.74Chicago (30)1300.483600299.42300.0534.42−0.35−0.14Chicago (30)2299.763600242.00242.6933.23−19.27−19.04Washington (40)1736.883600688.63692.1260.31−6.55−6.07Washington (40)2911.883600855.64863.2038.21−6.17−5.34Chicago (40)1576.943600449.41449.4147.47−22.10−22.10Chicago (40)2538.803600243.16245.9850.99−54.87−54.35Washington (50)1581.86588.8485.98Washington (50)2647.38650.6375.82Chicago (50)353.99354.5169.17Washington (66)676.54683.9390.98Chicago (66)6192.786468.38120.21Washington (80)1733.58744.35114.69Washington (80)2736.77745.27183.02Washington (90)984.90996.38228.76Avg335568.40−11.73−11.49Table 3
Comparison of the results between Lingo and SABRPSD (Q = 20 and Ch = 0).
InstanceLingoSABRPSDGapBest (%)GapAvg (%)Optimal valueCPUBest valueAverage valueCPUWashington(20)1645.103600627.85627.9013.76−2.67−2.67Washington(20)2556.2640556.26556.2633.820.000.00Chicago(20)1134.733600134.73134.7320.530.000.00Chicago(20)2100.80360099.6099.7617.95−1.19−1.04Washington(30)1414.183600369.72369.7232.90−10.73−10.73Washington(30)2432.253600392.72393.6127.89−9.15−8.94Chicago(30)1489.713600249.47249.8035.62−49.06−48.99Chicago(30)2321.253600189.40191.2131.73−41.04−40.48Washington(40)1721.113600617.41622.7650.49−14.38−13.64Washington(40)21021.873600814.77819.7942.10−20.27−19.78Chicago(40)1412.363600408.94408.9457.98−0.83−0.83Chicago(40)2397.273600201.52203.1850.88−49.27−48.86Washington(50)1526.11534.88109.26Washington(50)2592.72595.7879.45Chicago(50)321.13324.6069.87Washington(66)656.99663.09105.25Chicago(66)6243.756494.41122.49Washington(80)1702.93716.69126.66Washington(80)2661.88673.31171.68Washington(90)914.40924.30204.03Avg3303.3370.22−16.55−16.33Table 4
Comparison of the results between Lingo and SABRPSD (Q = 10 and Ch = 0).
InstanceLingoSABRPSDGapBest (%)GapAvg (%)Optimal valueCPUBest valueAverage valueCPUWashington(20)1665.083600654.91655.0110.76−1.53−1.52Washington(20)2566.2630566.26566.2625.000.000.00Chicago(20)1155.173600155.17155.1719.200.000.00Chicago(20)2127.973600127.97127.9717.380.000.00Washington(30)1449.663600382.56382.5633.10−14.92−14.92Washington(30)2442.693600410.45411.1828.40−7.28−7.12Chicago(30)1292.283600289.57290.6733.25−0.93−0.55Chicago(30)2236.603600234.10234.1032.92−1.06−1.06Washington(40)1818.253600681.61685.4061.54−16.70−16.24Washington(40)2859.043600853.74857.8447.10−0.62−0.14Chicago(40)1500.443600442.74442.7447.85−11.53−11.53Chicago(40)2349.263600239.51240.6153.41−31.42−31.11Washington(50)1571.78579.44106.77Washington(50)2638.40640.9275.32Chicago(50)352.67354.7272.96Washington(66)664.31671.8789.90Chicago(66)6175.146472.54117.22Washington(80)1728.64739.63114.94Washington(80)2722.88743.14183.62Washington(90)984.90996.38228.76Avg330369.97−7.17−7.02As shown in Tables1–4, all of the values of GapBest and GapAvg are negative. This implies that the SABRPSD performs better than Lingo. The absolute values of the average GapBest and GapAvg values obtained by the SABRPSD for the tests with Q = 20 are larger than those with Q = 10. As the capacity of the repositioning truck increases, the objective function value decreases. This may be explained by the fact that if the truck capacity increases, the truck can load/unload more bikes at one station, resulting in an expansion of the solution space. Overall, we can draw the conclusion that the proposed SABRPSD can obtain better feasible optimal solutions much faster than Lingo.


### 5.2. The Necessity of Considering Demand as a Stochastic Parameter

To evaluate the performance of the stochastic model we proposed in this paper, we use the two concepts of the evaluation approach: the expected value of perfect information (EVPI) and the value of the stochastic solution (VSS) [32–34]. EVPI measures the maximum amount a decision maker would be ready to pay in return for perfect information about the future, and VSS measures the amount of cost saving when the decision maker uses expected values of stochastic parameters instead of stochastic parameters in the model (the amount of cost due to ignoring the uncertainty). EVPI is defined as the difference between the wait-and-see solution (WS) and the here-and-now solution (HN). In the EVPI, the WS solution is the expected value of the foresight. We obtain the value by averaging the results of each stochastic scenario. The HN solution is the objective value of this two-stage stochastic model. VSS is defined as the difference between the expected results of using the expected value problem solution (EEV) and the here-and-now solution. In the VSS, the value of EEV is obtained by inputting the optimal solution of the optimization problem associated with the mean value of stochastic demands into the two-stage stochastic model. The gaps GapVSS and GapEVPI for VSS and EVPI are calculated by VSS/HN and EVPI/WS, respectively.The test instanceChicago 20(1) used for explaining the total costs of WS, HN, EEV, EVPI, and VSS is a small-size instance consisting of 20 stations. We set the truck capacity Q = 10, Ch = 1, Cd = 1, and Ct = 1.In this test instance, the total costs can be solved by the SABRPSD as follows: WS = 145.31, HN = 153.40, and EEV = 161.31. Then, calculate VSS = EEV − HN = 7.90, EVPI = HN − WS = 8.09, GapVSS = 5.15%, and GapEVPI = 5.57%. Both values of EVPI and VSS lead to the conclusion that managers must pay 5.57% more of the total cost of the stochastic solutions to obtain the perfect redistribution demand information about the future. Ignoring the uncertainty will let managers in a situation where they have a risk to pay at least 5.15% higher if they only focus on a scenario only (deterministic solutions).The results of the sensitivity analysis on GapVSS and GapEVPI for the truck capacity Q, the holding cost Ch, the penalty cost Cd, and the travel cost Ct are explained in the following. The value of the four parameters are increased by −50%, −25%, +25%, and +50%, respectively. Tables 5–8 summarize the total costs of WS, HN, EEV, EVPI and VSS, GAPEVPI, and GAPVSS obtained from all tests. Figure 1 shows the sensitivity analysis on the results for the four parameters. Under current settings, the abovementioned four parameters have a significant impact on the solutions. From Tables 5–8, consistent with theoretical results, it can be founded that WS < HN < EEV in all tests. We can see that the average GAPVSS are all greater than the average GAPEVPI. The GAPEVPI of the stochastic model in all tests is nonnegative, indicating the problem of the BRPSD is stochastic by nature. Besides, the GAPVSS in all tests is nonnegative for the BRPSD, indicating that the problem in the study is suitable for the stochastic model.Table 5
Results of different vehicle capacities (Q).
QWSHNEEVVSSGapVSS (%)EVPIGapEVPI (%)10153.86164.14168.574.432.7010.286.6815147.66156.87163.246.374.069.226.2420145.31153.40161.317.905.158.095.5725144.69151.60160.979.376.186.914.7830144.35150.87160.419.546.326.534.52Avg7.524.888.215.56Table 6
Results of different holding costs (Ch).
ChWSHNEEVVSSGapVSS (%)EVPIGapEVPI (%)0.5137.68144.73150.295.563.847.055.120.75141.89149.73155.806.074.057.845.531145.31153.40161.317.905.158.095.571.25147.43157.02166.829.796.249.606.511.5148.80160.64172.3211.697.2811.847.96Avg8.205.318.916.16Table 7
Results of different penalty costs (Cd).
CdWSHNEEVVSSGapVSS (%)EVPIGapEVPI (%)0.5120.92125.00128.243.242.594.083.380.75133.14139.57144.775.213.736.434.831145.31153.40161.317.905.158.095.571.25157.43167.19177.8410.656.379.766.201.5169.50180.97194.3713.407.4111.476.77Avg8.085.057.975.35Table 8
Results of different travel costs (Ct).
CtWSHNEEVVSSGapVSS (%)EVPIGapEVPI (%)0.596.81104.30113.729.429.047.497.740.75121.09128.84137.518.686.747.756.401145.31153.40161.317.905.158.095.571.25169.49177.97185.107.134.018.495.011.5193.61202.07208.906.833.388.474.37Avg7.995.668.065.82Figure 1
Sensitivity analysis on different values of parameters: (a)Q; (b) Ch; (c) Cd; (d) Ct.
(a)(b)(c)(d)From Figure1, we can see that the increase of Ch, Cd, and Ct rends the increase of HN. We also see that the increase of Q rends the decrease of HN. The parameter that has the greatest impact on HN is the unit transportation cost Ct. This is likely because the contribution of transportation cost to the total objective cost is greater than the penalty cost and the holding cost.From Figure1, we can see that, as Q increases, GAPEVPI tends to decrease, but GAPVSS increases. It is also noticed that GAPEVPI and GAPVSS tend to increase when Ch and Cd increase. However, the value of GAPEVPI and GAPVSS contradicts the increase of Ct. The influence of the change of the abovementioned four parameters on GAPVSS is significantly greater than that of GAPEVPI.The results illustrate that the GAPEVPI increases when Ch and Cd increase and Q and Ct decrease, which means that the decision makers are willing to pay more to get accurate redistribution demand information about the future. GAPVSS increases by increasing the values of Ch, Cd, and Q or decreasing the values of Ct, and consequently, the decision makers can obtain more cost saving resulting from the two-stage stochastic model.


## 5.1. The Performance Comparison between Lingo and SA Algorithm

In terms of the quality of the solution and the calculation efficiency, Tables1–4 show the comparison results obtained by Lingo and SABRPSD under different truck capacity Q, the holding cost Ch, and the number of stations. The CPU (in seconds) indicates the average computing time of the SABRPSD or the computing time for Lingo, respectively. GapBest (%) and GapAvg (%) indicate the performance of the SABRP relative to that of Lingo based on the best and average objective values, respectively. When |N0| ≥ 50, Lingo is not able to obtain any feasible solutions for the problems, and thus, the results are not shown in the tables. It also generally fails to obtain any global optimal solutions within 3600 seconds even for small-size problems (with four exceptions for the results obtained under instance Washington (20)2). From Tables 1–4, we can see that SABRPSD is significantly faster than Lingo in all instances, i.e., it has better time efficiency to solve the BRPSD compared to Lingo. For the various sizes of problems from small to large, the average computing time of the SABRPSD varies from 66.14 s to 70.22 s.Table 1
Comparison of the results between Lingo and SABRPSD (Q = 20 and Ch = 1).
InstanceLingoSABRPSDGapBest (%)GapAvg (%)Optimal valueCPUBest valueAverage valueCPUWashington (20)1639.153600639.16639.1710.150.000.00Washington (20)2576.79159576.79576.7924.580.000.00Chicago (20)1166.243600153.40153.4020.85−7.72−7.72Chicago (20)2115.193600113.46113.4614.04−1.50−1.50Washington (30)1450.193600387.78388.0330.77−13.86−13.81Washington (30)2520.393600403.12405.0925.22−22.53−22.16Chicago (30)1518.023600265.71266.9654.21−48.71−48.47Chicago (30)2204.143600202.21204.1429.48−0.940.00Washington (40)1797.873600634.07638.5244.71−20.53−19.97Washington (40)21036.513600826.68831.6229.94−20.24−19.77Chicago (40)11287.453600424.34424.3452.13−67.04−67.04Chicago (40)2478.013600213.10215.9248.37−55.42−54.83Washington (50)1546.18554.30105.62Washington (50)2603.40611.7277.76Chicago (50)326.32328.5970.84Washington (66)682.51685.62101.87Chicago (66)6243.756494.41122.49Washington (80)1719.65732.09121.20Washington (80)2678.58684.66159.47Washington (90)925.21938.56196.93Avg333566.14−24.15−23.85Table 2
Comparison of the results between Lingo and SABRPSD (Q = 10 and Ch = 1).
InstanceLingoSABRPSDGapBest (%)GapAvg (%)Optimal valueCPUBest valueAverage valueCPUWashington (20)1668.943600662.46662.5012.63−0.97−0.96Washington (20)2576.79663576.79576.7924.630.000.00Chicago (20)1164.143600164.14164.1419.190.000.00Chicago (20)2136.833600135.19135.2216.13−1.20−1.17Washington (30)1447.373600393.75393.7534.19−11.99−11.99Washington (30)2501.143600414.52417.2428.02−17.28−16.74Chicago (30)1300.483600299.42300.0534.42−0.35−0.14Chicago (30)2299.763600242.00242.6933.23−19.27−19.04Washington (40)1736.883600688.63692.1260.31−6.55−6.07Washington (40)2911.883600855.64863.2038.21−6.17−5.34Chicago (40)1576.943600449.41449.4147.47−22.10−22.10Chicago (40)2538.803600243.16245.9850.99−54.87−54.35Washington (50)1581.86588.8485.98Washington (50)2647.38650.6375.82Chicago (50)353.99354.5169.17Washington (66)676.54683.9390.98Chicago (66)6192.786468.38120.21Washington (80)1733.58744.35114.69Washington (80)2736.77745.27183.02Washington (90)984.90996.38228.76Avg335568.40−11.73−11.49Table 3
Comparison of the results between Lingo and SABRPSD (Q = 20 and Ch = 0).
InstanceLingoSABRPSDGapBest (%)GapAvg (%)Optimal valueCPUBest valueAverage valueCPUWashington(20)1645.103600627.85627.9013.76−2.67−2.67Washington(20)2556.2640556.26556.2633.820.000.00Chicago(20)1134.733600134.73134.7320.530.000.00Chicago(20)2100.80360099.6099.7617.95−1.19−1.04Washington(30)1414.183600369.72369.7232.90−10.73−10.73Washington(30)2432.253600392.72393.6127.89−9.15−8.94Chicago(30)1489.713600249.47249.8035.62−49.06−48.99Chicago(30)2321.253600189.40191.2131.73−41.04−40.48Washington(40)1721.113600617.41622.7650.49−14.38−13.64Washington(40)21021.873600814.77819.7942.10−20.27−19.78Chicago(40)1412.363600408.94408.9457.98−0.83−0.83Chicago(40)2397.273600201.52203.1850.88−49.27−48.86Washington(50)1526.11534.88109.26Washington(50)2592.72595.7879.45Chicago(50)321.13324.6069.87Washington(66)656.99663.09105.25Chicago(66)6243.756494.41122.49Washington(80)1702.93716.69126.66Washington(80)2661.88673.31171.68Washington(90)914.40924.30204.03Avg3303.3370.22−16.55−16.33Table 4
Comparison of the results between Lingo and SABRPSD (Q = 10 and Ch = 0).
InstanceLingoSABRPSDGapBest (%)GapAvg (%)Optimal valueCPUBest valueAverage valueCPUWashington(20)1665.083600654.91655.0110.76−1.53−1.52Washington(20)2566.2630566.26566.2625.000.000.00Chicago(20)1155.173600155.17155.1719.200.000.00Chicago(20)2127.973600127.97127.9717.380.000.00Washington(30)1449.663600382.56382.5633.10−14.92−14.92Washington(30)2442.693600410.45411.1828.40−7.28−7.12Chicago(30)1292.283600289.57290.6733.25−0.93−0.55Chicago(30)2236.603600234.10234.1032.92−1.06−1.06Washington(40)1818.253600681.61685.4061.54−16.70−16.24Washington(40)2859.043600853.74857.8447.10−0.62−0.14Chicago(40)1500.443600442.74442.7447.85−11.53−11.53Chicago(40)2349.263600239.51240.6153.41−31.42−31.11Washington(50)1571.78579.44106.77Washington(50)2638.40640.9275.32Chicago(50)352.67354.7272.96Washington(66)664.31671.8789.90Chicago(66)6175.146472.54117.22Washington(80)1728.64739.63114.94Washington(80)2722.88743.14183.62Washington(90)984.90996.38228.76Avg330369.97−7.17−7.02As shown in Tables1–4, all of the values of GapBest and GapAvg are negative. This implies that the SABRPSD performs better than Lingo. The absolute values of the average GapBest and GapAvg values obtained by the SABRPSD for the tests with Q = 20 are larger than those with Q = 10. As the capacity of the repositioning truck increases, the objective function value decreases. This may be explained by the fact that if the truck capacity increases, the truck can load/unload more bikes at one station, resulting in an expansion of the solution space. Overall, we can draw the conclusion that the proposed SABRPSD can obtain better feasible optimal solutions much faster than Lingo.


## 5.2. The Necessity of Considering Demand as a Stochastic Parameter

To evaluate the performance of the stochastic model we proposed in this paper, we use the two concepts of the evaluation approach: the expected value of perfect information (EVPI) and the value of the stochastic solution (VSS) [32–34]. EVPI measures the maximum amount a decision maker would be ready to pay in return for perfect information about the future, and VSS measures the amount of cost saving when the decision maker uses expected values of stochastic parameters instead of stochastic parameters in the model (the amount of cost due to ignoring the uncertainty). EVPI is defined as the difference between the wait-and-see solution (WS) and the here-and-now solution (HN). In the EVPI, the WS solution is the expected value of the foresight. We obtain the value by averaging the results of each stochastic scenario. The HN solution is the objective value of this two-stage stochastic model. VSS is defined as the difference between the expected results of using the expected value problem solution (EEV) and the here-and-now solution. In the VSS, the value of EEV is obtained by inputting the optimal solution of the optimization problem associated with the mean value of stochastic demands into the two-stage stochastic model. The gaps GapVSS and GapEVPI for VSS and EVPI are calculated by VSS/HN and EVPI/WS, respectively.The test instanceChicago 20(1) used for explaining the total costs of WS, HN, EEV, EVPI, and VSS is a small-size instance consisting of 20 stations. We set the truck capacity Q = 10, Ch = 1, Cd = 1, and Ct = 1.In this test instance, the total costs can be solved by the SABRPSD as follows: WS = 145.31, HN = 153.40, and EEV = 161.31. Then, calculate VSS = EEV − HN = 7.90, EVPI = HN − WS = 8.09, GapVSS = 5.15%, and GapEVPI = 5.57%. Both values of EVPI and VSS lead to the conclusion that managers must pay 5.57% more of the total cost of the stochastic solutions to obtain the perfect redistribution demand information about the future. Ignoring the uncertainty will let managers in a situation where they have a risk to pay at least 5.15% higher if they only focus on a scenario only (deterministic solutions).The results of the sensitivity analysis on GapVSS and GapEVPI for the truck capacity Q, the holding cost Ch, the penalty cost Cd, and the travel cost Ct are explained in the following. The value of the four parameters are increased by −50%, −25%, +25%, and +50%, respectively. Tables 5–8 summarize the total costs of WS, HN, EEV, EVPI and VSS, GAPEVPI, and GAPVSS obtained from all tests. Figure 1 shows the sensitivity analysis on the results for the four parameters. Under current settings, the abovementioned four parameters have a significant impact on the solutions. From Tables 5–8, consistent with theoretical results, it can be founded that WS < HN < EEV in all tests. We can see that the average GAPVSS are all greater than the average GAPEVPI. The GAPEVPI of the stochastic model in all tests is nonnegative, indicating the problem of the BRPSD is stochastic by nature. Besides, the GAPVSS in all tests is nonnegative for the BRPSD, indicating that the problem in the study is suitable for the stochastic model.Table 5
Results of different vehicle capacities (Q).
QWSHNEEVVSSGapVSS (%)EVPIGapEVPI (%)10153.86164.14168.574.432.7010.286.6815147.66156.87163.246.374.069.226.2420145.31153.40161.317.905.158.095.5725144.69151.60160.979.376.186.914.7830144.35150.87160.419.546.326.534.52Avg7.524.888.215.56Table 6
Results of different holding costs (Ch).
ChWSHNEEVVSSGapVSS (%)EVPIGapEVPI (%)0.5137.68144.73150.295.563.847.055.120.75141.89149.73155.806.074.057.845.531145.31153.40161.317.905.158.095.571.25147.43157.02166.829.796.249.606.511.5148.80160.64172.3211.697.2811.847.96Avg8.205.318.916.16Table 7
Results of different penalty costs (Cd).
CdWSHNEEVVSSGapVSS (%)EVPIGapEVPI (%)0.5120.92125.00128.243.242.594.083.380.75133.14139.57144.775.213.736.434.831145.31153.40161.317.905.158.095.571.25157.43167.19177.8410.656.379.766.201.5169.50180.97194.3713.407.4111.476.77Avg8.085.057.975.35Table 8
Results of different travel costs (Ct).
CtWSHNEEVVSSGapVSS (%)EVPIGapEVPI (%)0.596.81104.30113.729.429.047.497.740.75121.09128.84137.518.686.747.756.401145.31153.40161.317.905.158.095.571.25169.49177.97185.107.134.018.495.011.5193.61202.07208.906.833.388.474.37Avg7.995.668.065.82Figure 1
Sensitivity analysis on different values of parameters: (a)Q; (b) Ch; (c) Cd; (d) Ct.
(a)(b)(c)(d)From Figure1, we can see that the increase of Ch, Cd, and Ct rends the increase of HN. We also see that the increase of Q rends the decrease of HN. The parameter that has the greatest impact on HN is the unit transportation cost Ct. This is likely because the contribution of transportation cost to the total objective cost is greater than the penalty cost and the holding cost.From Figure1, we can see that, as Q increases, GAPEVPI tends to decrease, but GAPVSS increases. It is also noticed that GAPEVPI and GAPVSS tend to increase when Ch and Cd increase. However, the value of GAPEVPI and GAPVSS contradicts the increase of Ct. The influence of the change of the abovementioned four parameters on GAPVSS is significantly greater than that of GAPEVPI.The results illustrate that the GAPEVPI increases when Ch and Cd increase and Q and Ct decrease, which means that the decision makers are willing to pay more to get accurate redistribution demand information about the future. GAPVSS increases by increasing the values of Ch, Cd, and Q or decreasing the values of Ct, and consequently, the decision makers can obtain more cost saving resulting from the two-stage stochastic model.


## 6. Conclusions

In this paper, a general scenario-based two-stage programming model is proposed for bike repositioning problems with stochastic redistribution demands. In the proposed model, the first-stage decisions correspond to the routing decisions and the second-stage decisions correspond to the loading and unloading decisions. The model aims to find the best routes and the ideal quantities of loading and unloading at each station and depot in order to minimize the weighted sum of the expected transportation costs, penalty costs, and holding costs. Then, a simulated annealing algorithm is proposed to solve the model. Number examples are performed to evaluate the proposed model and algorithm, followed by a detailed sensitivity analysis that studies how the change of several important parameters affects the performance of the proposed model and solution algorithm. The proposed model and algorithm have important theoretical and practical significance for the BSS operators, which can reduce the operation costs of the BSS and improve user satisfaction. On the contrary, in addition to bike sharing, other sharing facilities in the sharing economy, such as car sharing, also need to be relocated, so this kind of problem has a strong application background.In the future, we will apply robust optimization model to solve the bike repositioning problem with stochastic demand in the bike sharing system [35]. We also consider environmental issues by adding the carbon emissions to the objective function of the two-stage stochastic programming model [36–38].



---

*Source: 8868892-2020-05-20.xml*