arXiv:2611.22330v1 cs.AI

차량 재배치를 위한 다단계 문맥 최적화

Multistage Contextual Optimization for Vehicle Repositioning

Jinyu Zhang, Di Huang, Zhiyuan Liu, Nikolas Geroliminis

제출 2026-11-18

한국어 초록

차량 호출 플랫폼은 이용 가능한 차량을 재배치해 지역별 수요와 공급의 균형을 맞춘다. 예측을 바탕으로 여러 단계에 걸쳐 결정하는 문제다. 플랫폼은 단계마다 미래 수요를 예측하고 현재 결정을 실행한다. 그 결과 상태는 다음 단계의 초기 상태가 된다. 차량 누적량과 운행 완료량을 연결하는 거시적 기본도(MFD)를 사용해 다단계 선형 계획법(LP)으로 정식화했다. 이어 의사결정 성능으로 예측 모델을 학습시키는 다단계 문맥 최적화 방법을 개발했다. 학습 문제는 서로 얽힌 여러 단계, 이전 결정에 의존하는 문맥, LP의 목적함수·제약 행렬·우변에 영향을 주는 예측을 결합한다. 정확한 그래디언트는 세 부분으로 나뉜다. 매개변수는 예측과 그에 따른 결정을 바꾼다. 이전 결정은 다음 단계로 전달된 상태를 통해 현재 결정에 영향을 준다. 이 상태는 문맥으로도 쓰여 예측을 바꾼다. 동등한 수반 형식은 역방향 벡터–야코비안 곱을 사용해 해와 상태의 매개변수에 대한 전체 야코비안을 계산하지 않는다. 순전파에서 단계별 LP를 차례로 많이 풀어야 해 학습 속도가 느리다. 연속 단계의 블록을 병렬로 풀고 각 블록 출력을 다음 블록에 반복적으로 전달하는 병렬 블록 평가 알고리즘을 제안한다. 유한한 횟수의 반복으로 순차 궤적을 복원하며, 일찍 멈춰도 그래디언트 오차가 유계임을 증명한다. 뉴욕시 차량 호출 데이터에서 평균제곱오차로 학습한 동일 예측기보다 사업상 이득을 7.7~9.1% 더 얻었다. 다섯 접근법의 모든 비교 기준선을 앞섰고, 실현된 수요를 같은 정책에 입력한 경우보다도 우수했다. 워커 여덟 개로 병렬 블록 평가를 수행하면 의사결정 성능 저하 없이 학습 시간이 기존의 1.86분의 1로 줄었다.

원문 초록

Ride-hailing platforms reposition idle vehicles to improve spatial supply-demand balances. This problem is prediction-driven and multistage: at each stage, the platform forecasts future demand, executes current decisions, and uses the resulting state to initialize the next stage. We formulate a multistage linear program (LP) with a macroscopic fundamental diagram (MFD) linking accumulation to trip completion. We then develop a multistage contextual optimization approach that uses decision performance to train the prediction model. The learning problem combines multiple coupled stages, context that depends on earlier decisions, and predictions that affect the objective, the constraint matrix, and the right-hand side of the LP. We derive the exact gradient, which has three parts: parameters change forecasts and hence decisions; earlier decisions change the current decision through the inherited state; and this state also changes forecasts as context. An equivalent adjoint uses reverse vector-Jacobian products, avoiding full solution and state-parameter Jacobians. Finally, forward propagation solves many stage LPs one after another, which makes training slow. We propose a parallel block evaluation algorithm that solves blocks of consecutive stages in parallel and repeatedly feeds each block output to the next block. We prove that the algorithm recovers the serial trajectory within a finite number of passes and that its gradient error remains bounded when it stops early. On New York City ride-hailing data, multistage contextual optimization yields 7.7% to 9.1% more business benefit than the same predictor trained by mean squared error, outperforms all compared baselines from five paradigms, and even outperforms realized demand fed to the same policy. With eight workers, parallel block evaluation shortens training by a factor of 1.86 without loss of decision performance.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.22330v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.