In the past few years, ridesharing has been becoming increasingly popular in urban areas worldwide for its low cost and environment friendliness. In a typical scenario, the ridesharing service provider matches drivers of private vehicles or taxis to those seeking local taxicab- like transportation. Much research attention has been drawn to the optimization of travel costs in shared rides. However, other important factors in ridesharing, such as the social comfort, trust issues and revenue, have not been fully considered in the existing works. Social-aware ridesharing, which makes use of social relations among drivers and riders to address safety issues, and dynamic pricing, which dynamically determines shared ride fares, are two active research directions with important business implications. In this dissertation, we take the first step to comprehensively investigate the social-aware ridesharing queries. First, we study the problem of the top-k social-aware taxi ridesharing query. In particular, upon receiving a user's trip request, the service ranks feasible taxis in a way that integrates detour in time and passengers' cohesion in social distance. We propose a new system framework to support such a social-aware taxi-sharing service. It provides two methods for selecting candidate taxis for a given trip request. The grid-based method quickly goes through available taxis and returns a relatively larger candidate set, whereas the edge-based method takes more time to obtain a smaller candidate set. Furthermore, we design techniques to speed up taxi route scheduling for a given trip request. We propose travel-time based bounds to rule out unqualified cases quickly, as well as algorithms to find feasible cases efficiently. We evaluate our proposals using a real taxi dataset from New York City. Experimental results demonstrate the efficiency and scalability of the proposed taxi recommendation solution in real-time social-aware ridesharing services. Second, we study the problem of efficient matching of offers and requests in social-aware ridesharing. We formulate a new problem, named Assignment of Requests to Offers (ARO), that aims to maximize the number of served riders while satisfying the social comfort constraints as well as spatial-temporal constraints. We prove that the ARO problem is NP- hard. We then propose an exact algorithm for a simplified ARO problem. We further propose three pruning strategies to efficiently narrow down the searching space and speed up the assignment processing. Based on these pruning strategies, we develop two novel heuristic algorithms, the request-oriented approach and offer-oriented approach, to tackle the ARO problem. We also study the dynamic ARO problem and present a novel algorithm to tackle this problem. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches on real-world datasets. Third, we study the top-k vehicle matching in social ridesharing. In the current ridesharing research, optimizing social cohesion and revenue at the same time has not been well studied. We present a new pricing scheme that better incentivizes drivers and riders to participate in ridesharing, and then propose a novel type of Price-aware Top-k Matching (PTkM) queries which retrieve the top-k vehicles for a rider's request by taking into account both social relations and revenue. We design an efficient algorithm with a set of powerful pruning techniques to tackle this problem. Moreover, we propose a novel index tailored to our problem to further speed up query processing. Extensive experimental results on real datasets show that our proposed algorithms achieve desirable performance for real-world deployment. The work of this thesis shows that the social-aware ridesharing query processing techniques are effective and efficient, which would facilitate ridesharing services in real world.
| Identifer | oai:union.ndltd.org:hkbu.edu.hk/oai:repository.hkbu.edu.hk:etd_oa-1726 |
| Date | 04 December 2019 |
| Creators | Fu, Xiaoyi |
| Publisher | HKBU Institutional Repository |
| Source Sets | Hong Kong Baptist University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Open Access Theses and Dissertations |
Page generated in 0.0019 seconds