조합적 최적화 문제를 해결하기 위해 어떤 수리적 최적화 기법을 적용하셨는지 구체적으로 설명해 주세요.

졸업 논문에서 배차 최적화 문제를 Mixed Integer Programming으로 모델링했습니다. 차량 수, 경유지 방문 시간 제약, 용량 제약이 맞물리는 구조라 조합 폭발이 금방 일어났습니다. 기법 선택 기준은 문제 규모와 풀이 시간 예산이었습니다. 최적 풀이는 보장되지만 인스턴스가 커지면 수 시간씩 걸렸습니다. 그래서 저는 Gurobi로 소규모(10차량 이하)는 정확하게 풀고, 대규모는 Greedy Heuristic으로 초기 해를 잡은 뒤 Local Search로 개선하는 두 단계 방식을 썼습니다. 운영 관점에서는 풀이 시간 제한 5분을 걸고 그 안에 최선 해를 반환하는 방식이 현실적이었습니다. 한계는 동적 변화(갑작스러운 요청 추가 등)에 재최적화를 얼마나 빠르게 돌릴 수 있는지는 아직 실험해보지 못했습니다.