This thesis addresses decision-making for networked autonomous vehicles in mobility on demand (MoD) systems. We introduce an optimization formulation, Decentralized Dial-A-Ride Problem (DDARP), that simultaneously accounts for the dispatching of vehicles in response to existing service requests and the routing vehicles for assigned requests. Additionally, we extend the D-DARP for
ride-sharing and transfer problems, Decentralized Dial-A-Ride Problem with transfer (D-DARPT). The DARP comprises optimization to assign transportation requests and planning of individual vehicle routes. In the case of self-optimizing on-demand mobility, a dispatcher does not know the exact cost of the vehicle to perform each request. So we decompose DARP into D-DARP with sub-problems of decision-makers in the decentralized AMoD system. We develop an alternating direction method of multipliers (ADMM) based decomposition method to solve this optimization problem in a distributed manner effectively. The ADMM-based framework enables (i) decomposing the DARP into a dispatching problem and vehicle sub-problems with a subset of assigning decisions based on an ADMM; and (ii) optimizing individual vehicles to ensure the convergence to the feasible solution of the global system by an individual heuristic algorithm. The coordination algorithm is based on a variable neighborhood search and adaptive penalty selection strategy, accelerating the ADMM considering the binary decision. Numerical examples demonstrate the efficacy and the benefits of the optimization model in the context of real-world autonomous mobility-on-demand systems. Additionally, these optimization algorithms provide a hierarchical solution
structure that aids in solving the autonomous mobility-on-demand system decision-making problems.
본 학위 논문에서는 주문형 자율주행 교통 시스템 (Autonomous Mobility-On-Demand, AMoD) 의 차량 경로 계획 및 차량 재배치 계획을 위한 의사결정 문제를 다룬다. 주문형 교통 시스템의 자율 운용을 위해서는 주어진 사용자 요청에 대해 차량을 할당하고, 각 차량은 할당된 승객을 이송하기 위한 차량경로를 계획할 필요가 있다. 고도화된 각 자율주행 차량의 의사 결정이 분산화 되어 있을때, 전체 시스템의 효율적인 운영을 위해 할당 시스템은 분산된 차량의 의사결정을 협의하여 배차를 결정하여야 한다. 이러한 문제를 해결하기 위해 분산된 배차 및 차량 경로 계획 문제 (Decentralized Dial-A-Ride Problem, D-DARP) 를 제안하고, 시스템의 합승과 환승 문제로 확장하여 도심 항공 시스템(Urban Air Mobility, UAM)과 결합한 주문형 자율 주행 교통 시스템을 제안한다 (Decentralized Dial-A-Ride Problem with Transfer, D-DARPT). 더불어, 본 문제를 개별 차량 단위의 분산화된 시스템에 적용하기 위해 Alternating Direction Method of Multipliers (ADMM) 기법을 적용하고 이를 기반으로 한 분산 휴리스틱 기법을 제안한다. ADMM 기반의 분산 최적화 기법은 분할된 부분 문제의 최적화와 분할된 문제의 해 사이의 조정 과정으로 구성되며, 분할 기법을 통해 배차 및 경로 계획 문제는 각 차량의 운용 비용을 최소화하고 배차로 얻는 이득을 최대화 하는 문제로 분할하여 재구성할 수 있다. 이진 결정변수를 가진 비볼록 문제에 대한 ADMM 기반 기법의 한계를 해결하기 위해, 분할 반복 연산 과정에서 분할된 문제의 계산시간을 줄이기 위한 부분 문제 휴리스틱을 제안하고, 또한 결정 조정 과정에서 전체 시스템의 합의 속도를 높이기 위한 시장 기반 라그랑지안 패널티 파라미터 결정 기법을 제안한다. 본 논문에서는 계층적 ADMM 기반 반복적 알고리즘을 활용하여 차량 배차 및 경로 계획 문제의 준 최적해를 탐색하고, 주문형 자율주행 교통 시스템 모델에 도로망 모델과 교통 수요 모델을 적용하여 제안된 확장 문제와 확장 기법들의 타당성과 효율성을 검증한다. 또한 수치적 시뮬레이션을 통해 자율 주문형 시스템의 특성을 분석하고 이를 통해 제안한 문제의 일반화된 분산 자율 교통 문제로의 확장성을 확인한다.
