A heuristic approach to bicycle repositioning problems with dynamic pricing

3.1. Modeling Analysis

In model M1, the unknown decision variables include p _tijk , v _ti , and dependent variables x _tijk . To reduce the number of variables, we will express the recursive function v _ti in terms of the known parameter v_1i and decision variable x _tijk .

Lemma 1: v _ti can be re-expressed by (8) and (9).

v ti = v 1 i - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik , ∀ i , 1 < t ≤ K .(8) v ti = v 1 i - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - K ∑ j = 1 M ∑ k = 1 K x sjik + ∑ s = t - K + 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik , ∀ i , 1 < K < t .(9)

Proof: The assertion holds for t = 2 and t ≤ K since from (6) we have

v 2 i = v 1 i - ∑ s = 1 1 ∑ j = 1 M ( ∑ k = 1 K x sijk - ∑ k = 1 1 x sjik ) , ∀ i .(10)

Assume the assertion holds for t - 1, we have

v ti = v t - 1 , i - ∑ j = 1 M ∑ k = 1 K x t - 1 , ijk + ∑ j = 1 M ∑ k = 1 t - 1 x t - k , jik = v 1 i - ∑ s = 1 t - 2 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - 2 ∑ j = 1 M ∑ k = 1 t - 1 - s x sijk - ∑ j = 1 M ∑ k = 1 K x t - 1 , ijk + ∑ j = 1 M ∑ k = 1 t - 1 x t - k , jik = v 1 i - ∑ s = 1 t - 1 ∑ j = 1 M ( ∑ k = 1 K x sijk - ∑ k = 1 t - 2 x sjik ) .(11)

Thus, the assertion of equation (8) holds. For t = K + 1, By (6) and (8), we have

v K + 1 , i = v Ki - ∑ j = 1 M ∑ k = 1 K x Kijk + ∑ j = 1 M ∑ k = 1 K x K - k + 1 , jik = v 1 i - ∑ s = 1 K - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 K - 1 ∑ j = 1 M ∑ k = 1 K - s x sijk - ∑ j = 1 M ∑ k = 1 K x Kijk + ∑ j = 1 M ∑ k = 1 t - 1 x K - k + 1 , jik = v 1 i - ∑ s = 1 K ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 1 ∑ j = 1 M ∑ k = 1 K x sjik + ∑ s = 2 K ∑ j = 1 M ∑ k = 1 K - s + 1 x sjik .(12)

Thus, the assertion of Eq.(9) holds for t = K + 1. Using the same logic, by induction, we can show that

v ti = v 1 i - ∑ s = 1 t - 2 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - K - 1 ∑ j = 1 M ∑ k = 1 K x sjik + ∑ s = t - K t - 2 ∑ j = 1 M ∑ k = 1 t - s - 1 x sjik - ∑ j = 1 M ∑ k = 1 K x t - 1 , ijk + ∑ j = 1 M ∑ k = 1 K x t - k , jik

= v 1 i - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - K ∑ j = 1 M ∑ k = 1 K x sjik + ∑ s = t - K + 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik .(13)

Thus, we have completed the proof of Lemma 1.

Lemma 2: Setting v _ti as that in constraints (8) and (9) is equivalent to setting constraint (3).

Proof: For 2 ≤ t ≤ K, substituting equation (8) into constraint (3), we have

∑ i = 1 M v 1 i - ∑ s = 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 t - s x sjik + ∑ i = 1 M ∑ j = 1 M ∑ k = 1 t - 1 ∑ g = k + 1 K x t - k , ijg = S .(14)

Since ∑ i = 1 M ∑ j = 1 M ∑ k = 1 t - 1 ∑ g = k + 1 K x t - k , ijg = ∑ s = 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = t - s + 1 K x sijk , we have

∑ s = 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 t - s x sjik + ∑ s = 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x t - k , ijg = ∑ s = 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x sijk .(15)

