⚡ electrical engineering

Where Should Robotaxis Operate? Strategic Network Design for Autonomous Mobility-on-Demand

이 논문은 자율주행 모빌리티 온 디맨드 (AMoD) 서비스를 위한 운영 서브네트워크와 차량 대수를 동시에 최적화하는 전략적 설계 문제를 공식화하고, 맨해튼의 실제 데이터를 기반으로 인프라 투자와 차량 운영 시간 간의 균형을 분석할 수 있는 효율적인 알고리즘을 제안합니다.

원저자: Xinling Li, Gioele Zardini

게시일 2026-02-24

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Xinling Li, Gioele Zardini

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 **"자율주행 택시 (로보택시) 가 도시에 들어오면, 과연 어디를 다니게 해야 할까?"**라는 아주 실용적이고 중요한 질문에 답합니다.

기존의 우버나 리프트 같은 택시 서비스는 사람이 운전하기 때문에, 운전자가 마음대로 어디로든 갈 수 있습니다. 하지만 로보택시는 완전히 다른 문제입니다. 안전을 위해 특정 도로만 다니게 해야 하거나, 도로에 특수한 장비 (센서 등) 를 설치해야 하기 때문입니다.

이 논문은 **"어떤 도로를 선택하고, 차를 몇 대나 준비해야 가장 돈을 잘 벌면서 시민들도 만족시킬 수 있을까?"**를 수학적으로 계산하는 방법을 제안합니다.

이 복잡한 내용을 쉽게 이해할 수 있도록 세 가지 비유로 설명해 드릴게요.

1. 비유: "새로운 레일 (궤도) 을 깔아야 하는 마법 기차"

기존 택시 (사람 운전) 는 자전거와 같습니다. 길이 있으면 어디든 갈 수 있고, 길에 구멍이 좀 나 있어도 넘어가면 됩니다.

하지만 로보택시는 고급스러운 마법 기차와 같습니다.

이 기차는 특수한 레일 (도로) 위에서만 달릴 수 있습니다.
레일을 깔려면 **돈 (인프라 예산)**이 듭니다.
기차 (차량) 도 한정되어 있고, 기름 (시간/연료) 도 한정되어 있습니다.

핵심 문제:
도시 전체에 레일을 다 깔면 돈이 너무 많이 듭니다. 반면, 레일을 너무 적게 깔면 기차가 목적지까지 못 가서 손님이 불평합니다.
이 논문은 **"최소한의 레일만 깔아서, 최대한 많은 손님을 태우고, 가장 많이 돈을 벌 수 있는 레일 지도"**를 찾아내는 방법을 알려줍니다.

2. 비유: "미로 찾기 게임과 숨겨진 길"

도시는 거대한 미로입니다. A 지점에서 B 지점으로 가는 길은 수천, 수만 가지가 있을 수 있습니다.

기존 방법: 모든 길을 다 계산하려고 하면 컴퓨터가 "오버플로우"가 나서 멈춰버립니다. (너무 많은 길!)
이 논문의 방법 (기둥 생성 알고리즘):
1. 먼저 가장 유망한 몇 개의 길만 골라봅니다.
2. 그 길들만 가지고 "어떻게 하면 가장 효율적일까?" 계산합니다.
3. 계산 결과, "아직 더 좋은 길이 숨어있을지도 몰라!"라고 생각하면, 그 길만 찾아서 추가합니다.
4. 더 이상 좋은 길이 없으면 멈춥니다.

이 방법은 모든 길을 다 보지 않아도, 정답에 가장 가까운 길만 골라내서 거대한 도시 (맨해튼) 규모에서도 순식간에 해답을 찾아냅니다. 마치 미로에서 모든 길을 다 헤매지 않고, 가장 가까운 출구만 쫓아다니는 것과 같습니다.

3. 비유: "안전한 운전 규칙 (좌회전 금지)"

자율주행차에게 가장 무서운 것은 복잡한 좌회전입니다. 차가 막히고, 신호가 꼬이고, 사고 위험이 큽니다.
이 논문은 **"좌회전 횟수를 제한하자"**는 규칙을 넣을 수도 있다고 말합니다.

결과: 좌회전을 아예 안 하거나 줄이면, 차가 조금 더 돌아가서 시간이 걸릴 수는 있지만, 사고 위험은 확실히 줄어듭니다.
이 논리는 "안전과 수익 사이의 균형"을 어떻게 잡을지 도시 계획자들에게 보여줍니다. "좌회전 100 회만 허용하면, 수익은 10% 줄지만 안전은 50% 좋아집니다"처럼 숫자로 보여줄 수 있는 것입니다.

이 연구가 우리에게 주는 메시지 (결론)

