Simulating and Evaluating Rebalancing Strategies
for Dockless Bike-Sharing Systems

The demand model works by polling a Poisson process generated from historical bike trip data. The data consists of an origin station, destination station and timestamp for every trip. However in dockless BSS, there is no notion of stations, and the raw data consists of a collection of location pings with bike IDs which must get processed and clustered into abstract stations. This whole procedure is described later in Section 3. Once processed, we combine data from certain days of the week that exhibit similar ridership timings and patterns in order to increase the amount of data at hand when generating the Poisson process. Data from Monday through Thursday forms one category, Friday another, and Saturday and Sunday a third. These groupings are based on an analysis of variance across weekdays within our data set and findings presented by Xu et al [8]. Then following a similar data aggregation strategy as [9], the bike trip data is sorted into hourly bins per each category based on the start time and weekday of the trip. Then for each hour for every station, a rate of bikes out (demand) on 2 minute intervals is recorded to form a Poisson process. To generate the demand simulation, for every station, the demand random variable is polled as a Poisson random variable 30 times due to the 2 minute intervals and the sum of the bikes out is the demand at that station for that hour. To generate complete bike trips with assigned origins and destinations, a probability distribution per station is built per hour with 2-minute polling intervals for the destinations of trips from historical bike data. Then for every station and its generated demand-out, the respective destination random variable is polled the demand-out number of times to assign destinations and create complete trips. Furthermore, since the trips have assigned destinations, this creates an implicit model for supply when counting the number of trips that have a given station set as their destination. Using this technique, the demand simulation can generate trips for every station at every hour of the week.

In this section we describe the generic model of the Dockless Repositioning Problem. We modify the objective function, inputs, and a few constraints from the Mixed Integer Linear Program (MILP) proposed by Ghosh et al [6] to develop a Mixed Integer Program (MIP) to represent the dockless case. The problem can be represented using the following tuple:

$\mathcal{S}$ denotes the set of abstracted base stations and $d^{t}_{s}$ represents the number of bikes at station $s\in\mathcal{S}$ at time-step $t$. We have a set of repositioning vehicles where $C_{\textit{v}}^{*}$ represents the number of bike slots in the vehicle $v\in\mathcal{V}$. The $\mathcal{F}^{t}$ represents a set of $\mathcal{K}$ discrete training demand scenarios generated by the aforementioned demand model at time-step $t$. More concretely, $F_{s,\textit{k}}^{t+}$ and $F_{s,\textit{k}}^{t-}$ represent the number of bikes entering and exiting station $s$ in demand scenario $k$ at time $t$ respectively . Lastly, $N_{p}$ is the maximum number of pickup locations at each time-step for each vehicle and $N_{d}$ is the maximum number of drop off locations at each time-step for each vehicle.

Solving this MIP returns an optimal repositioning strategy for only a single time-step $t$. In order to optimize over a time range, the LP must be solved for increasing values of $t$ and station bike amounts updated after each time-step. This iterative process is described further in Section 2.3.

For simplicity purposes, we make the following assumptions. First, we assume that a repositioning vehicle can make only one repositioning trip per time-step by setting $N_{p}$ and $N_{d}$ to 1. This includes time spent collecting bikes within the neighborhood of the abstract initial station and placing the bikes within the neighborhood of the abstract final station. We also assume all bikes within the confines of the abstract station are accessible and homogeneous, meaning they are all equally likely to be selected by users for a trip or selected by the operator for a repositioning task.

To represent the repositioning tasks, we introduce the following decision variables:

• •

  $y_{s,v}^{+}$ denotes the number of bikes dropped off by vehicle $v$ at station $s$;

• •

  $y_{s,v}^{-}$ denotes the number of bikes picked up by vehicle $v$ from station $s$;

• •

  $b_{s,v}^{+}$ is a binary decision variable. It is set to 1 if vehicle $v$ dropped off any bikes at station $s$ and 0 otherwise.

• •

  $b_{s,v}^{-}$ is a binary decision variable. It is set to 1 if vehicle $v$ picked up any bikes from station $s$ and 0 otherwise.

• •

  $L_{s}^{k}$ denotes the lost demand (as a negative number) at station $s$ for demand scenario $k$.

We can now describe the method for computing repositioning tasks for the vehicles.

• •

  Objective (1): Minimize lost profit. Lost profit is computed as the difference between the number of repositioning trips to handle all $\mathcal{K}$ demand scenarios for all $v\in\mathcal{V}$ and all $s\in\mathcal{S}$ multiplied by some cost parameter $\alpha$ represented by the first term, and the sum of lost demand for each $s\in\mathcal{S}$ during each $k\in\mathcal{K}$ times some cost parameter $\beta$ represented by the second term. These cost parameters provide a simple way of comparing performance given an estimated cost and varying business models (whether the company wishes to prioritize revenue or service quality). The purpose for optimizing over the $\mathcal{K}$ demand scenarios is to come up with a single repositioning combination that works well in the general case and is not too over-fit. The program’s iterating frequency equates to rebalancing frequency and can be adjusted as well. Decisions are made one time-step at time and the program is iterative.

