공유 이동성을 위한 통합 경로 계획: 삽입 기반 프레임워크

공유 이동 애플리케이션인 라이드 셰어링, 음식 배달, 크라우드소싱 소포 배달의 급격한 성장이 있었습니다. 공유 이동성은 사용자 간에 공유되는 운송 서비스를 의미하며, 여기서 중앙 문제는 경로 계획입니다. 일련의 작업자와 요청 세트를 고려할 때, 경로 계획은 각 작업자를 위해 경로를 찾으며, 즉, 시간에 따라 도착하는 승객/소포를 픽업하고 하차하는 위치의 순서를 최적화 목표에 따라 다르게 선정합니다. 이전 연구들은 상충하는 목표와 새로운 요청을 경로에 삽입하는 비효율성으로 인해 실용성이 부족합니다. 또한, 기존의 경로 계획 솔루션은 최적화를 위해 역사적 데이터에 숨겨진 미래 요청의 발생 패턴을 활용하지 못합니다. 본 논문에서는 URPSM이라고 불리는 경로 계획의 통합 공식을 제시합니다. 이는 이전 연구에서의 상충된 목표를 제거하고 공유 이동성을 위한 유연한 다중 목표 경로 계획을 가능하게 하는 잘 정의된 매개변수화된 목적 함수를 가지고 있습니다. 우리는 URPSM 문제를 해결하기 위해 두 가지 삽입 기반 프레임워크를 제안합니다. 첫 번째는 이전 연구들에서 널리 사용된 일반 삽입에 기반하여 온라인 요청만 처리하며, 두 번째는 온라인 및 예측 요청 모두를 처리하는 새로운 삽입 연산자 '예언자 삽입'에 의존합니다. 새로운 동적 프로그래밍 알고리즘은 두 삽입을 선형 시간으로 가속화하도록 설계되었습니다. 이론적 분석에 따르면 URPSM 문제에 대해 어떤 온라인 알고리즘도 경쟁 분석 모델 하에서 일정한 경쟁 비율을 가질 수 없지만, 우리의 예언자 삽입 기반 프레임워크는 인스턴스 최적 모델 하에서 일정한 최적 비율을 달성할 수 있습니다. 실제 데이터 세트에 대한 광범위한 실험 결과는 우리의 삽입 기반 솔루션이 효과성과 효율성 모두에서 최신 알고리즘에 비해 큰 차이로 우수하다는 것을 보여줍니다(예: 목표에서 최대 30% 더 효과적이고 최대 20% 더 빠름).