utterances-bot commented 2 years ago

쏘카 예약을 효율적으로 - 수학적 모델링을 활용한 쏘카 예약 테트리스 - SOCAR Tech Blog

https://tech.socarcorp.kr/data/2022/06/10/reservation-tetris.html

hee10k commented 2 years ago

좋은 글 잘 읽었습니다 감사합니다👍

PabloKim89 commented 2 years ago

이 문제의 경우 병렬처리까지 했을 때 Run Time 시간이 얼마나 걸리나요? 그리고 혹시 상업용 LP 솔버와 Google OR Solver의 연산 속도 차이도 비교해 보셨는지 궁금합니다.

socar-kyle commented 2 years ago

@hee10k 안녕하세요! 좋은 글이라고 해주셔서 감사합니다!! :)

socar-kyle commented 2 years ago

@PabloKim89

안녕하세요! 좋은 질문해주셔서 감사합니다!

이 문제는 본문엔 작성하지 않았지만 내부적으로 내륙 지역과 제주 지역으로 나뉘게 됩니다. 내륙 지역은 대부분 1초 안에 문제가 풀리며, 제주 지역은 차량과 예약, 예약 가능한 일자가 제일 많아서 짧으면 1분 길면 5분 이상이 걸리게 됩니다. 저흰 이런 경우에 꼭 Optimal을 찾지 않고, Feasible이여도 채택하는 방식으로 진행했습니다. 시간과 정확도의 Tradeoff라고 볼 수 있는데, 최적화하는 Max 시간 Limit을 두고 진행했습니다. Ray에서 병렬처리 할 때도 내륙 지역과 제주 지역을 구분해서 연산되도록 진행했습니다(최적화할 때 제주 지역만 연산이 되면 병목이 생길 수 있으므로)

상업용 LP 솔버도 검토해보았으나, 회사에서 상업용 LP 솔버를 구입해서 운영하기엔 비용적으로 어려울 것이라 판단해(비용이 너무 크기에) 정밀하게 속도 비교를 하진 않았습니다.

검토했던 솔버는 IBM의 CPLEX였습니다! 예전에 파이콘 19에서 최적화 관련 세션이 있었는데, 이 세션이 프로젝트할 때 큰 도움이 되었습니다. 참고하시면 좋을 것 같아 제 후기 글 공유드립니다 https://zzsza.github.io/etc/2019/08/18/pycon2019/

감사합니다 :)

socar-inc / techblog-comments

data/2022/06/10/reservation-tetris #25

쏘카 예약을 효율적으로 - 수학적 모델링을 활용한 쏘카 예약 테트리스 - SOCAR Tech Blog