라이드쉐어링 서비스 실시간 차량-승객 매칭 문제 리뷰

우버로 대표되는 라이드 쉐어링 (Ride sharing)서비스는 승객이 차량을 호출하면 차량이 실시간으로 응답하는 (배차되는) 수요 반응형 (On-demand) 서비스이다. 당연히 승객 모두의 대기 시간이 최소화되게끔 차량과 승객을 매칭해주는 것이 서비스 품질에 지대한 영향을 끼친다.

한국에는 라이드쉐어링 서비스는 없지만 수요 응답형 (on-demand) 서비스라고 부를만한 서비스들이 적지 않다. 라이드 헤일링(ride-hailing) 서비스인 카카오 택시, 반반 택시 부터 출퇴근 시간대 이용가능한 카풀(carpool) 서비스인 풀러스, 현대자동차가 출시한 것으로 알려진 수요 응답형 버스 등이 그 예이다. 승객의 실시간 수요를 받아서 차량의 위치를 파악해 매칭시켜주어야한다는 점에서 라이드 쉐어링 서비스의 실시간 차량-승객 매칭 알고리즘을 적용해볼 수 있고, 현재 어느정도까지 알고리즘이 발전해왔는지 파악하는 것은 유용할 것이다.

 

2017년도 이전 논문들을 살펴보면 1개 차량당 2명의 승객을 매칭하는 문제의 최적해를 구할 수 있었고 (3개부터는 heuristics 로 풀어야 함) 이마저도 static routes 였다. (static routes 라는 것은 dynamic routes 와 달리 알고리즘이 실시간으로 개선되지 않음을 의미한다.) 

쉽게 말하면 한 차량이 조금 돌아가더라도 여러명의 승객을 태우는 우버풀 (uber-pool) 같은 서비스에 이용될 수 있는 매칭 알고리즘이 없었다는 것이다. 

Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., & Rus, D. (2017). On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences, 114(3), 462-467.

2017년도에 나온 이 논문은 (1) 실시간 차량과 승객의 위치를 고려해 매칭해줄 수 있고 (2) 최대 10인까지 많은 승객을 태울 수 있는 차량 (high-capacity vehicle)을 고려한다. 이를 충분히 큰 네트워크(승객과 차량의 수가 많은 네트워크를 의미)에서도 빠른 연산 시간안에 풀어낼 수 있도록 하는 알고리즘을 제시한다. 실제로 매일 사십만건 정도의 호출이 발생하는 뉴욕 택시 데이터로 검증까지한다. 저자가 제시한 알고리즘을 사용하면 차량이 1000대 일 때 30초, 2000-3000대일 때 대략 1분 안에 최적해를 구할 수 있다.

 

2019년도에 나온 TR part C 논문은 Alonso(2017) 논문과 비슷한 성능에 4배가 빠르다고 주장한다.

Simonetto, A., Monteil, J., & Gambella, C. (2019). Real-time city-scale ridesharing via linear assignment problems. 
Transportation Research Part C: Emerging Technologies, 101, 208-232.

federated optimization architecture 를 사용한다. 쉽게 설명하면 모든 연산을 서버에서 하는 기존의 방식에서 벗어나 연산의 부담을 각 device (여기서는 라이드쉐어링 드라이버의 휴대폰)가 나누어 부담해 병렬적으로 연산 함으로써 계산량을 확 줄이는 방식이다. Alonso (2017) 논문에서는 한대의 차량에 여러명의 승객을 매칭할 수 있도록 설계하느라 ILP 문제로 정의했는데, Simonetto (2019)는 오히려 이 문제를 단순화시켜 한대의 차량의 한명의 승객만 매칭될 수 있도록하고 문제를 LP로 포뮬레이션 한다. 대신 매 연산은 10-30초마다 수행되기 때문에 이미 승객을 한명 매칭한 차량이라도 그 다음번 연산에서 다른 승객과 매칭될 수 있으므로 큰 문제가 없다는것이 저자의 주장이다. 실제로 연산 속도의 차이를 표로 비교해서 보여주는데 같은 스케일의 문제 (차량 3000대 기준)를 본 알고리즘은 4-20초 가량이면 푸는데 반해 Alonso (2017) 년 논문은 60초 정도 걸린다. 

 

Shah, S., Lowalekar, M., & Varakantham, P. (2020, April). Neural Approximate Dynamic Programming for On-Demand Ride-Pooling. In 
Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 34, No. 01, pp. 507-515).

2020년도에 나온 논문은 또 다른 방식으로 Alonso(2017)의 문제를 발전시킨다. Alonso (2017)가 제안한 프레임워크가 다소 근시안적이라는 점을 극복하기 위한 논문이다. 이 논문은 마치 강화학습 프레임워크에서처럼 long-term 값을 학습시킨다는 점에서 가장 다르다. 가능한 차량-승객 매칭 짝이 나오면 이것을 Neural network 구조에 넣고 각각의 value function(강화학습에서 어떤 액션이 얼마나 좋았는지를 평가하는 것) 을 구한다. 이후 최적해를 기반으로 value function을 업데이트 한다. 실제로 하루 동안의 시뮬레이션 결과를 살펴보면 시간이 지날수록 매칭률이 높아지는 것을 볼 수 있었다.