기술 요약: 커넥티드 자율주행 차량(CAV) 플릿의 무작위 라우팅 전략

문제 정의

본 논문은 도시의 커넥티드 자율주행 차량(CAV) 운영을 위한 공정하고 효율적이며 경쟁적인 시장 구조를 설계하는 과제를 다룹니다. 모든 운전자가 독립적으로 주행하거나(HDV) 경쟁하는 플릿 운영자에 의해 자율적으로 경로가 지정되는 차량을 소유하게 될 미래 시나리오에서, 저자들은 시장 인센티브를 도시의 목표와 어떻게 일치시킬 것인지 조사합니다.

연구된 특정 시장 변형은 플릿 운영자가 구독료나 직접적인 사용자 결제를 통해 수익을 얻는 대신, 시장 점유율(사용자 수)에 비례하는 교통세를 통해 집단적으로 보상받는 "수수료 없는(fee-free)" 모델을 가정합니다. 핵심 문제는 플릿 운영자가 시장 점유율을 극대화하기 위해 어떤 라우팅 알고리즘을 채택할 것인지, 그리고 이러한 전략이 사회적 후생(시스템 전체의 통행 시간 최소화)과 일치하는지 여부를 결정하는 것입니다. 저자들은 다양한 운전자 태도가 존재하는 경쟁 환경에서, 운영자들이 시장 점유율을 높이기 위해 사회에 반하는(antisocial) 전략, 즉 시스템 효율성과 독립 운전자의 예측 가능성을 희생시키는 "무작위 라우팅(randomized routing)"을 채택할 수 있다고 가설을 세웁니다.

방법론

시스템 역학 및 시뮬레이션 프레임워크

저자들은 $N_D$명의 운전자와 $N_{FLEET}$개의 운영자가 참여하는 게임을 정해진 기간 동안 시뮬레이션하는 벤치마크 프레임워크를 제안합니다. 시스템은 평행한 경로를 가진 하나의 기점-종점(OD) 쌍으로 구성됩니다. 일일 역학은 다음과 같이 순차적으로 진행됩니다:

1. 오퍼(Offers): 각 플릿 운영자 $f$는 특정 알고리즘에 기반하여 모든 운전자 $i$에 대해 여행 시간 오퍼 벡터 $O_{i,j}^f$를 생성합니다.
2. 모드 선택(Mode Choice): 운전자는 과거의 주행 경험, 현재의 오퍼, 그리고 특정 플릿에 대한 태도를 나타내는 개인적 "할인 계수($\gamma$)"를 바탕으로 독립 주행(HDV)을 유지할지 또는 특정 플릿에 합류할지 결정합니다.
3. 라우팅(Routing): 운전자가 모드를 결정하면, 플릿은 구성원들을 라우팅합니다. 독립 운전자는 불쾌도(disutility)를 최소화하는 로그 모델(logit model)에 따라 경로를 선택합니다.
4. 시뮬레이션: 경로의 혼잡도에 따른 경로 여행 시간을 계산하기 위해 BPR 함수를 사용하여 하루의 주행을 시뮬레이션합니다.
5. 신뢰도 업데이트(Credibility Update): 플릿의 신뢰도는 제공된 여행 시간과 실제 경험한 여행 시간의 비율을 바탕으로 업데이트됩니다.

인간 행동 모델링

운전자는 CAV에 대해 이질적인 태도를 가진 것으로 모델링됩니다. 각 운전자 $i$는 AV에 대한 일반적인 선호도와 플릿별 구성 요소로 분해되는 할인 계수 $\gamma_{i}^{F,f}$를 가집니다. 이러한 계수들은 가우시안 분포에서 추출됩니다. 운전자는 제공된 여행 시간, 할인 계수, 그리고 플릿의 신뢰도의 함수인 불쾌도를 최소화하는 모드(HDV 또는 특정 플릿)를 선택합니다. 독립 운전자는 파라미터 $\beta=0.2$인 로그 모델을 사용하여 확률적으로 경로를 선택합니다.

라우팅 알고리즘

본 논문은 플릿 운영자를 위한 네 가지 주요 알고리즘 전략을 도입하고 비교합니다:

1. 비례 SO (System Optimum, 시스템 최적): 시스템 최적 흐름을 달성하도록 운전자를 라우팅하며, 평균 SO 여행 시간을 제공합니다. 이는 최적 흐름에 비례하여 운전자를 나누기 위해 무작위 순번제(random turn-taking)를 사용합니다.
2. 비례 UE (User Equilibrium, 사용자 평형): 사용자 평형 흐름을 달성하도록 운전자를 라우팅합니다.
3. RFlexV (Randomized Flexibility - Version): 불확실성을 도입하여 시장 점유율을 극대화하도록 설계된 휴리스틱입니다. 이는 독립 운전자가 가장 빠른 경로를 예측하기 어렵게 만들기 위해 의도적으로 경로 할당을 무작위화하며, 이를 통해 그들이 플릿으로 전환하도록 유도합니다. 이는 현재 구성원을 만족시키는 것을 우선시하면서 잠재적 이탈자의 "불만"을 극대화합니다.
4. RFlex (Randomized Flexibility): RFlexV의 확장판으로, 고객을 유지하면서 효율성 손실을 최소화하기 위해 운전자가 만족을 유지하기 위해 더 빠른 경로에 머물러야 하는 최소 점유 시간을 적응적으로 계산하여 할당을 최적화합니다.

