On demand high capacity ride sharing for mobility on demand (MoD) systems

Abstract

Mobility-on-demand (MoD) systems are emerging as a novel mode for urban mobility which have enabled the users to have a reliable medium for mobility requirements. Ride sharing services provided by these mobility on demand systems provide not just a personalized experience in mobility but also present an immense potential for positive societal impacts with reference to pollution, energy consumption, congestion, and etc. Ride sharing services primarily concern with picking up spatiotemporally distributed mobility demand and delivering it within a pre-specified time window subjected to different other constraints. Large scale ride sharing in more sophisticated spatiotemporally distributed mobility demand distributions require mathematical models and algorithms in order to match riders and vehicle fleets in real time. As such common requirement of models which address the potential of ride sharing is meticulously planned routes for a fleet of taxis. Accordingly another such requirement is to incorporate meeting points in route planning. In this work, we address the use of aforementioned two requirements for ride sharing systems. Therefore our main contribution lies in the intersection of (1) determining optimal routes for fleet of taxis with arbitrary set of constraints and, (2) introducing meeting points to improve ride sharing. We approach the optimal route planning problem by proposing two new types of queries called Generalized Optimal Single Meeting Point Route (GOSMPR) query and Generalized Optimal Multi Meeting Point Route (GOMMPR) query in road networks. Given a vehicle current location 𝑠, a set of origin and destinations pairs of passenger set 𝑃 and, an arbitrary set of constraints 𝐶, GOSMPR aims to find the optimal route for the given taxi such that the selected route traverse all origins and destinations while adhering to the constraints set C and minimizing the total path cost. In the same way, GOMMPR address the same problem but by replacing each origin and destination with set of pickup points and drop off points respectively. We show that problem of GOSMPR and GOMMPR queries are NP-hard. Thus to address the GOSMPR problem efficiently, we propose a dynamic programming approach inspired by 𝐴* algorithm. To reduce the search state space of the proposed algorithm, we propose a series of state elimination criteria and a novel variant of classical Held Karp lower bound of Travelling Salesman Problem (TSP) as a heuristic. Also to address the GOMMPR problem, we propose another dynamic programming based algorithm. We demonstrate that our proposed iii algorithm for GOSMPR can efficiently solve 10 passenger requests (21 points)(more than the capacity of a typical ride sharing vehicle) optimally while the algorithm for GOMMPR can solve up to 4 passenger requests within acceptable time limits. We also conduct extensive experiments to demonstrate the impact of meeting points in the context of ride sharing. We compare state of art ride sharing model RS-ILP and our new meeting points based model RSMP-ILP to demonstrate the impact of meeting points. We show that there is an improvement of 1.53% in service rates in RSMP-ILP compared to RS-ILP which corresponds to 5048 trips in total.