🌈 쏘카 예약을 효율적으로 - 수학적 모델링을 활용한 쏘카 예약 테트리스 🎁 이 글을 추천하는 이유 - 산업공학 전공에서 배우는 선형 최적화, 비선형 최적화, Integer Programming에 대해 아시나요? - 저도 경영과학 시간에 이런 과목을 배웠는데, 그 당시엔 이해했으나 실무에서 어떻게 사용할지 너무 상상하기 어려웠어요 - 쏘카에선 이런 방법을 사용해 예약 효율을 개선하는 프로젝트를 진행했어요 - 데이터 기반 문제 해결에 데이터 분석, 머신러닝/딥러닝 등만 있다고 생각하는 경우가 있는데, 최적화 이론에서 나오는 방법을 사용할 수 있다는 부분을 공유하고 싶어 팀원분과 글을 작성했습니다 - 이 최적화 프로젝트를 어떻게 배포했는지도 담았습니다. 병렬처리를 위해 Ray를 사용하고, GCP Pub/Sub, Dataflow, CPU 224 Core 선점형 인스턴스 등을 사용한 내용도 있으니 데이터 엔지니어분들도 재미있게 읽을 수 있을거에요 👍 읽으면 좋은 분 - 모빌리티, 물류, 배달 산업에서 일하고 계신 분(이 분야가 최적화와 잘 맞아요) - 최적화 문제가 어떤 방식으로 해결되는지 궁금하신 분 - 쏘카 데이터비즈니스 본부의 업무 방식이 궁금하신 분 - 최적화 문제를 배포하는 데이터 엔지니어링 과정이 궁금하신 분 📋 목차 1. 예약 테트리스 프로젝트 소개 - 1.1 프로젝트 이름의 유래 - 1.2 예약 테트리스의 목적 2. 예약 테트리스 최적화 모델링 - 2.1 최적화 문제(Optimization Problem)의 접근법 - 2.2 정수 계획법(Integer Programming) - 2.3 최적화 지표 정의하기 : 어떤 상태가 더 ‘최적’일까? - 2.4 최적화 모델 정의하기 - 2.5 최적화 모델 구현하기 : Google OR-Tools 3. 예약 테트리스 모델 배포 - 3.1 최적화 서버 & 병렬 처리 - 3.2 쏘카 서비스 서버와 최적화 서버의 데이터 프로토콜 4. 예약 테트리스 적용 성과 5. 마무리 --- 최적화 문제(Optimization Problem) : 어떤 목적 함수(Objective Function)의 함숫값을 최대화 또는 최소화하는 변수의 해 값을 찾는 유형의 문제 최적화 문제의 해결 방식 1) 알고리즘 1-1) 문제에 맞춤인 알고리즘 개발 1-2) 휴리스틱 알고리즘 사용 2) 수학적 모델링 후 Solver 사용 각각 최적해 보장 여부, 개발의 난이도가 다르므로 취사 선택할 수 있음 정수 계획법(Integer Programming) : 선형 제약조건으로 표현된 해 공간에서 조합 최적화(Combinatorial Optimization) 문제를 푸는 최적화 기법 최적화 모델의 3요소 1) 제약조건(Contraints) - 특정 제약을 거는 조건입니다. 예를 들어 x는 0 보다 큰 값이다, -x와 y를 더하면 2보다 작다입니다. 2) 결정변수(Decision Variable) - 우리가 알고자 하는 변수인 x, y는 k 값을 결정하는 결정변수로 정의할 수 있습니다 3) 목적 함수(Objective Function) - 최대화하고자 하는 값 k는 이 문제의 목적이 되는 함수로 목적함수라고 부릅니다