Thus, the right-hand side of Eq. (14) becomes ∑ i = 1 M v 1 i . the result of ∑ i = 1 M v 1 i is the total capacity, that is ∑ i = 1 M v 1 i = S , and thus the statement holds for 2 ≤ t ≤ K. For 2 ≤ K < t, substituting equation (9) in constraint (3), we have

∑ i = 1 M v 1 i - ∑ s = 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - K ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x sjik + ∑ s = t - K + 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 t - s x sjik + ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K - 1 ∑ g = k + 1 K x t - k , ijg = S .(16)

Note

∑ i = 1 M ∑ j = 1 M ∑ k = 1 K - 1 ∑ g = k + 1 K x t - k , ijg = ∑ s = t - K + 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = t - s + 1 K x sijk .(17)

Then, it is clear that the sum of second, third, fourth and fifth terms is zero. The remining term in the right hand side of (3) is ∑ i = 1 M v 1 i . Thus, the right-hand side of (3) eventually leads to ∑ i = 1 M v 1 i = S when v _ti is set by (8) and (9) and the result follows.

Substituting constraints (8) and (9) in constraint (4), we can express constraint (4) by constraints (18), (19) and constraint (5) by constraints (20) to (22).

v 1 i - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik ≤ D i , ∀ 2 ≤ t ≤ K , i ,(18) v 1 i - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - K ∑ j = 1 M ∑ k = 1 K x sjik + ∑ s = t - K + 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik ≤ D i , ∀ 2 ≤ K < t , i ,(19) ∑ j = 1 M ∑ k = 1 K x 1 ijk - v 1 i ≤ 0 , ∀ i ,(20) ∑ j = 1 M ∑ k = 1 K x tijk - v 1 i + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik ≤ 0 , ∀ 2 ≤ t ≤ K , i ,(21) ∑ j = 1 M ∑ k = 1 K x tijk - v 1 i + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk - ∑ s = 1 t - K ∑ j = 1 M ∑ k = 1 K x sjik - ∑ s = t - K + 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik ≤ 0 , ∀ 2 ≤ K < t , i ,(22)

Combining equations (18)-(22) and Lemma 2, we can reduce variable v _ti in Model-1 and can re-express Model-1 as the form of maximizing PR subject to constraints (7) and (18-22). We refer to this model as Model-2 and show Model-2’s Lagrangean function below.

Lagrangean function:

The Lagrangean function of the problem L (P) is given as follows.

L ( P ) = PR - L 1 - L 2 - L 3(23)

where

L 1 = ∑ t = 2 K ∑ i = 1 M λ ti ( v 1 i - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik - D i + μ ti 2 ) + ∑ t = K + 1 T ∑ i = 1 M λ ti ( v 1 i - ∑ s = t - K + 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = t - K + 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik - D i + μ ti 2 ) ,(24) L 2 = ∑ i = 1 M γ 1 i ( ∑ j = 1 M ∑ k = 1 K x 1 ijk - v 1 i + w 1 i 2 ) - ∑ t = 2 K ∑ i = 1 M γ ti ( ∑ j = 1 M ∑ k = 1 K x 1 ijk - v 1 i + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik + w ti 2 ) + ∑ t = K + 1 T ∑ i = 1 M γ ti ( ∑ j = 1 M ∑ k = 1 K x tijk - v 1 i + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk - ∑ s = 1 t - K ∑ j = 1 M ∑ k = 1 K x sjik - ∑ s = t - K + 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik + w ti 2 ) .(25) L 3 = ∑ t = 1 T ∑ i = 1 M ∑ j = 1 M η tijk ∑ k = 1 K ( p k min - p tijk + h tijk 2 ) .(26)

where λ _ti , γ _ti and η _tijk are the Lagrange multiplier associated with the above constraints.

Remark 1: L₁ and L₂ can be rearranged as (27) and (28), respectively.

