|
Data Science seminar Date: Tuesday, 22 June 2023 Time: 11:00 AM - 12:00 PM Venue: Online Opportunistic problems along the shortest path on road networks Debajyoti Ghosh BML Munjal University. 22-06-23 Abstract Spatial information has now become a crucial tool for decision-making and daily needs for billions of people worldwide. Users rely on route planning apps to find the shortest paths when traveling on the road network and typically undertake to accomplish tasks as they go from their source to destination. For instance, they might pick up coffee along the way or might indulge in activities for profit such as pick up and deliver packages. We discuss two problems in this talk involving opportunistic services around the shortest path. In particular, we will consider “near shortest paths” which are paths from source to destination that involve small but bounded detours. In the first problem, we propose a spatial platform that assigns packages to drivers (for delivery) en-route to their destinations while specifying the detour limit on their shortest path on road networks. In the second problem, we propose a spatial platform that quickly determines if a given POI (e.g., coffee shops, gas stations, businesses with offers, etc.) is along the shortest path involving bounded detours. The novelty in this solution is that we will make the determination without actually computing the shortest path during runtime. We advocate a preprocessing strategy as a way of supporting the necessary throughput to cater to a large number of users. To that end, we have developed efficient algorithms that rely on both run-time and precomputed strategies. Experimental results show the applicability of our techniques to real-world use-cases. Short bio: Debajyoti earned B.Sc (Hons.) in Computer Science from the University of Calcutta (2004), an M.Sc in Computer Science from the University of Calcutta (2006), and an M.Tech in CSE from the University of Calcutta (2008). Presently, he is on the verge of completing his PhD (Thesis submission is expected on June 2023) at BML Munjal University, Gurgaon, Haryana. He has 15 years of teaching experience at the undergraduate level of Computer Science and Engineering. He taught several places including BITS Pilani, Goa campus, NIIT University, and BML Munjal University. His research area includes Spatial query processing and optimization, opportunistic shortest path problems on road networks, Design and Analysis of Algorithms, and Graph Algorithms.
|
