Overview
문제와 해결
대형 이커머스 FC 셔틀버스 노선을 Hungarian Algorithm으로 최적화하는 자동화 시스템. 18개 지역, 69개 FC, 1,556개 노선을 처리합니다.
기존 수작업 분석 대비 90% 이상의 시간 절감. 실제 도로 거리 기반 최적화로 운영 효율성 15% 이상 개선.
Features
주요 기능
01
Hungarian Algorithm
이분 그래프 최적 매칭 알고리즘. O(n³) 시간복잡도로 최소 비용 할당 문제 해결.
02
U-Turn Prevention
150° 각도 임계값으로 U-턴 감지. 지수 페널티 적용으로 부자연스러운 경로 방지.
03
Hybrid Routing
Kakao API + OSRM 하이브리드 라우팅. 캐시 시스템으로 80%+ API 호출 절감.
04
Constraint Validation
50분 시간 허용, 45인승 정원, 저승객(<1) 노선 필터링.
Process
Pipeline Architecture
01Stage 1: Integration Analysis
MERGE/CONNECT 가능한 노선 조합 분석. 각 FC별 출퇴근 노선 데이터를 분석하여 통합 후보를 식별합니다.
02Stage 2: Hungarian Algorithm Matching
NetworkX 기반 최적 매칭. 실제 도로 거리(Kakao API)와 시간 제약을 고려하여 최적의 노선 조합을 찾습니다.
03Stage 3: Report Generation
검증 완료된 결과를 HTML 시각화, Excel RFP 보고서, JSON 데이터로 출력합니다.
Stack
기술 스택
Python 3.11NetworkXSciPyKakao MapsOSRMExcelHTMLJSON