Relazione di adempimento al Dottorato di Ricerca in Informatica
Centro de Informática
Universidade Federal de Pernambuco, Brazil Cotutela: Dipartimento di Informatica
Università di Pisa, Italy
Vinícius Cezar Monteiro de Lira
During the period of PhD in Computer Science, the undersigned candidate, Vinícius Cezar Monteiro de Lira, has carried out his research in the field of Ride-Sharing Systems. In particular, his PhD thesis proposes a ride matching algorithm for alternative destinations and a machine learning approach to identify potential users for a transportation service towards large events. In the following, a brief description of the research results obtained during the PhD of the candidate. With regard to the activities performed by the candidate during his PhD, this document also reports the courses and seminars attended, publications obtained, and the list of stays abroad.
1. Research Results
People living in highly-populated cities increasingly suffer an impoverishment of their quality of life due to pollution and traffic congestion problems caused by the huge number of circulating vehicles. Indeed, the reduction of circulating vehicles is one of the most difficult challenges in large metropolitan areas. We proposed a research contribution with the final objective of reducing travelling vehicles. This was done towards two different directions: on the one hand, we improved the efficacy of ride sharing systems, creating a larger number of ride possibilities based on the passengers destination activities. On the other hand, we proposed a social media analysis method, based on machine learning, to identify groups of users who are going to participate in an event, with the objective of potentially enabling them to share a ride.
Concerning the first research direction we investigated a novel approach to boost ride sharing opportunities based, not only on fixed destinations, but also on alternative destinations while preserving the intended activity of the user (LIRA et al, 2015, LIRA et al, 2017a, LIRA et al, 2018). Ride matching algorithms are used to find feasible associations between driver and passengers (FURUHATA et al., 2013). Basically, the drivers offer rides using their vehicles and, in turn, the riders seek for available rides to reach their desired destination. A feasible matching must satisfy certain spatial-temporal constraints such as: passenger’s pick-up time, pick-up
location and destination, and drivers’ route and departure time (FURUHATA et al., 2013). However, when there are few ride offers available, it might be difficult to find feasible matches (WANG et al., 2016; STIGLIC et al., 2016). Therefore several methods to enhance the number of possible matchings have to be developed in the literature. A largely adopted solution to improve ride-sharing opportunities consists in relaxing the spatio-temporal constraints (STIGLIC et al., 2016; GEISBERGER et al., 2010; FURUHATA et al., 2013; AGATZ et al., 2012) such as delay and walking distance tolerance of the passengers or drivers’ route detours. However, these approaches focus only on spatial and temporal constraints for the matching between ride offers and ride requests, without exploring a valuable dimension: the semantics behind the ride requests. Here, with semantic we refer to the activity that is going to be performed by the passenger at the trip destination. We observe, in fact, that in many cases the activity motivating the use of a private car (e.g., going to a shopping mall) can be performed at many different locations (e.g. all the shopping malls in a given area). Our assumption is that, when there is the possibility of sharing a ride, people may accept visiting an alternative destination to fulfill their needs. By analyzing two large mobility datasets, extracted from a popular social network, we show that increasing individuals’ flexibility in changing destination could have a large impact on urban mobility. In fact, we found that with our approach there is an increase up to 54.69% in ride-sharing opportunities compared to a traditional fixed destination-oriented approach. We thus proposed Activity-Based Ride Matching (ABRM), an algorithm aimed at matching ride requests with ride offers to alternative destinations where the intended activity can still be performed.
For the second research contribution, we focused on the analysis of social media for inferring the transportation demands for large events (LIRA et al, 2017b, LIRA et al, 2019). Large events like important music concerts, religious celebrations or sports matches, attract thousands of participants. These events cause the movement of thousands of people to a specific location at a given time. In general, a large event requires careful transportation planning to facilitate the attendees’ arrival at the event location from their diverse departure locations. For this reason, often the event organizers provide the participants with dedicated transportation services (e.g. bus, carpooling, shuttle) to supply the demand for rides. However, for large events involving a massive number of attendees, the identification of this demand of rides might not be a straightforward process, requiring new methods to devise them (SINNOTT; CHEN, 2016a). Our investigation starts from observing that large events are well reflected in social media (e.g. Facebook, Foursquare, Instagram, Twitter). We noticed how popular events are well reflected in social media, where people share their feelings and discuss their experiences. In this context, we investigated the novel problem of exploiting the content of non-geotagged posts to infer users’ attendance of large events. We identified three temporal periods: before, during and after an event. We detail the features used to train the event attendance classifiers on the three temporal periods and report on experiments conducted on two large music festivals in the UK, namely VFestival and Creamfields events. Our classifiers attained very high accuracy, with the highest result observed for Creamfields festival (∼91% accuracy to classify users that will participate in the event). We study the most informative features for the tasks addressed and the generalization of the learned models across different
events. Furthermore, we proposed an example of application of our methodology in event-related transportation. This proposed application aimed to evaluate the geographic areas with a higher potential demand for transportation services to an event.
2. Exams Taken
Exams taken at the Universidade Federal de Pernambuco: ● Programação Paralela (Parallel Programing);
● Trabalho Individual Em Banco De Dados (Advances in Database);
● Tópicos Avançados Em Inteligência Computacional (Advanced Topics in Intelligent Computation)
Exams taken at the Università di Pisa:
● Mine Learning Techniques and Selected Applications for Big Data ● Deep Learning
● IoT - Internet of Things
3. Participation in Seminars
Participation in seminars at the Universidade Federal de Pernambuco: ● Seminários (Seminars in Computer Science);
Participation in seminars at the Università di Pisa: ● Mauriana Pesaresi Seminars;
● Seminar in Service, Cloud and Fog Computing;
4. Period abroad
Besides the period spent in both universities that the candidate is in join supervision (i.e. Universidade Federal de Pernambuco, Brazil and Università di Pisa, Italy), the candidate also spent two month, from 27 July 2016 to 29 September 2016 in the Universidade of Glasgow, Scotland, under the supervision of Professor Craig Macdonald and Professor Iadh Ounis.
5. Publication obtained
Journals:● Boosting Ride Sharing With Alternative Destinations. Vinicius Monteiro de Lira, Raffaele Perego, Chiara Renso, Salvatore Rinzivillo, Valéria Cesário Times. IEEE Trans.
● Event attendance classification in social media. Vinicius Monteiro de Lira, Craig Macdonald, Iadh Ounis, Raffaele Perego, Chiara Renso, Valéria Cesário Times. Information Processing & Management Journal, IPM, 2019.
Conferences:
● The ComeWithMe System for Searching and Ranking Activity-Based Carpooling Rides. Vinicius Monteiro de Lira, Chiara Renso, Raffaele Perego, Salvatore Rinzivillo, Valéria Cesário Times. In Proceedings of the 39th International ACM conference on Research and Development in Information Retrieval, pp. 1145- 1148. (ACM SIGIR) Pisa, Italy July 17 - July 21, 2016.
● ComeWithMe: An activity-oriented carpooling approach. Vinícius Monteiro de Lira, Valeria Cesario Times, Chiara Renso, Salvatore Rinzivillo. IEEE 18th International Conference on Intelligent Transportation Systems, pp. 2574-2579, ITSC 2015. ● Exploring Social Media for Event Attendance. Vinicius Monteiro de Lira, Craig
Macdonald, Iadh Ounis, Raffaele Perego, Chiara Renso, Valéria Cesário Times. Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, pp. 447-450, ASONAM 2017, Sydney, Australia, July 31 - August 03, 2017.
Signature of the candidate (Vinícius Cezar Monteiro de Lira):
References:
(Wang et al, 2016) Wang, X.; Dessouky, M.; Ordonez, F. A pickup and delivery problem for ridesharing considering congestion. Transportation Letters, Taylor & Francis, v. 8, n. 5, p. 259–269, 2016
(STIGLIC et al, 2016) Stiglic, M.; Agatz, N.; Savelsbergh, M.; Gradisar, M. Making dynamic ride-sharing work: The impact of driver and rider flexibility. Transportation Research Part E: Logistics and
Transportation Review, v. 91, n. Supplement C, p. 190 – 207, 2016. ISSN 1366-5545.
(SINNOTT, CHEN, 2016) Sinnott, R. O.; Chen, W. Estimating crowd sizes through social media. In: 2016 IEEE International Conference on Pervasive Computing and Communication Workshops, PerCom Workshops 2016, Sydney, Australia, March 14-18, 2016. [s.n.], 2016. p. 1–6.
(GEISBERGER et al, 2010) Geisberger, R.; Luxen, D.; Neubauer, S.; Sanders, P.; Völker, L. Fast detour computation for ride sharing. In: ATMOS 2010 - 10th Workshop on Algorithmic Approaches for
Transportation Modeling, Optimization, and Systems, Liverpool, United Kingdom, September 6-10, 2010. [S.l.: s.n.], 2010. p. 88–99.
(AGATZ et al, 2012) Agatz, N.; Erera, A.; Savelsbergh, M.; Wang, X. Optimization for dynamic
ride-sharing: A review. European Journal of Operational Research, v. 223, n. 2, p. 295 – 303, 2012. ISSN 0377-2217.
(FURUHATA et al, 2013) Furuhata, M.; Dessouky, M.; Ordóñez, F.; Brunet, M.-e.; Wang, X.; Koenig, S. Ridesharing: The state-of-the-art and future directions. Transportation Research Part B: Methodological, v. 57, p. 28 – 46, 2013. ISSN 0191-2615.
(LIRA et al, 2019) Event attendance classification in social media. Vinicius Monteiro de Lira, Craig Macdonald, Iadh Ounis, Raffaele Perego, Chiara Renso, Valéria Cesário Times. Information Processing & Management Journal, IPM, 2019.
(LIRA et al, 2018) Boosting Ride Sharing With Alternative Destinations. Vinicius Monteiro de Lira, Raffaele Perego, Chiara Renso, Salvatore Rinzivillo, Valéria Cesário Times. IEEE Trans. Intelligent Transportation Systems, Volume 19. pp. 2290-2300 (2018).
(LIRA et al, 2017a) The ComeWithMe System for Searching and Ranking Activity-Based Carpooling Rides. Vinicius Monteiro de Lira, Chiara Renso, Raffaele Perego, Salvatore Rinzivillo, Valéria Cesário Times. In Proceedings of the 39th International ACM conference on Research and Development in Information Retrieval, pp. 1145- 1148. (ACM SIGIR) Pisa, Italy July 17 - July 21, 2016.
(LIRA et al, 2017b) Exploring Social Media for Event Attendance. Vinicius Monteiro de Lira, Craig
Macdonald, Iadh Ounis, Raffaele Perego, Chiara Renso, Valéria Cesário Times. Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, pp. 447-450, ASONAM 2017, Sydney, Australia, July 31 - August 03, 2017.
(LIRA et al, 2015) ComeWithMe: An activity-oriented carpooling approach. Vinícius Monteiro de Lira, Valeria Cesario Times, Chiara Renso, Salvatore Rinzivillo. IEEE 18th International Conference on Intelligent Transportation Systems, pp. 2574-2579, ITSC 2015.
