Tech

공공 데이터 없이 동적 혼잡도 만들기: 곱셈 모델과 최적 배정 알고리즘

방문자 수 API 없이 곱셈 모델로 관광지 혼잡도를 추정하고, 완전탐색·그리디로 하루 코스를 최적 배정한 과정을 정리했습니다.

Soojung Kim

— 7 min read
Share
공공 데이터 없이 동적 혼잡도 만들기: 곱셈 모델과 최적 배정 알고리즘
Photo by Jacek Dylag / Unsplash

관광 추천 서비스 "에움길"을 개발하고 있습니다. 관광 추천 서비스에서 "지금 이 곳이 얼마나 붐비는가"를 알 수 있다면, 사용자에게 한산한 시간대를 제안하거나 방문 순서를 최적화하는 것이 가능합니다. 문제는 이 데이터를 공공 API로 제공하는 곳이 거의 없다는 점입니다. 에움길에서는 방문자 수 API 없이도 혼잡도를 추정하는 모델을 직접 설계했고, 그 결과를 하루 코스 정렬에까지 활용했습니다. 이 글은 그 설계와 구현을 정리한 기록입니다. 관광지 외에도 비슷한 수요 추정 문제를 다루시는 분들께 참고가 되었으면 합니다.

전체 흐름 한눈에 보기

먼저 큰 그림입니다. 두 가지 순수 함수로 구성됩니다.

  1. estimateCongestion — 스팟 하나의 "지금 이 순간" 혼잡도를 0~100 지수로 산출하고, 개장시간대(8~20시) 전체 곡선과 가장 한산한 방문 시간대를 함께 반환합니다.
  2. reorderSpotsByCongestion — 하루 일정의 여러 스팟을, 각자의 혼잡 곡선을 보고 방문 슬롯에 재배정합니다. 목표는 총 혼잡 지수 합 최소화입니다.

두 함수 모두 외부 상태를 읽지 않는 순수 함수라 단위 테스트가 간단합니다.

혼잡도 추정: 곱셈 모델

기본 아이디어는 "기본 수요에 상황 계수를 곱해 현재 수요를 만든다"는 것입니다.

demand = prior × f_시간대 × f_요일 × f_계절 × f_날씨
index  = round( demand / RAW_MAX × 100 )

각 계수는 1.0을 중립으로 두고, 1보다 크면 혼잡을 가중하고 작으면 완화합니다. 예를 들어 토요일(1.35)의 여름 해변(1.4)을 오후 3시(피크)에 방문하면 계수들이 모두 곱해져 혼잡 지수가 높게 나옵니다.

장소별 다른 피크 시각

모든 장소가 같은 시간에 붐비지는 않습니다. 해변은 오후, 산악은 오전, 시장·도심은 점심 전후가 피크입니다. 이를 장소 성격(EnvKind)별 가우시안 곡선으로 표현했습니다.

const PEAK: Record<EnvKind, { peak: number; width: number }> = {
  beach:    { peak: 15, width: 4.5 },
  mountain: { peak: 11, width: 3.5 },
  inland:   { peak: 13, width: 4.0 },
};

function hourFactor(hour: number, kind: EnvKind): number {
  const { peak, width } = PEAK[kind];
  const g = Math.exp(-((hour - peak) ** 2) / (2 * width ** 2));
  return 0.15 + 1.2 * g;  // 야간 바닥 0.15, 피크 최대 1.35
}

가우시안을 쓴 이유는 자연스러운 분포 때문입니다. 스텝 함수로 "11~13시는 높다, 나머지는 낮다"고 하면 인위적인 계단이 생기지만, 가우시안은 피크를 중심으로 완만하게 퍼집니다.

날씨는 장소마다 민감도가 다르다

강수가 예상되면 혼잡이 줄지만, 그 정도는 장소마다 다릅니다. 해변이나 산악 같은 야외는 비가 오면 수요가 크게 떨어지지만, 실내 시장은 오히려 사람들이 모이기도 합니다.

function weatherFactor(pop: number, pty: number, kind: EnvKind): number {
  const outdoor = kind !== "inland";
  if (pty > 0)    return outdoor ? 0.5 : 0.8;  // 실제 강수
  if (pop > 60)   return outdoor ? 0.7 : 0.9;
  if (pop > 40)   return outdoor ? 0.85 : 0.95;
  return 1.0;
}

