석박사 (62) 썸네일형 리스트형 [Gurobi] big-M constraint 가 일으킬 수 있는 문제 big-M constraint 은 gurobi 를 포함한 많은 최적화 솔버에서 해의 불안정성 (instability) 문제를 일으킨다. 우선 아래 예시를 통해 big-M constraint 가 무엇인지부터 살펴보자. y는 도로를 사용할지 말지 결정하는 binary variable 이고 10^6은 도로의 용량을 나타내며 x는 차량의 통행량이라고 해보자. 첫번째 수식을 살펴보면 y=0이면 x ILP 문제를 푸는 exact method (cutting plane, branch-and-bound, branch-and-cut) ILP in practice ILP는 np hard 이기 때문에 이론적으로 optimal solution 을 구할 수 있을 것이라 기대할 수 없다. 하지만 현실에서 많은 경우 ILP 솔버가 최적해를 준다. 이는 ILP 의 정확해를 찾아주는 Exact algorithm 이 많이 발전했기 때문이다. 아주 나이브하게 생각해보면 ILP 를 풀기 위한 첫걸음으로 LP relaxation 을 생각해볼 수 있다. 쉽게말해 변수가 integer 라는 제약만 없애고 LP 문제를 푸는것이다. 당연히 얻은 결과는 정수가 아니라 실수일 수 있다. 이를 정수해로 변환하기 위해 반올림을 하면 어떨까? 이렇게 구한 해는 최적해가 아닐 수 있을 뿐더러 심지어는 feasible 한 해가 아닐 수도 있다. 우리에게는 반올림 보다는 조금.. [영어미팅] 줌 미팅중 먼저 나갈때 채팅창에 쓸수있는 말 줌미팅중 먼저 나가야할때가 종종 있다. 첨엔 뭐라고 말할지 몰라서 사람들은 어떻게하나 관찰했는데 다들 채팅창에 아래 중 하나를 투척하고 나감. 다들 많이 쓰는말들만 복사해놨당 I have to run; thank you! GTG(got to go의 줄임말). Thanks all! Have to head off to another meeting — thanks! Hi All - I need to drop off to deal with something right now. See you all next week. TSP 연구에 사용할만한 솔버와 예제 문제 TSP란? TSP 는 np hard 문제이다. 다항 시간 내에 최적해를 찾을 수 없는 문제의 특성때문에 사이즈가 큰 instance 의 경우 아직도 최적해를 찾아나가고 있는 중이며 현재까지 찾은 해중 가장 좋은 해를 best known solution 이라 명명한다 TSPLIB 유명한 instance 들은 아래에서 찾아볼 수 있다. 만일 누군가 TSP 문제를 더 효율적으로 풀기 위한 heuristic 을 개발했다고 해보자. 그 성능 (얼마나 빨리 더 좋은 해를 찾나) 을 기존에 제시된 알고리즘과 비교하기위해 특수한 instance 가 아니라 잘 알려진 instance 에 적용해보고 싶을 수 있다. 그럴때 사용할수 있는 것이 TSPLIB 이다. http://comopt.ifi.uni-heidelberg.d.. [최적화 솔버] Google ortools 와 GUROBI index.php/en/ https://w1.cirrelt.ca/~vidalt/en/VRP-resources.html 기존에 최적화 문제를 풀기 위해서 ortools 를 많이 써왔었는데 GUROBI 라는 최적화 솔버를 발견했다. 현존하는 솔버중에 가장 성능이 좋다고 평가되며 당연히 open source인 ortools 보다 성능이 뛰어나다. 튜토리얼도 상세하고 예제 코드도 많아 google ortools 를 이용할 정도의 실력이라면 무리 없이 사용할 수 있다. 학생이라면 아카데믹 라이센스를 신청해서 무료로 사용할 수 있다. https://www.gurobi.com/resource/modeling-examples-using-the-gurobi-python-api-in-jupyter-notebook/ Gur.. demand-responsive transit (DRT) 란? demand-responsive transit (DRT) service 도시 대중교통의 서비스 수준을 높이기 위해 도입된다. 다음과 같은 것들이 DRT에 포함된다. customized (or subscription) bus (CB) shuttle bus feeder bus on-demand shared mobility service 가장 유동적이며 개인화된 서비스인 택시와 대중교통의 중간정도 성격을 지녔다. 이 중 특히 customized bus는 다음의 특정 통행자 집단에게 서비스하려는 성격이 강하며 기존의 자가용과 대중교통을 보완해주는 기능을 하는 효율적인 녹색 교통 수단으로 평가된다. 정기적 통근자 교통 약자 대중교통 접근성이 좋지 못한 지역의 사람들 이에 반해 paratransit 은 준대중교통이.. [논문이 나왔습니다] 토픽: Mobility as a Service, 방법론: Discrete choice analysis Mobility-as-a-Service (MaaS) 토픽을 주제로 연구하시려는 분, Discrete choice modeling 방법론을 새롭게 배우시려는 분께 도움이 될까해서 공유합니다. 아래 논문은 대한교통학회지에 발간한 2020년 논문입니다. 서울시 통근자의 수단선택에 초점을 맞추어 연구했습니다. Nested logit 모델을 사용했고, 설문조사 설계에 대한 보다 자세한 내용을 담았습니다. https://www.dbpia.co.kr/Journal/articleDetail?nodeId=NODE09872020 서울시 Mobility-as-a-Service 시스템에서의 통근자 교통 대안 선택 모형 구축 논문, 학술저널 검색 플랫폼 서비스 www.dbpia.co.kr 국내 학술지에 게재된 연구를 모델링 측.. [저널 클럽] Multimodal system optimization 어떤 교통 수단의 최적화 문제를 풀던간에 일반적으로 3 종류의 agent 가 개입된다. 특히 여러 교통 수단들이 모두 포함된 MaaS 시스템에서는 각 agent 간의 상충되는 목표 (objective)를 고려해 모델링 하는 것이 중요한 연구 주제이다. 혹은 한가지 agent 의 관점 (perspective)을 택해 문제를 정의해내기도 한다. 첫째는 개인 통행자. 이들은 개인의 효용을 최대화 하기 위한 경로/ 수단 선택을 하며 전체 효용을 생각하지 않기때문에 selfish 하다고 표현한다. 둘째는 각 교통 수단의 운영 주체. subsystem 이라고도 종종 표현하는데 public transit agency 가 아닌 일반적인 private company 라면 profit maximization 하는 것이 목.. 이전 1 2 3 4 5 6 ··· 8 다음