L 1 = - ∑ t = 1 K - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = t + 1 K λ si + ∑ t = 1 K - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K - t + 1 x tijk ∑ s = t + k K λ sj - ∑ t = 2 K ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = K + 1 K + t - 1 λ si - ∑ t = K + 1 T - K ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = t + 1 K + t - 1 λ si - ∑ t = T - K + 1 T - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = t + 1 T λ si + ∑ t = 2 T ∑ i = 1 M λ ti ( v 1 i - D i + μ ti 2 ) + ∑ t = K + 1 T ∑ s = t - K + 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 t - s x sijk λ sj .(27)

L 2 = ∑ t = 1 T ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K γ ti x tijk + ∑ t = 1 K - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = t + 1 K γ si - ∑ t = 1 K - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K - t x tijk ∑ s = t + k K γ sj + ∑ t = 1 K ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = K + 1 T γ si + ∑ t = K + 1 T ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = t + 1 T γ si - ∑ t = 1 T - K ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = t + K T γ sj + ∑ t = 1 T ∑ i = 1 M γ ti ( - v 1 i + w ti 2 ) - ∑ t = K + 1 T ∑ s = t - K + 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 t - s x sijk γ sj .(28)

Lemma 3: The profit function is concave.

Proof: First, we have ∂²PR/∂p _tijk ∂p_{t′i′j′k′} = 0 if p _tijk ≠ p_{t′i′j′k′}. In addition, given that the modeling assumption results in a negative ∂ 2 PR / ∂ p tijk 2 , thus, we have completed the proof.

Lemma 4: The Kuhn-Tucker necessary conditions satisfy the sufficient condition for optimality.

Proof: The solution space is convex because the constraints are all linear. Combining this constraint and Lemma 3 with concave objective function, then we have completed the proof.

Lemma 4 implies that the resulting stationary point yields a global constrained maximum. The Karush-Kuhn-Tucker (KKT) conditions are derived as follows:

∂ L ( P ) / ∂ P ) = 0 .(29) v 1 i - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik - D i + μ ti 2 = 0 , 2 ≤ t ≤ K , i .(30) v 1 i - ∑ s = t - K + 1 t - 1 ∑ j = 1 M ( ∑ k = 1 K x sijk - ∑ k = 1 t - s x sjik ) - D i + μ ti 2 = 0 , 2 ≤ K < t , i .(31) ∑ j = 1 M ∑ k = 1 t - s x 1 ijk - v 1 i + w ti 2 = 0 , ∀ i .(32) ∑ j = 1 M ∑ k = 1 K x tijk - v 1 i + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk - ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik + w ti 2 = 0 , 2 ≤ t ≤ K , i .(33) ∑ j = 1 M ∑ k = 1 K x tijk - v 1 i + ∑ s = 1 t - 1 ∑ j = 1 M ∑ k = 1 K x sijk - ∑ s = 1 t - K ∑ j = 1 M ∑ k = 1 K x sjik - ∑ s = t - K + 1 t - 1 ∑ j = 1 M ∑ k = 1 t - s x sjik + w ti 2 = 0 , 2 ≤ K < t , i .(34) p tijk min - p tijk + h tijk 2 = 0 , ∀ t , i , j , k .(35) λ ti μ ti = 0 , ∀ t , i .(36) γ ti w ti = 0 , ∀ t , i .(37) η tijk h tijk = 0 , ∀ t , i , j , k .(38)

In these cases, the first derivative of the Lagrangian function with respect to P, ∂L (P)/∂P) can be easily obtained from their current forms, except for the last terms of L₁ and L₂ in constraints (27) and (28), respectively. However, the last two terms can be expressed in forms that can be easily differentiated if the maximum rental periods, K, are provided. For example, when K = 3, the last term in constraint (27) can be rearranged by constraint (39).

