INFORMS 2022 세션에서 배운 것 정리

 

 

 

Optimizing Lane Reversal Using a Global Optimization Approach

piecewise affline approximation 을 이용해서 convex optimization 으로 변환한게 인상깊었다. 이 발표자가 여러 접근법중에 왜 convex approximation 이 가장 흥미롭다고 말했는지 살펴볼 예정. 워낙 결과 표나 그래프가 좋아서 어떻게 서술했는지 살펴보는것도 도움이 될 것 같았다. 

https://www.sciencedirect.com/science/article/pii/S0968090X22002595

Optimizing lane reversals in transportation networks to reduce traffic congestion: A global optimization approach

 

Effects of Task-based incentives on Labor Supply in Ride-sourcing Market

Dynamic Discrete Choice Model 을 구축해 15분 간격으로 드라이버의 선택을 (승객을 태울 것인지, 그만 일할 것인지 등) 모델링 한게 인상적이었다. stochatic dynamic programming 에 해당됨. 제대로된 아직 퍼블리케이션은 찾을 수 없어서 향후 팔로업 할 예정. 

 

 

Dynamic On-Demand Crowdshipping using DQN

state, action space 정의하는건 비슷했다. indicator based reward 랑 실제 reward 중에 전자가 더 낫다고 언급해서 흥미로웠다. 

 

https://reader.elsevier.com/reader/sd/pii/S1366554522002678?token=A6EF0AF0F3B00DE19C6545972FCD17F6A5D85E2FC86474575D0E203C7B368408A7A9B6A1585F55902AB464AB2D0A5D9A&originRegion=us-east-1&originCreation=20221018220212 

Elsevier Enhanced Reader

 

Sparse Graph Design for Middle-mile Transportation Management

아마존 middle-mile 물류문제에서 트럭이 한 노드로만 가는 dedicated shipping 형태가 현재 사용되는 방식이다. 다른 node 를 거치는 indirect shipping 방식으로 현 상태를 개선할 수 있다. 문제를 아주 단순화 시켜 간단하게 수요를 binary (high and low) 로 표현한다. low demand node 의 경우에는 두 노드를 하나로 묶어 한 트럭이 두 노드를 배송할 수 있는데, 따라서 이를 graph matching 문제로 볼 수 있다. 이때 graph sparsify 테크닉이 쓰이는데 본 논문에서는 sparse graph 의 매칭 효율의 lower bound 도 구했다.

증명 스케치: isolate 된 어떤 노드를 생각해보자. low demand 임에도 isolate 되려면 주변이 모두 high demand 여야한다. 그러한 확률을 구하면 pq^n 이다. 이제 그러한 노드의 개수를 구하면 nd 이다. 그 후 Jensen's 를 적용하면 lower bound 를 구할 수 있다. 

https://scholar.google.com/citations?view_op=view_citation&hl=en&user=HCHLK5wAAAAJ&sortby=pubdate&citation_for_view=HCHLK5wAAAAJ:Y5dfb0dijaUC 

Designing Sparse Graphs for Stochastic Matching with an Application to Middle-Mile Transportation Management

 

The Benefits of Delay to Online Decision-Making

Online decision making 문제에서 decision delay 는 항상 중요하다. 예를들어 우버가 승객을 차량과 매칭할때 배치 간격을 늘리면 더 좋은 매칭 조합을 찾을 수 있게 되는 반면 승객이 더 오래 기다리게 된다는 단점이 있어서 그 tradeoff 를 잘 살펴야한다. 본 논문은 그 이득을 이론적으로 characterize 한다. 증명의 핵심은 우리가 기존의 LP 문제를 K 만큼 예측한 값으로 풀던걸 K 만큼 delay해서 realize 한 값으로 풀 수 있다는 것에서 출발한다. regret ratio 는 offline 문제 대비 떨어진 성능을 의미한다. 

K 를 늘리는 것은 내 논문에서 rolling horizon factor 를 증가시키는 것에 대응되는데 regret ratio 가 떨어지는게 내 그래프의 형태와 비슷해서 흥미로웠다. 항상 theoretical background 를 찾고 있었는데 그걸 제공해줄 수 있을듯.

https://faculty.chicagobooth.edu/linwei-xin/research

Research