제약 조건을 포함한 최적화

[kyungheee]

우선순위

1. 일치해야 하는 정보 a. 출발지→공항 or 공항→목적지 두개 중에 어떤 걸 선택했는지! b. 출발 날짜가 같아야 함

2. 제약 조건 a. 탑승 인원 4-8명 b. 공항에 최소 도착 시간안에 도착해야 함 (공항으로 가는 경우에 적용) -> 중요 c. 조용히 가고 싶다고 체크한 사람은 그들끼리 묶어야 함 d. 동성끼리 탑승하고 싶다고 체크하면 조건 추가 e. 짐 개수 고려 -> 중요도에 따라 weight를 부여

3. 최적화 할 것 - Loss function에 어떤 것들을 고려해서 넣을건지 a. 최대한 많은 팟이 '생성' 되도록 (2-a,b,c,d,e 고려해서) b. 동시에 각 팟의 '평균 이동 시간' 이 최소가 되도록 (API 호출해서) c. 사람들의 탑승 위치를 고려했을 때 공항버스와 비교하는 건 어려울 것 같구, 승용차로 각 탑승 위치에서 공항까지 걸리는 시간과 비교했을 때 '차이' 가 최소가 되도록? d. 동시에 우리가 얻는 '수익' 이 최대화 되도록 (= 각 팟에 포함된, 즉 탑승하는 '총 승객 수' 가 최대화 되도록) -> 중요도에 따라 weight를 부여
   -> 모두 느낌은 비슷한데, 미세하게 다른 느낌이라 저렇게 나눴어용

@kcy24 추가 의견 있으시면 댓글 달아주세용

[kyungheee]

레퍼런스

1. Combinatorial Optimization and Reasoning with Graph Neural Networks https://www.ijcai.org/proceedings/2021/0595.pdf

2. Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective https://ar5iv.labs.arxiv.org/html/2404.06492

   Loss function 말고 제약 조건을 만족시켜서 나온 클러스터링 결과에 따라 reward를 주는 방식으로 RL을 적용해도 재밌을 것 같아요

3. A Survey of Intelligent End-to-End Networking Solutions: Integrating Graph Neural Networks and Deep Reinforcement Learning Approaches https://www.mdpi.com/2079-9292/13/5/994

[kcy24]

1. 예외적으로 수요가 너무 없을 경우, 한 팟에 최소 도착 시간이 너무 다양한 사람들끼리 모이면 ?
2. a의 '최대한 많은 팟이 생성', d의 '각 팟에 포함된 총 승객수가 최대화 되도록' => 이 두 조건이 충돌한다고 생각함