∑ t = K + 1 T ∑ s = t - K + 1 t - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x sijk λ sj = ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K - 1 x 2 ijk λ K + 1 , j + ∑ t = K T - K + 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 K x tijk ∑ s = t + k K + t - 1 λ sj + ∑ t = T - K + 2 T - 1 ∑ i = 1 M ∑ j = 1 M ∑ k = 1 T - t x tijk ∑ s = t + k T λ sj .(39)

The last term of L₂ in constraint (28) is the result when λ _sj is replaced with γ _sj in constraint (39).

The KKT condition system may not be easy to solve. To reduce the complexity, we denote the following three sets: Ω₁ (λ), Ω₂ (γ), Ω₃ (η), in which Ω₁ (λ) = {(t, i) |λ _ti = 0,   ∀  t, i}, Ω₂ (γ) = {(t, i) |γ _ti = 0,   ∀  t, i}, Ω₃ (η) = {(t, i) |η _tijk = 0,   ∀  t, i, j, k}, respectively. According to the values of the three sets, by (36)-(38), we can set u _ti = 0 for (t, i) ∉ Ω₁ (λ), w _ti = 0 for (t, i) ∉ Ω₂ (γ), and h _tijk = 0 for (t, i, j, k) ∉ Ω₃ (η), and eliminate constraints (36)-(38). We propose a hybrid evolution method based on linear programming and genetic algorithm (GA) to produce the values of Ω₁ (λ), Ω₂ (γ) and Ω₃ (η). The encoding scheme and decoding method are as follows.

Chromosome θ = (θ₁, θ₂, ⋯, θ_2TM+TMMK) in a population is expressed by an integer string over [0, 9]. Suppose that, for example, a chromosome for a case of T = 2, M = 2 and K = 1 is generated as

θ = ( 8 , 0 , 3 , 1 , 0 , 7 , 3 , 9 , 5 , 9 , 6 , 8 , 2 , 3 , 8 , 1 ) .(40)

We use the values of (θ₁, θ₂, ⋯, θ₁₆) to judge whether the value of λ_1,1, λ_1,2, ⋯, η_2,2,2,1 is zero or not. The n-th parameter is set to zero if its encoding value is θ _n ≤ σ, where σ is a prespecified parameter. For example, suppose that we set the value of σ in the above case at σ = 8. Then, we have Ω₁ (λ) = {(1, 2), (2, 1), (2, 2)}, Ω₂ (γ) = {(1, 1), (1, 2), (2, 1)} and Ω₃ (η) = {(1, 1, 1, 1), (1, 2, 1, 1), (2, 1, 1, 1), (2, 1, 2, 1), (2, 2, 2, 2)}. Accordingly, λ _ti = 0 for (t, i) ∈ Ω₁ (λ), γ _ti = 0 for (t, i) ∈ Ω₂ (γ), and η _tijk = 0 for (t, i, j, k) ∈ Ω₃ (η). In addition, we have u _ti = 0 for (t, i) ∉ Ω₁ (λ), w _ti = 0 for (t, i) ∉ Ω₂ (γ), and h _tijk = 0 for (t, i, j, k) ∉ Ω₃ (η).

Evaluation:.

Elimination of nonlinear constraints (36-38). The parameters of λ _ti , γ _ti , η _tijk , u _ti , w _ti and h _tijk provide the characteristics of either λ _ti = 0 or u _ti = 0, γ _ti = 0 or w _ti = 0, and η _tijk = 0 or h _tijk = 0. Therefore, λ _ti u _ti = 0, γ _ti w _ti = 0, and η _tijk h _tijk = 0. Constraints (36) to (38) can, thus, be withdrawn. We refer to the result as the KKT₁ system.

The solution to Model 3 must be a feasible solution to the original problem. The value of G in (41) depends on the value of chromosome θ. If the objective value, G, converges to an extremely small number, Then the result is reported; otherwise, the chromosomes are renewed based on the standard GA operator to update the set of Ω₁ (λ), Ω₂ (γ), and Ω₃ (η); step 1 is repeated to improve the solution quality.