연구는 또한 플릿이 초기 사용자를 끌어들이기 위해 비현리적으로 짧은 여행 시간(예: $0.5 \times$ SO 시간)을 제공하는 변형 모델도 테스트합니다.

주요 기여

1. 벤치마크 프레임워크: 저자들은 수익이 시장 점유율과 연계된 경쟁적인 CAV 시장에서 라우팅 알고리즘을 비교하기 위한 동적 시뮬레이션 프레임워크를 도입합니다.
2. 무작위성의 우월성 입증: 본 논문은 실험을 통해 무작위 라우팅 알고리즘(RFlexV 및 RFlex)이 비무작위 베이스라인 알고리즘(SO 및 UE)보다, 특히 운전자의 태도가 다양할 때 시장 점유율 확보 측면에서 엄격하게 우월함을 입증합니다.
3. 사회에 반하는 균형(Antisocial Equilibria) 식별: 본 연구는 무작위 전략이 "죄수의 딜레마" 시나리오를 생성함을 밝힙니다. 즉, 한 플릿이 무작위화를 채택하면 다른 플릿들도 경쟁력을 유지하기 위해 이를 따라야 하며, 이는 시스템 전체의 여행 시간 증가와 변동성을 초래합니다.
4. 시장 설계 제안: 저자들은 시장 점유율 극대화와 시스템 전체의 평균 여행 시간 최소화를 결합한 수정된 플릿 운영자 목적 함수를 제안합니다. 저자들은 목적 함수에 여행 시간 패널티(파라미터 $\mu$)를 추가함으로써, 경쟁을 제거하지 않으면서도 무작위 전략을 억제하고 시장을 사회적 후생 지향적 협력으로 유도할 수 있음을 보여줍니다.

결과

• 시장 점유율 vs. 효율성: 유일한 목적이 시장 점유율 극대화($\mu=0$)인 시나리오에서, 무작위 알고리즘(RFlexV-, RFlex-)은 시스템 최적(SO-) 알고리즘보다 성능이 뛰어납니다. 이들은 독립 주행을 유지하거나 다른 플릿을 선택하려는 운전자들, 심지어 높은 할인 계수(AV에 대한 회의론)를 가진 운전자들까지 성공적으로 유인합니다.
• 시스템 불안정성: 무작위 전략의 채택은 여행 시간의 상당한 변동과 시스템 전체 평균 여행 시간의 증가를 초래합니다. 두 플릿이 무작위 전략을 사용하여 경쟁할 때, 시스템은 SO 라우팅의 안정성에 비해 높은 분산을 보입니다.
• 경쟁 역학: 한 플립이 무작위 알고리즘을 사용하면, 표준 SO 알고리즘을 사용하는 경쟁자는 경쟁력을 잃고 생존을 위해 무작위 전략으로 전환해야 합니다.
• 목적 함수의 영향: 목적 함수가 여행 시간 증가에 대한 패널티를 포함하도록 수정될 때( $\mu$ 증가), 무작위 알고리즘의 성능은 저하됩니다. $\mu \approx 0.5$에서 SO 기반 알고리즘이 다시 경쟁력을 갖게 되며, 무작위적이고 사회에 반하는 전략을 사용할 유인이 제거됩니다. 시스템은 더 낮은 여행 시간 분산과 더 나은 사회적 후생을 갖는 상태로 수렴합니다.

의의 및 주장

본 논문은 집단적으로 라우팅되는 CAV 플릿의 신흥 시장에 대한 기초적인 분석을 제공한다고 주장합니다. 주요 의의는 시장 점유율 기반의 보상 체계만으로는 운영자가 운영자에게는 효율적이지만 도시 전체의 교통 흐름에는 해로운 무작위 라우팅 전략을 채택하도록 만드는 인센티브를 생성한다는 점을 식별한 데 있습니다.

저자들은 현재의 가정하에서 무작위 라우팅은 시장 경쟁에 대한 합리적인 대응이지만, 도시의 목표와는 일치하지 않는다고 주장합니다. 저자들은 도시 당국이 시스템 전체의 여행 시간을 기준으로 하는 구성 요소를 포함하여 보상 체계를 조정함으로써 이 시장을 형성할 수 있다고 제안합니다. 이러한 조정은 경쟁적인 시장의 특성을 파괴하지 않으면서도 사회적 후생 지향적 협력을 이끌어내고 사회에 반하는 전략을 제한하는 데 충분하다고 주장됩니다.

논문은 본 연구의 결과가 단순화된 벤치마크(두 개의 경로, 알려진 할인 계수)에 기반하고 있으며, 향후 연구에서는 더 복적인 시나리오, 머신 러닝 기반 알고리즘, 그리고 현실적인 도시 규모의 시뮬레이션(예: SUMO)이 포함될 것임을 언급하며 겸허하게 결론을 맺습니다.