Politecnico di Torino (logo)

An association rule based framework for dynamic systems rebalancing: an application to bike sharing.

Marco Cipriano

An association rule based framework for dynamic systems rebalancing: an application to bike sharing.

Rel. Paolo Garza, Sara Comai. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2020

PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (1MB) | Preview

Bike sharing systems are spreading throughout the world, being used by more and more people every day. Anyway, a higher diffusion means more bikes to manage and reorganise among bike sharing stations to guarantee a good quality of the service. Up to today, it does not exist a universally accepted algorithm to rebalance the distribution of bikes over a dock-based bike sharing system. From an extensive review of the current state of the art, it appears that, although bike sharing is a very active research field, there are few papers about dynamic rebalancing algorithms and all the existing ones are based on mathematical models of bike sharing stations. This thesis presents a completely data-driven based framework to solve the dynamic rebalancing problem of a bike sharing dock-based system and its application on Barcelona’s bike sharing system. The available dataset includes two input sources. The former contains the stations’ position, name and unique identifier. The latter is a log produced by the stations of Barcelona’s bike sharing system. Log lines are generated by each station every 2 minutes and contain the number of taken and free slots. The proposed framework can be decomposed in 3 main blocks: preprocessing, rules extraction and station rebalancing. Since Barcelona’s bike sharing system data are not perfect, the preprocessing block deletes log lines of unavailable stations and removes stations either frequently unavailable or having a number of bike slots that fluctuates too much. Finally, the input dataset is partitioned according to different time-based criteria to generate 4 sets of data of different granularity. This partitioning allows the framework to extract recurrent patterns present in different time ranges. As a consequence, each partition will be considered as a different rebalancing approach in the last step of the framework. The rules extraction block elaborates the data generated during the preprocessing phase, detecting the “critical” bike sharing stations per timestamp. A station is considered “critical” when it has an occupancy rate different of at least a threshold t with respect to the average occupancy rate of near stations. Both the threshold t and the maximum distance d at which two stations are considered near each other are parameters of the framework. After that, the framework extracts association rules between critical stations for each of the 4 partitions and filters the ones containing only stations belonging to the same neighbourhood. In this way, it is possible to highlight problematic neighbourhoods, where employees must be sent in order to move bikes between critical stations. Finally, the station rebalancing block orders association rules in a descendant fashion by confidence, support and length and exploits the top N rules to reallocate bikes among critical stations. N is a parameter of the framework and it is supposed to be the number of trucks available to move the bikes, being sent one per neighbourhood when the system has to be rebalanced. The framework’s performance is measured in terms of number of: stations that are not critical anymore after the rebalancing (fixed), bike movements between stations and critical stations fixed per movement.

Relators: Paolo Garza, Sara Comai
Academic year: 2020/21
Publication type: Electronic
Number of Pages: 78
Corso di laurea: Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering)
Classe di laurea: New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING
Aziende collaboratrici: Politecnico di Torino
URI: http://webthesis.biblio.polito.it/id/eprint/16604
Modify record (reserved for operators) Modify record (reserved for operators)