The solution procedure applies the mathematical programming approach, and performs the evolution and refinement of the GA to obtain solutions. The solution procedure can also confirm global constrained maximum when a solution to Model 3 leads to G = 0, and all parameters λ _ti , γ _ti , η _tijk , u _ti , w _ti and h _tijk are non-negative.

Lemma 5: Model-3 is a linear formulation if x _tijk is a linear function of p _tijk .

Proof: The result follows since constraints (30) to (35) and ∂PR/∂p _tijk are all linear. Thus, we have completed the proof.

The case of x _tijk = a _tijk - b _tijk p _tijk is a typical demand type, where a _tijk is the demand scale and b _tijk is the price elasticity. It is a linear function of p _tijk . Linear programming can be used to solve Model 3 to obtain optimal solution. The formulation of ∂L (P)/∂P depends on K. The solution can be easily derived. The result of ∂L (P)/∂P for K = 3 is as follows.

∂ L ( P ) / ∂ P = ∑ m = 1 11 Δ m .(42)

where

Δ 1 = a tijk + b tijk ( γ ti - 2 p tijk ) + η tijk , ∀ t , i , j , k ,(43) Δ 2 = b tijk ( ∑ s = t + k K ( λ sj - γ sj ) - ∑ s = t + 1 K ( λ si - γ si ) ) ∀ t ≤ K - 1 , i , j , k ,(44) Δ 3 = - b tijk ∑ s = K + 1 K + t - 1 λ si , ∀ 2 ≤ t ≤ K , i , j , k ,(45) Δ 4 = - b tijk ∑ s = t + 1 K + t - 1 λ si , ∀ K + 1 ≤ t ≤ T - K , i , j , k ,(46) Δ 5 = - b tijk ∑ s = t + 1 T λ si , T - K < t < T - 1 , i , j , k ,(47) Δ 6 = b tijk ( λ K + 1 , j - γ K + 1 , j ) , ∀ t = 2 , i , j , k ,(48) Δ 7 = b tijk ∑ s = t + k K + t - 1 ( λ sj - γ sj ) , ∀ K ≤ t ≤ T - K + 1 , i , j , k ,(49) Δ 8 = b tijk ∑ s = t + k T ( λ sj - γ sj ) , ∀ T - K + 2 ≤ t < T , i , j , 1 ≤ k ≤ T - t ,(50) Δ 9 = b tijk ∑ s = K + 1 T γ si , ∀ 1 ≤ t < K , i , j , k ,(51)

Δ 10 = b tijk ∑ s = t + 1 T γ si , ∀ K + 1 ≤ t < T - 1 , i , j , k ,(52) Δ 11 = - b tijk ∑ s = K + t T γ sj , ∀ t < T - K , i , j , k .(53)

The right-hand side of Eqs. (42-53) is zero if (t, i, j, k) is not in the specified range in each equation. These formulas are omitted to save space. For example, ∂L (P)/∂P = Δ₁ + Δ₂ + Δ₉ + Δ₁₁ for t = 1, and ∂ L ( P ) / ∂ P = ∑ m = 1 3 Δ m + Δ 6 + Δ 9 + Δ 11 for t = 2.

4.1. Problem description

The case discussed in this section consists of M = 35 rental stations near Mass Rapid Transit stations, which are obtained from A-bike Company in Taiwan. The locations of these bicycle rental stations are numbered 1-35 in Fig. 1.

OPEN IN VIEWER

Fig. 1.

Locations of bike stations.

A-bike Company charges NT$20 per hour for the first 4 hours and NT$20 per hour (a half period rental) when the rental and return stations are the same. For each 30-minute block, the company charges NT$10 for the first 4 hours, NT$20 for the next 4 hours, and NT$40 for more than 8 hours. We divide a day into T = 12 equal time periods, each having two hours. Table 1 shows the number of bicycle docking piles for the 35 stations.

The values of the required parameters were estimated as follows. The numbers of initial bicycles at the start of period 1, v_1i, were set at the entire value of 0.8D _i (Table 2).