• •

  Constraint (2): The lost demand is the deficit between the net of the demand at a station and the bikes available at that station. The absolute value of $L_{s}^{k}$ is the number of bike trips that were lost due to improper positioning of bikes in the system. This value is the sum of the number of bikes present at $s$, the net flow of bikes computed via the demand model for $T$ time-steps into the future and the net change in bikes due to repositioning. The adjustable parameter $T$ can be used to account for the differences in static and dynamic repositioning strategies.

• •

  Constraint (3): A vehicle can not pick up more bikes than the amount present at the station. For a vehicle $v$ and a station $s$, the number of bikes picked up at $s$ at time-step $t$ may not exceed the amount present there at time-step $t$. This also ensures that a vehicle can only pick up bikes from a station it visits ($b_{s,v}^{-}$ is set to 1).

• •

  Constraint (4): A vehicle can not pick up more bikes than its capacity. For a vehicle $v$, the sum of all of the bikes it picks up may not exceed its capacity.

• •

  Constraint (5): The number of bikes picked up among all vehicles may not exceed the amount present at the station. The sum of the bikes picked up at $s$ at time-step $t$ over all vehicles $v$ must be less than or equal to the number of bikes present at $s$ at time-step $t$.

• •

  Constraint (6): A vehicle cannot drop off more bikes than its capacity. The number of bikes dropped off at station $s$ by a vehicle $v$ must be no larger than the capacity of that vehicle $v$. This also ensures that a vehicle can only drop off bikes at a station it visits ($b_{s,v}^{+}$ is set to 1).

• •

  Constraint (7): A vehicle must drop off the same number of bikes it picked up.

• •

  Constraint (8): A vehicle can only drop off at a fixed number of stations during a time-step. During dynamic repositioning, a vehicle can only visit one station in a time-step. During static repositioning, a vehicle can visit up to $N_{d}$ stations.

• •

  Constraint (9): A vehicle can only pick up from a fixed number of stations during a time-step. During dynamic repositioning, a vehicle can only visit one station in a time-step. During static repositioning, a vehicle can visit up to $N_{p}$ stations.

A mathematical caveat allows the MIP to have a binary decision variable $b$ to be set to 1 while still having its respective $y$ at 0. This explains why $N_{p}$ and $N_{d}$ refer to an upper-bound on the number of stations as a repositioning trip is only scheduled if the $y$ is non-zero. This reason is also why the objective function looks at the $y_{s,v}^{+}$ when counting the number of drop-off trips rather than $b_{s,v}^{+}$ directly.

Since BSS providers may develop different business models depending on their environment and priorities, we design the MIP to be as flexibile as possible. Parameters such as cost, number of repositioning vehicles, rebalancing frequency, etc. can be easily modified to fit different scenarios and systems.

This MIP is not formulated as a traditional linear program. However, we were able to program it directly using the Python extension of the IBM ILOP CPLEX Optimization Studio version 12.9.

The MIP described solves only for the optimal repositioning strategy at a single time-step $t$ while considering $T$ time-steps of demand into the future. In order to optimize over a time range, the MIP must be iterated over increasing $t$ time-steps and station bike amounts updated with time. When iterating over the MIP to extract results, we choose to use a time-step $t$ of 1 hour which aligns itself well with the demand model setup. Additionally since the MIP considers $T$ hours into the future, as a design decision, we choose to rebalance only once every $T$ hours so to not rebalance on an artificially inflated demand. This effectively treats the $T$ as the rebalancing frequency as well. So upon iterating, on time-steps where the MIP should not rebalance, setting $||\mathcal{V}||=0$ effectively turns off rebalancing, and then restoring the $\mathcal{V}$ re-enables the rebalancing.

We choose the genesis $t=0$ to be on a Monday at midnight. At $t=0$, for every $s\in\mathcal{S}$, its $d_{s}^{0}$ is set to a respective initial amount of bikes calculated as per Section 3.2. The demand model is polled for all $\mathcal{F}^{t}$ considering $T$ hours into the future, and then the MIP is populated with all of the parameters of the respective rebalancing strategy and solved. Once solved, the repositioning combinations $y_{s,v}^{+}$ and $y_{s,v}^{-}$ are recorded. Then a random $k_{R}$ is chosen from the $\mathcal{K}$ to be used as the guiding demand scenario at time-step $t$ when gathering results. The $\sum\limits_{s}{L_{s}^{k_{R}}}$ is recorded as the lost demand at time-step $t$ and, before the next iteration, the station bike amounts are updated as $d_{s}^{t+1}\leftarrow\max\Big{\{}d_{s}^{t}+(F_{s,k_{R}}^{t+}-F_{s,k_{R}}^{t-})+\sum\limits_{\textit{v}}(y_{s,\textit{v}}^{+}-y_{s,\textit{v}}^{-}),0\Big{\}}$. In both the static and dynamic repositioning strategies, the MIP is for the same number of iterations to facilitate a fair comparison.

