수요응답형 승차 문제 (Dial-a-Ride Problem)
한 줄 정의: 여러 고객이 각자 지정한 출발지에서 목적지까지의 이동을 요청할 때, 시간창과 차량 용량, 최대 탑승시간 제약을 만족하면서 차량 경로를 최적으로 설계하는 수송 최적화 문제입니다.
쉽게 풀면
콜택시나 장애인 콜버스처럼 '나를 A에서 B로 몇 시까지 태워 달라'는 요청이 여러 건 들어올 때, 한정된 차량으로 누구를 어떤 순서로 태우고 내려 줄지 정하는 문제입니다. 사람을 실어 나르므로 짐과 달리 '너무 오래 태우고 돌아다니면 안 된다'는 승차 시간 제약이 붙는 것이 특징입니다.
왜 중요한가
고령화와 대중교통 사각지대 해소로 수요응답형 교통(DRT)이 확산되면서 핵심 계획 문제가 되었습니다. 픽업·배달 문제의 특수형이지만, 승객 편의(대기시간·우회시간)를 명시적으로 고려해야 하므로 비용 최소화와 서비스 품질 간의 균형이 연구의 중심이 됩니다.
논문에서는 이렇게 쓰입니다
"농촌 지역 수요응답형 버스 운영을 수요응답형 승차 문제(dial-a-ride problem)로 모형화하고, 최대 승차시간 제약을 포함한 혼합정수계획법으로 해를 구하였다."
시골 콜버스 운영을 이 문제로 정식화해 수학적 최적화로 풀었다는 뜻입니다.
"동적 수요응답형 승차 문제에서 실시간 요청 수락 여부를 결정하는 삽입 휴리스틱의 성능을 평가하였다."
실시간으로 들어오는 탑승 요청을 기존 경로에 끼워 넣을지 판단하는 빠른 방법을 시험했다는 의미입니다.
조금 더 깊게 보면
정적(모든 요청이 사전에 알려짐) 버전과 동적(요청이 실시간 도착) 버전으로 나뉘며, 동적 버전은 온라인 최적화와 롤링 호라이즌 기법으로 다룹니다. 정확해법으로는 분지절단법과 열생성법이, 대규모 사례에는 적응적 대규모 근방탐색(ALNS)이 주로 쓰입니다. 최근에는 전기차·자율주행 셔틀의 충전 제약이나 라이드 풀링 서비스와 결합한 확장 모형이 활발합니다.
주의할 점
픽업과 배달의 선후관계, 동일 차량 배정, 시간창, 승차시간 상한 등 제약이 많아 중소 규모에서도 정확해를 구하기 어렵습니다. 또한 비용만 최소화하면 승객 우회시간이 길어지므로 목적함수에 서비스 품질을 어떻게 반영할지 신중히 정해야 합니다.