The minimum rental prices were set at NT$1 for all rental types. The demand markets for the company are assumed to follow a price dependent linear function d _tijk (p _tijk ). The values of a _tijk were set at a _tijk = α _t β _ijk D _i , in which parameters α _t are the time-variant scales and parameters β _ijk are the location and rental length-variant scales. The value of α _t is set at 0.1 for t = 1, 2, 3 and 12; 0.8 for t = 4, 9 and 10; 0.7 for t = 5; 0.6 for 6 ≤ t ≤ 8; and 0.4 for t = 11. The value of β _ijk was randomly generated over [0.004, 0.08] for k = 1, [0.004, 0.06] for k = 2, and [0.004, 0.035] for k = 3 under ∑ j = 1 M ∑ k = 1 K β ijk = 1 . The values of the price elastics b _tijk were randomly generated over [ a tijk / p tijk o , 1.8 a tijk / p tijk o ] , where p tijk o is the original rental price. We use symbols a tijk o , b tijk o , and v 1 i o to represent the values of a _tijk , b _tijk , and v_1i, respectively, as set and referred as basic values.

Five types of problems were designed, and seven cases were generated for each problem type. The number of bicycle stations is set to five for Problem type 1 and 35 for Problem types 3-5. For Problem type 2, the number of bicycle stations is incremental from 5 to 35. The values of all parameters in all cases of all the problem types are the same as that set in the previous section, except for the following changes.

In Problem types 1 and 3, we change the number of initial bicycle incrementally from 0.85 v 1 i o to 1.15 v 1 i o with 0.05 equal-percentage increment. In Problem type 4, we change the value of demand coefficient incrementally from 0.85 a tijk o to 1.15 a tijk o . In Problem type 5, we change the value of demand coefficient b _tijk incrementally from 0.85 b tijk o to 1.15 b tijk o .

4.3. Computational results

Problem types 1-2 were used to evaluate the performance of the proposed solution procedure. To confirm the solution, we use the Lingo global solver to identify the global maximum for all instances. We use HS to stand for the proposed heuristic approach. The computational results confirm the following:

The Lingo global solver can produce feasible solutions within 4h CPU time for problem instances, in which the number of stations is not larger than 15. Among these results, the Lingo global solver could only confirm global optimums for all cases in Problem type 1.

Sensitivity analyses were performed to investigate the impact of the initial located bicycles, v_1i, and demand coefficients a _tijk and b _tijk on the computational results. We use initials RS = PR/S and ST = SD/S to represent the average rental revenue per bicycle and the average leased frequency per bicycle, respectively, where SD is the total number of biked rented out.

Problem types 1 and 3 investigates the impact of allocated number of bicycles on the computational results. The effects of the number of initial bicycles on the computational results are displayed in Tables 3 for small-scale problems (Problem type 1) and in Table 5 for large-scale problems (Problem type 3). From Columns 9 and 10 of Table 3 and Columns 7-8 of Table 5, the values of RS and ST decrease as the number of allocated bicycles, v_1i, and total number of bicycles, S, increases. Columns 4 and 5 of Table 5 shows that the revenues and number of bike rented out (SD) increase as the number of initial bicycles increases. This phenomenon fits the general cognition that considerable capacities can produce substantial sales and revenues. However, the results of Problem type 1 verify that this phenomenon does not always hold. Column 4 of Table 3 shows that the revenues increase as the number of initial bicycles increases. However, when the value of v_1i reaches 0.95 v 1 i o , the revenue begins to descend. The reason may be that the number of available docking poles decreases with the number of bicycles allocated. A demand is composed of a rental and a return service; thus, insufficient bicycle docking poles may result in lost sales. The phenomenon reflects that considerable capacities cannot guarantee the generation of substantial sales and revenues. The number of initial bicycles allocated currently is suitable for the network with five bicycle stations. We can also affirm that the marginal revenue decreases as the number of bicycles increases.