하루 곡선과 추천 시간대

estimateCongestion은 현재 지수 하나만 반환하지 않습니다. 개장시간(8~20시) 전체의 시간대별 혼잡 지수 배열(hourly)을 함께 반환합니다. 이 배열에서 가장 낮은 두 시간대를 bestHours로 추려서, "지금 붐비면 오전 9시·10시에 방문하면 비교적 한산합니다" 같은 안내를 생성합니다.

코스 재정렬: 배정 최적화 문제

하루 일정에 스팟이 여러 개 있을 때, 방문 순서를 바꾸면 전체 혼잡을 줄일 수 있습니다. 예를 들어 해변(오후 피크)과 시장(점심 피크)이 있다면, 오전 슬롯에 해변을, 오후 슬롯에 시장을 두는 것이 더 한산합니다.

이 문제는 "어느 슬롯에 어느 스팟을 배정할지"를 결정하는 배정 문제(assignment problem)입니다. 슬롯의 집합(방문 시각)은 그대로 두고, 슬롯과 스팟의 대응만 바꿉니다.

완전탐색 vs 그리디

스팟 수가 작으면(≤7) 모든 순열을 시도해서 총 혼잡 지수 합이 가장 낮은 배정을 찾습니다. 7!=5040이라 충분히 빠릅니다. 그보다 많으면 그리디 알고리즘으로 폴백합니다. 슬롯 순서대로 "지금 남은 스팟 중 이 슬롯에서 가장 한산한 것"을 하나씩 고릅니다.

const BRUTE_LIMIT = 7;

function greedyAssign(cost: number[][], n: number): number[] {
  const used = new Array<boolean>(n).fill(false);
  const perm: number[] = [];
  for (let slot = 0; slot < n; slot++) {
    let pick = -1, pickCost = Infinity;
    for (let s = 0; s < n; s++) {
      if (!used[s] && cost[s]![slot]! < pickCost) {
        pickCost = cost[s]![slot]!; pick = s;
      }
    }
    used[pick] = true;
    perm.push(pick);
  }
  return perm;
}

비용 행렬 cost[spotIdx][slotIdx]는 "스팟을 그 슬롯 시각에 배정했을 때의 혼잡 지수"입니다. 혼잡 곡선(hourly)에서 가장 가까운 시각의 값을 읽어 채웁니다.

식사·숙박은 고정

코스 항목 중 식당이나 숙박은 재배정하지 않습니다. 점심 식당을 오전으로 옮기는 것은 현실적이지 않기 때문입니다. 이 항목들은 ScheduledSpot에서 제외하고, 관광지 스팟만 재배정 대상으로 삼습니다.

결과 해석

reorderSpotsByCongestion은 { order, changed, saved, movedRefIds }를 반환합니다. saved는 원래 배정 대비 줄어든 총 혼잡 지수 합입니다. 예를 들어 saved: 18이면 "배정을 바꿔서 혼잡 지수 총합이 18 줄었다"는 뜻이고, 이 수치가 코스 화면의 reorderNote로 노출됩니다.

마치며

공공 데이터 없이 혼잡도를 만들어낸다는 발상이 처음엔 막연했습니다. 하지만 "기본 수요에 상황 계수를 곱한다"는 곱셈 모델을 잡고 나니, 각 계수를 독립적으로 조정하고 테스트할 수 있었습니다.

교훈을 정리하면 이렇습니다. 첫째, 외부 데이터가 없을 때는 도메인 지식을 계수로 인코딩하는 곱셈 모델이 유용합니다. 덧셈보다 계수 간 상호작용이 자연스럽고, 하나를 조정해도 다른 계수가 망가지지 않습니다. 둘째, 최적화 문제의 규모를 확인하고 경계를 정해두는 것이 중요합니다. n≤7 완전탐색, 그 이상 그리디라는 분기선 하나로 정확성과 성능을 동시에 잡았습니다. 셋째, 이런 모델을 순수 함수로 만들면 실제 API 없이도 단위 테스트로 빠르게 검증할 수 있습니다.

비슷한 수요 추정이나 일정 최적화 문제를 다루시는 분들께 참고가 된다면 더할 나위 없겠습니다.

Read more