Matching and Pricing Algorithm in a Ride-hailing Service Based on Reinforcement Learning to Reduce Pickup Waiting Time

Abstract

With the popularization of smartphones, ride-hailing services mediate hailing requests from many users to drivers. They are expected to ease urban problems such as traffic congestion by replacing the demand for private cars. However, contrary to their intended purpose, there exists criticism that ride-hailing services exacerbate negative externalities such as traffic congestion and air pollution. Therefore, it is necessary to alleviate those negative externalities in ride-hailing services. We focus on reducing pickup waiting times, as this also helps decrease negative externalities by reducing the distance traveled by vehicles. This study develops a matching and pricing algorithm to reduce pickup waiting time based on reinforcement learning methods, namely contextual bandits and temporal difference learning. The algorithm iteratively assigns surge multipliers to individual requests and matches the requests to drivers. We apply the proposed algorithm to ride-hailing data in Singapore while investigating the effects of changes in price sensitivity and value term coefficient. The results show similar patterns to the historical matching rate during both peak hours and off-peak hours, demonstrating its applicability in large cities as big as Singapore. Simulations during the morning peak hour show that our proposed model reduces 20 kilograms of carbon dioxide emissions and decreases pickup waiting time by 15% with only a 2% reduction in revenue. By addressing matching, pricing, and reducing pickup waiting time together, this study estimates how much pickup waiting time can be potentially saved and contributes to improving ride-hailing services both in terms of user benefits and reducing externalities.

스마트폰의 대중화와 함께, 승차 공유 서비스는 많은 이용자들의 차량 호출을 운전자에게 중개해주고 있다. 이는 자가용 수요를 대체해 교통혼잡 등 도시문제를 완화할 것으로 기대된다. 그러나 애초 취지와 달리 승차 공유 서비스가 교통 혼잡과 대기오염 등 부정적인 외부효과를 악화시킨다는 비판이 제기되고 있다. 따라서, 승차 공유 서비스에서 이러한 부정적인 외부효과를 저감할 필요가 있다. 픽업 대기 시간이 줄어들면 차량이 이동하는 거리가 줄어들어 부정적 외부 효과를 줄일 수 있으므로, 본 연구는 픽업 대기 시간의 감소에 초점을 맞춘다. 본 연구에서는 픽업 대기 시간의 감소를 위하여 강화 학습을 기반으로 한 매칭 및 요금 책정 알고리즘을 개발하였다. 컨텍스츄얼 밴딧과 시간차 학습을 이용하여 개별 호출에 요율을 부여하고 운전자에게 할당하는 작업을 반복적으로 수행하는 알고리즘이다. 개발된 알고리즘은 싱가포르의 승차 공유 서비스 데이터에 적용되었다. 가격 민감도 변화의 영향과 가치항 계수 변화의 영향도 조사하였다. 첨두시간대 뿐만 아니라 비첨두 시간대에도 실제 매칭률과 유사한 매칭률 패턴을 보여 싱가포르와 같은 대도시에서의 적용 가능성을 연구하였다. 오전 첨두 시간에서의 시뮬레이션 결과, 픽업 대기 시간 단축 모델은 픽업 시간을 15% 단축하고, 이산화탄소 배출량을 20kg 절감하며, 수익은 2% 감소하는 데 그쳤다. 본 연구를 통해 동적 요금과 매칭, 픽업 대기 시간 단축을 함께 다뤄 승차 공유 서비스에서 잠재적인 픽업 대기 시간을 얼마나 절약할 수 있는지를 추정하고, 이용자 편익 측면에서 승차 호출 서비스를 개선하는 데 기여하였다.