Inspired from Shen et al. (2018) [2], we filter through the data for each bike by making three basic assumptions about trips. First, the time between the consecutive pings should be at least 180 seconds; we assume that users would not take a bike for less than 3 minutes. Second, the GPS locations between two time-steps must change by at least 200 meters for the change in location to be considered a trip; this filters out inconsistencies due to instability in GPS recordings. Finally, the velocity of the trip should be lower than 25 km/hour (the speed limit for bikes in Singapore); this check accounts for potential “trips” due to repositioning, where the bike is in a motored vehicle. In the event that all these conditions are satisfied, a new trip is defined.

In order to simplify the modeling, Singapore was segmented into eight separate regions based on the trip data described in Section 3.1. The origin and destination of all 939,762 trips were considered as individual points. The resulting 1,879,524 points were then clustered into eight regions using k-means clustering.

We focused specifically on the k-means defined Northern region of Singapore labeled in Figure 1. This region roughly correlates to Singapore’s Woodlands, a residential town which was selected as a microcosm of Singapore [10]. We refer to this area as the Woodlands for the remainder of the paper.

The selected region was then segmented again using a k-means clustering approach with 120 clusters. Trips that started in the Woodlands but ended in a different region or vice versa comprised less than 1% of the roughly 120,000 trips and were filtered out for simplicity. In addition, of the 7,821 bikes in this region, 890 bikes were idle throughout the entire observation period for unknown reasons, leaving 6,931 active bikes. The idle bikes were not considered when constructing the abstract stations as they had no associated trips.

The resulting 120 clusters are treated as abstract stations. To understand the feasibility of and develop a physical representation for each station, a radius and an area were estimated for each station. The radius is determined by calculating the Euclidean distance between the generated k-means central coordinates of the station and the furthest origin or destination point within that cluster. From the radius, the circular area of each station was also computed.

Each abstract station can be physically represented by the central coordinates and all of the bikes that lie within the computed radius of that coordinate. Of the 120 stations in the Woodlands, 75% of the stations are less than 1 square kilometer in area. All but seven stations have a radius less than 1 kilometer. The mean radius of the 120 stations is 0.50 km, and the mean area of the 120 stations is 1.01 $\text{km}^{2}$. This radius and area motivated the selection of 120 as the number of stations because it simplified the dockless problem through abstraction while still producing stations that covered a small enough land area to be feasibly traversed by a dockless BSS operator for repositioning. The stations were granular enough such that only 13$\%$ of trips start and end at the same abstract station. More stations may be added to increase accuracy given enough computational power to iterate the MIP.

To estimate the initial number of bikes at each station, we mapped the first GPS ping for each of the bikes present during the period of data collection. We then assigned each bike to the closest station based on Euclidean distance.

Visual representations of the 8 regions of Singapore and the 120 abstract stations in the Woodlands are shown in Figure 1.

As previously mentioned, unmanageable fleet size was a large reason for the LTA’s conservative regulations in Singapore’s dockless BSS. After being launched in 2017, dockless bikes were parked in inconvenient places, clogging up sidewalks, as well as MRT exits and entrances. Bike maintenance was difficult and faulty bikes sat on the streets for weeks or even months [2]. As a result, the Land Transport Authority (LTA) took serious restrictive measures in 2018 to regulate Dockless BSS. Two major companies had to surrender their operating licenses in Singapore and many other dockless BSS companies withdrew from the Singaporean market. In order to assure that our model and data set align with these facts, we investigate trends in bike usage in our data set.

When considering the data for all of Singapore over the month of September 2017, we notice that usage of the 47,302 bikes was quite variable. Figure 2 breaks down the large bike fleet in terms of the number of trips bikes were utilized for. While the most used bike was used 123 times that month, 11,575 (24.5%) bikes were used $\leq 4$ times and 5,858 of those bikes were unused for the entire month. Possible explanations for the skewed distribution of Figure 2 could be that: bikes broke and were left on the street; bikes were dropped in inaccessible locations (such as hidden behind a bush); there was an excess of bikes such that many of them did not need to get used.

To gain a better understanding of why bikes are unused in the Woodlands, we consider bikes idle for 7 or more consecutive days over the month of September and visualize their location alongside the abstract stations. As seen in Figure 3, a wide majority of the idle bikes were located at or near stations. It seems bikes were left in populated areas and remained unused as opposed to being left in distant areas and unused due to inaccessibility. Approximately 66% of all bikes were idle for at least 7 days at some point during September 2017, and it seems unrealistic to propose that such a high portion of bikes are broken. We conclude that there was an excess of supply and infer that our data-set reflects the complete demand.

These trends in bike usage, as well as the guidelines of the LTA’s operator license, served as motivation for investigating the impact of diminishing fleet size on the amount of lost demand in Singapore’s dockless BSS.