[저널 클럽] Multimodal system optimization

어떤 교통 수단의 최적화 문제를 풀던간에 일반적으로 3 종류의 agent 가 개입된다. 특히 여러 교통 수단들이 모두 포함된 MaaS 시스템에서는 각 agent 간의 상충되는 목표 (objective)를 고려해 모델링 하는 것이 중요한 연구 주제이다. 혹은 한가지 agent 의 관점 (perspective)을 택해 문제를 정의해내기도 한다. 

• 첫째는 개인 통행자. 이들은 개인의 효용을 최대화 하기 위한 경로/ 수단 선택을 하며 전체 효용을 생각하지 않기때문에 selfish 하다고 표현한다. 
• 둘째는 각 교통 수단의 운영 주체. subsystem 이라고도 종종 표현하는데 public transit agency 가 아닌 일반적인 private company 라면 profit maximization 하는 것이 목표이다. 
• 셋째는 정부이다. 이들은 social welfare/benefit 을 최대화 하고자 하며 incentive, tax 등의 정책으로 개인과 회사들을 컨트롤하고자 한다. 

 

모델링 관점에서 생각해보자면 개인 통행자의 수단 선택을 다루기 위해서는 discrete choice model을 사용한다. 이에 더해 두가지 서로 다른 위계의 mathematical programming 문제를 생각해볼 수 있다. 첫째는 profit maximization 을 위해 pricing, assignment, rebalancing 등을 결정하는 운영자, 둘째는 social welfare maximization 을 위해 incentive, tax등을 결정하는 정부이다. 이렇듯 여러 agent가 개입된 문제를 풀면 문제가 복잡해지기 때문에 exact method 를 사용하여 analytical solution을 구하기 어려워진다. 하지만 analytical approach 를 취하고 있는 귀한 논문들이 몇개 있다ㅎㅎ. 본 포스팅은 그런 논문들을 다룬다. 

 

Wischik, D. (2018, October). The price of choice: models, paradoxes, and inference for ‘mobility as a service’. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (pp. 604-610). IEEE.

 

이 논문은 개인의 selfish 한 선택 (consumer choice)을 고려했을때 profit maximization/system welfare maximization 을 위해 ridesharing company 들이 어떻게 가격정책을 수립할 수 있는지에 대한 최적화 문제를 푼다. 본 논문은 개인들은 자기 자신의 utility 를 최대화 하려고 하고 ride sharing 회사는 본인들의 이익을 최대화 할 수 있는 방향으로 가격을 동적으로 조정했을 때 그것이 사실상 system welfare maximization 과 일치함을 증명한다. 이 특정한 세팅하에서 이것이 성립하는 이유는 본 모델이 ridesharing, transit 옵션 각각 한개씩 단 두개의 수단만 포함하고 있고 ride sharing 회사들간의 competition을 반영하지 않고있기 때문인 듯 하다. 

위 노트에는 생략되어있지만 회사의 profit을 최대화하는 alpha 를 찾는 목적함수 식과 alpha 를 price 로 표현해낸 식 (1) 에서 역으로 해당하는 price 를 읽어내는 방식으로 price 를 결정할 수 있다. 일단 dynamic price 를 결정하고 나면 식 (2) 는 convex function 이다. 따라서 expected utility 를 최대화하는 alpha 를 구하는 건 trivial 하다.  이 두 식을 jointly solve 하면 이는 welfare maximization 과 일치한다고 논문은 증명하며, 여기까지가 본 논문의 핵심 내용이다. 

 

이 논문을 읽고 드는 자연스러운 의문은 더 많은 수단을 포함하게끔 일반화할 수 없을까? 하는 것이다. 여기서 주의할 점은 MNL은 IIA 가정을 하고 있기 때문에 대안간 독립성이 위배되는 수단을 포함하게 되면 이 가정에 위배되는 문제가 생길 수 있다. 나는 이 MNL 모델을 IIA 가정을 하고 있지 않은 다른 모델로 일반화 하는 방안을 생각해보려고 한다. 일반화 시 주의할 점은 식 1 의 두가지 조건이 필요하는 점이다.

• alpha(price) 함수가 1대 1 대응으로 invertible 해야한다. 
• global optimal을 찾기 위해 alpha 함수가 convex 여야한다. 

 

Basciftci, B., & Van Hentenryck, P. (2020, September). Bilevel optimization for on-demand multimodal transit systems. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research(pp. 52-68). Springer, Cham.

 

본 논문에서 다루고 있는 상황은 다음과 같다. 정류장 노드들로 구성된 기존의 대중교통 (여기서는 특히 버스) 네트워크가 주어졌다고 하자. 정류장 중 수요가 많은 곳 일부를 hub 로 설정해서 그 구간은 버스가 더욱 자주 다닐 수 있도록 하고 나머지 구간은 on-demand shuttle 로 대체해서 운영하려는 계획을 수립했다. 운영자 관점에서 투자 비용과 운영 비용 (여기서의 운영 비용은 이용자들의 비효용을 포함한 개념)을 최소화할 수 있도록 어떤 정류장을 hub로 설정하고 그 허브들을 어떻게 연결할지 결정해야한다. 이때 사람들의 경로 선택을 반영해야하는데 사람들은 본인의 통행 비용을 최소화 할 수 있는 선택을 할 것이다. 이렇게 서로 다른 위계의 결정을 한 모델에서 풀기 위한 bilevel optimization 방법을 본 논문은 제시하며 다음과 같이 포뮬레이션하고 benders decompositon 을 이용해 해를 구한다. 

 

Benders decomposition 에 대한 확실한 이해를 바탕으로 논문을 읽기 시작하면 훨씬 더 이해하기가 쉽다.

https://youngseokim.tistory.com/121

Benders decomposition

 

Bertsimas, D., Sian Ng, Y., & Yan, J. (2020). Joint Frequency-Setting and Pricing Optimization on Multimodal Transit Networks at Scale. Transportation Science, 54(3), 839-853.

본 연구는 multimodal network 의 시스템전체 대기 시간을 최소화 할 수 있는 포뮬레이션을 제시한다. 이 연구에서는 ridesharing 등 신 교통수단과 대중교통을 결합한 네트워크를 다루는 것은 아니고, 순수하게 버스, 지하철, 철도 등 대중교통 수단으로만 구성된 문제를 다룬다. 

본 포물레이션의 결정변수는 교통 수단의 frequency 와 price 이며 다음의 것들을 고려한다.

• 운영자의 예산 제약
• 용량 제약
• multimodal route choice 에서의 승객의 선호

나아가 도시 규모 네스워크에서 수 분 안에 near-optimal 해를 찾아낼 수 있음을 보인다. 

 

Luo, Qi, Samitha Samaranayake, and Siddhartha Banerjee. "Multimodal mobility systems: joint optimization of transit network design and pricing." Proceedings of the ACM/IEEE 12th International Conference on Cyber-Physical Systems. 2021.

본 논문은 다음 세개를 모두 결정할 수 있는 MILP를 제안한다. 

• 대중교통의 frequency 
• MoD service의 flows (assignment, rebalancing)
• 각 trip의 가격

본 논문은 scalable 한 framework (scalable 하다는 것은 현실 규모의 네트워크 문제로 확장 가능하다는 것을 뜻한다) 을 제시한 첫번째 논문임이 핵심 컨트리뷰션이라고 주장한다. 연산시간을 줄이기 위해 approximation algorithm, benders decomposition, cutting-plane approach 등을 사용하며 원래 MILP에 비교해서 연산시간을 60% 가까이 줄일 수 있음을 보여준다.