무작정 다 깔지 마세요: 도시 전체에 자율주행 도로를 다 깔 필요는 없습니다. 핵심 간선 도로만 잘 골라내면 훨씬 효율적입니다.
차량 수와 도로 공사는 동행해야 합니다: 차만 많이 사서 도로를 못 깔면 차가 막히고, 도로만 잘 깔고 차가 없으면 빈 차가 돌아다닙니다. 둘을 함께 계획해야 합니다.
날마다 변하지 않는 안정적인 지도: 하루하루 손님이 달라져도, 최적의 도로 지도는 거의 변하지 않습니다. 즉, 한 번 잘 설계하면 오랫동안 쓸 수 있다는 뜻입니다.
위험한 길은 피하세요: 좌회전 같은 위험한 maneuver(기동) 를 제한하면, 시스템이 더 안전해집니다.

한 줄 요약:

"이 논문은 자율주행 택시가 도시에 들어올 때, 어떤 도로만 골라야 돈을 가장 많이 벌면서 시민도 안전하게 태울 수 있는지를 계산해주는 최고의 설계도를 만들어냈습니다."

이 연구는 앞으로 우리가 로보택시를 타게 될 때, 그 차들이 어떻게 움직일지, 그리고 우리 도시는 어떻게 변할지 미리 예측하고 준비하는 데 큰 도움이 될 것입니다.

1. 문제 정의: AMoD-NDP (Autonomous Mobility-on-Demand Network Design Problem)

배경: 자율주행 차량 (AV) 은 인간 운전자가 아닌 중앙 운영자가 통제하므로, 전체 차량의 재배치와 경로 설정을 최적화할 수 있습니다. 하지만 AV 는 안전한 운행을 위해 특정 도로 인프라 (센서, 통신 등) 가 갖춰져야 하며, 초기에는 제한된 운영 설계 영역 (ODD) 내에서만 운행됩니다.
핵심 질문: 운영자는 제한된 인프라 예산과 차량 가용 시간 (플릿 시간) 제약 하에서, 어떤 도로 구간을 자율주행에 개방할지 (서브네트워크 선정) 와 승객을 어떻게 경로 설정할지 (수요 충족) 를 동시에 결정하여 이익을 극대화해야 합니다.
제약 조건:
- 인프라 예산: 자율주행 인프라를 구축하는 비용.
- 플릿 시간: 전체 차량이 운행할 수 있는 총 시간 (차량 대수와 직접 연관).
- 경로 수준 품질 (QoS) 및 리스크: 승객별 이동 시간 상한선, 위험한 조작 (예: 좌회전) 횟수 제한 등 경로 단위의 제약 조건.

2. 방법론 (Methodology)

A. 수학적 모델링

경로 기반 혼합 정수 선형 계획법 (Path-based MILP): 링크 (도로 구간) 기반 모델은 경로 수준의 제약 조건을 표현하기 어렵다는 한계가 있어, 승객 수요 (OD 쌍) 를 충족하는 모든 가능한 경로를 변수로 하는 모델을 제안했습니다.
목적 함수: 운영자의 기대 이익 (수익 - 변동 비용) 을 최대화합니다.
특징: 인프라 투자 비용, 차량 시간 제약, 링크 용량, 그리고 경로별 QoS/리스크 제약을 모두 포함합니다.

B. 컬럼 생성 (Column Generation, CG) 알고리즘

도시 규모의 네트워크에서 모든 가능한 경로를 나열하는 것은 계산적으로 불가능하므로 (지수적 복잡도), 컬럼 생성 기법을 사용하여 효율적으로 해결합니다.

마스터 문제 (Master Problem): 제한된 경로 집합 (Restricted Path Set) 에 대해 선형 계획법 (LP) 을 풀어 현재 최적 해와 쌍대 변수 (Dual Variables) 를 구합니다.
프라이싱 문제 (Pricing Problem): 현재 해를 개선할 수 있는 새로운 경로 (음의 감소 비용 또는 양의 이득을 주는 경로) 가 있는지 탐색합니다. 이는 자원 제약이 있는 기본 최단 경로 문제 (Elementary Shortest Path with Resource Constraints, SPRC) 로 귀결됩니다.
정확한 프라이싱 솔버:
- OD 별 전처리: 목적지까지의 최단 시간을 기준으로 실현 가능한 경로만 남기고 네트워크를 축소합니다.
- 라벨 교정 알고리즘 (Label-Correcting): A* 알고리즘의 아이디어를 활용하여, 시간 제약과 기본성 (Elementary, 순환 금지) 을 만족하는 최단 경로를 정확하게 탐색합니다.
정수 해 복원: LP 완화 해를 구한 후, 생성된 경로 집합 내에서 정수 제약 (도로 개방 여부) 을 다시 부과하여 MILP 를 풀어 최종 해를 도출합니다.

