| dc.description.abstract | This thesis examines the dynamic rebalancing of a bike sharing system (BSS). A BSS is a service where bicycles are made available to users on a short-term basis. However, imbalanced systems is a significant challenge and often results in unmet customer demand. A set of service vehicles are utilized to re-distribute the bicycles and to maintain a balanced system. The primary objective of this thesis is to implement a model that generates optimal rebalancing strategies for the service vehicles with the aim of reducing violated demand. The BSS in Oslo, operated by Urban Infrastructure Partners (UIP), is used as a sample case in this thesis. As the customer demand is unknown, the real-world problem is both dynamic and stochastic. In our solution method, the problem is simplified by approximating it into a set of smaller deterministic subproblems where the customer demand is assumed known. These smaller subproblems are defined as Dynamic Deterministic Bicycle Rebalancing Subproblems (DDBRS).\\
Through a comprehensive literature survey, it becomes evident that it is insufficient to use exact solution methods to solve the DDBRS of realistic sizes, and heuristic approaches are necessary. However, there is a lack of efficient heuristic solution algorithms for solving the DDBRS. Column generation heuristics applied to BSSs are not discovered in literature, despite its success on vehicle routing problems (VRPs). Because of the enormous amount of variables in the DDBRS, a column generation heuristic may be appropriate.\\
An arc-flow model is formulated and differs from others in the literature as we allow the service vehicles to initiate a trip that exceeds the time horizon. By doing this, the idle time of the service vehicle at the end of the period reduces, and a rebalancing strategy beneficial in the long run can be initiated instead of a shorter disadvantageous strategy. Additionally, the service vehicles strive to fulfill an optimal station inventory level at the end of each subproblem. This inventory level accounts for future demand. Altogether, these aspects incorporate a long-term focus.\\
A column generation heuristic is developed and consists of an initialization procedure, a master problem, and a pricing problem. We propose three different variations of the master problem. The amount of information predetermined differs for the three master problems. In version 1, the loading quantities are determined in the master problem; in version 2, the loading quantities are predetermined in the initialization and re-evaluated in the master problem; and in version 3, the loading quantities are entirely predetermined. The initialization process consists of a branching algorithm that generates many initial columns, i.e. routes, for each service vehicle, while the master problem determines the optimal combination of columns by allocating one column to each service vehicle. A heuristic pricing problem is developed with the goal of generating new and better columns. For diversification of routes, a model for clustering of stations is implemented. \\
Parameter tuning for the subproblem is conducted, and the parameters are set to their best-performing values. We observe that the computational time of the subproblem is highly dependent on the branching constant in the initialization, the number of possible visits to a station within the time horizon, and the number of service vehicles. Multiple visits to a station lead to drastic increases in computational time and only a marginal improvement in solution, hence, multiple visits is concluded to be unnecessary. Additionally, the different versions of the master problem are compared. The results shows that version 3, with predetermined loading quantities, outperforms the other versions.\\
As the subproblem does not account for real-world uncertainties, the results are simulated using an implemented discrete-event simulator. A system configuration is evaluated by observing the average total violations from ten randomly drawn demand scenarios generated based on historical data. Some parameters are re-tested in a dynamic setting, and the final configurations for the column generation heuristic are set. Further, operational insights are gathered, and is intended as a basis for strategic decision-making. Our heuristic is compared to UIP's current rebalancing method, and a reduction in the total violations of 31\% is observed. The effect of various strategic decisions regarding the BSS are analyzed, e.g. the number of service vehicles and bicycles, the size of the service vehicles, different prioritization of starvations and congestions, and the effect of enabling geo-fencing. By implementing our column generation heuristic, allowing geo-fencing and increasing the number of bicycles in the system, the total violation can decrease with as much as 81\% compared to today's current rebalancing strategies. | |
