Citation
Mishra, Saurabh, and Sonia Khetarpaul. "Optimal Placement of Taxis in a City Using Dominating Set Problem." In Databases Theory and Applications: 32nd Australasian Database Conference, ADC 2021, Dunedin, New Zealand, January 29–February 5, 2021, Proceedings 32, pp. 111-124. Springer International Publishing, 2021.
Abstract
Mobile application based ride-hailing systems, e.g., DiDi, Uber have become part of day to day life and natural choices of transport for urban commuters. However, the pick-up demand in any area is not always matching with the supply or drop-off request in the same area. Urban planners and researchers are working hard to balance this demand and supply situation for taxi requests. The existing approaches have mainly focused on clustering of the spatial regions to identify hotspots, which refer to the locations with a high demand for pick-up requests. In our study, we determined that if the hotspots focus on the clustering of high demand for pick-up requests, most of the hotspots pivot near the city center or two-three spatial regions, ignoring the other parts of the city. In this work, we proposed a method, which can help in finding a local hotspot to cover the whole city area. We proposed a dominating set problem based solution, which covers every part of the city. This will help the drivers looking for near-by next customer in the region wherever they drop their last customer. It will also reduce the waiting time for customers as well as for a driver looking for next pick-up request. This would maximize their profit as well as help in improving their services.