C. 강건성 (Robustness) 확장

불확실성 모델링: 이동 시간과 수요의 불확실성을 박스 (Box) 불확실성으로 가정합니다.
강건 대응: 이동 시간 불확실성은 링크별 이동 시간을 보수적으로 증가시켜 반영하고, 수요 불확실성은 수요 상한선을 낮추어 반영합니다. 이 경우에도 알고리즘의 구조 (마스터 문제와 프라이싱 문제의 분해) 는 유지되어 동일한 프레임워크로 해결 가능합니다.

3. 주요 기여 (Key Contributions)

AMoD-NDP 의 공식화: 기존 고정 네트워크 가정을 벗어날 수 있는, 인프라 설계와 차량 배치를 통합한 전략적 설계 문제를 최초로 정립했습니다.
확장 가능한 알고리즘 개발: 도시 규모의 네트워크에서도 작동하는 경로 기반 MILP 와 컬럼 생성 알고리즘을 개발했습니다. 특히, 라벨 교정 알고리즘을 통해 SPRC 를 정확하게 해결하여 최적성 간격 (Optimality Gap) 을 명시적으로 보장합니다.
리스크 및 QoS 제약 통합: 이동 시간뿐만 아니라 좌회전 횟수 제한과 같은 경로 수준의 안전/리스크 제약을 모델에 자연스럽게 통합할 수 있음을 보였습니다.
실증 분석: 뉴욕 맨해튼의 실제 데이터 (TLC 택시 데이터, OpenStreetMap) 를 사용하여 알고리즘의 확장성과 실용성을 입증했습니다.

4. 실험 결과 (Results)

데이터: 2024 년 5 월 뉴욕 맨해튼의 택시 이동 데이터 (하루 약 20 만 건) 와 도로 네트워크를 사용했습니다.
계산 효율성: 컬럼 생성 기법을 통해 변수 수를 지수적으로 줄여, 31 일간의 수요 시나리오 모두를 25 분 이내에 해결했습니다. 최적성 간격은 $10^{-6}$ 미만으로 매우 작았습니다.
서브네트워크 구조:
- 최적 운영 네트워크는 전체 도로의 일부만 선택하는 희소 (Sparse) 한 구조를 가집니다.
- 시간적 안정성: 하루 단위의 수요 변동에도 불구하고, 최적에 선정되는 주요 도로 구간 (코리도어) 은 31 일 동안 90% 이상 일관되게 유지되었습니다. 이는 인프라 계획이 단기 수요 변동에 민감하지 않음을 시사합니다.
예산 및 플릿 시간 민감도 분석:
- 플릿 제한 구간: 차량이 부족할 때는 인프라를 늘려도 이익이 크게 증가하지 않습니다.
- 예산 제한 구간: 인프라가 부족할 때는 차량을 늘려도 효과가 없습니다.
- 용량 제한 구간: 둘 다 충분하면 도로 물리적 용량이 병목이 되어 이익이 포화됩니다.
- 이는 인프라 투자와 차량 대수를 균형 있게 계획해야 함을 보여줍니다.
리스크 제약 (좌회전 제한): 좌회전 횟수를 제한하는 제약 조건을 추가했을 때, 제약이 엄격할수록 서비스 수요 충족률과 이익이 감소하지만, 일정 수준 이상 완화되면 효과가 포화되는 것을 확인했습니다. 이는 안전과 수익 간의 트레이드오프를 정량화할 수 있음을 보여줍니다.

5. 의의 및 결론

의의: 이 연구는 AMoD 서비스의 성공적인 도입을 위해 인프라 투자와 운영 전략을 통합적으로 고려해야 함을 강조합니다. 단순한 차량 제어 알고리즘을 넘어, 도시 계획자 (Municipalities) 와 운영자 (Operators) 가 인프라 예산과 차량 대수, 안전 기준을 어떻게 설정해야 하는지에 대한 의사결정 지원 도구를 제공합니다.
미래 작업: 불확실성 집합을 더 풍부하게 확장하거나, 실시간 차량 재배치 (Rebalancing) 와 동적 제어 계층을 통합한 다중 스케일 설계 프레임워크로 발전시킬 수 있습니다.

요약하자면, 이 논문은 자율주행 택시 서비스가 실제로 도시 도로망에 어떻게 통합되어야 하는지에 대한 전략적 청사진을 제시하며, 수학적 최적화 기법을 통해 인프라 비용, 차량 효율성, 안전성 사이의 최적 균형을 찾는 방법을 체계적으로 제시했습니다.