Scalable opportunistic shortest path problems on road networks

Abstract

Spatial information has now become a crucial tool for decision-making and daily needs for millions of people worldwide. Route planning apps are used by millions of users to find the shortest paths when traveling on the road network. This dissertation deals with opportunistic problems along the shortest paths involving a small but bounded detour in order to achieve common tasks such as picking up and delivering a package on the way, or stopping at a POI on the way from the source to the destination. newlineThe problems studied here are from the perspective of a spatial platform provider that wants to offer opportunistic services to its millions of users. Hence, the key dimensions of interest are the scalability of the platform in terms of latency to serve a user quickly and a large throughput to cater to billions of users. The strategy the dissertation advocates is precomputation, which provides the necessary scalability to serve billions of users and spatial objects of interest (e.g., packages, POIs, etc.). newlineDuring the literature review, it was observed that existing research predominantly focuses on single-package deliveries, especially those picked up by drivers along their existing routes. In our proposed study, we tackled the same challenge of delivering a package directly to a designated driver while adhering to a pre-specified detour limit. Our objective was to identify which available packages could be efficiently integrated into a driver s route with minimal detours. This allowed users to gradually deliver packages with increasing detours as they traveled. newlineTo address this challenge, we introduced a spatial platform known as Package Delivery as a Service (PDaaS), tailored for expansive road networks. PDaaS offers users optimal route suggestions to enhance the efficiency of package deliveries during their journeys. We demonstrated that the proposed algorithm s performance scales effectively with the increasing number of packages. newline