여정 경로 최적화: 시간 창과 다중 제약을 푸는 Itinerary Routing

출발지부터 도착지까지 다중 목적지와 교통수단, 시간 창, 비용·편의 제약을 동시에 만족시키는 여정을 찾는 일은 여행·물류·현장 서비스의 운영 성과를 직접 좌우한다. Itinerary Routing은 OTA(Online Travel Agency), 항공·철도, 라이드셰어, 라스트마일 배송에서 서비스 품질과 수익성을 동시에 개선하는 기반 기술로 자리 잡았다.

그래프와 다목적함수로 여정을 모델링한다

Itinerary Routing은 노드(정류장·포인트)와 엣지(이동 구간)로 구성된 그래프 위에서 비용·시간·리스크 최소화와 만족도 최대화 같은 복수 목적함수 하에, 시간 창과 자원 제약을 만족하는 여정(여러 구간의 시퀀스)을 산출하는 절차다. 단일 경로 탐색과 달리 연결·환승·대기·가용성·가격 변동을 포함한다.

문제는 다목적 최적화로 모델링한다. 입력(요청·선호·실시간 데이터) → 제약(시간 창·능력·운휴·정책) → 목적함수(가중합 또는 파레토) → 해 탐색(정확/휴리스틱/학습 기반) → 후보 랭킹·설명 출력 순으로 흐른다. 단일 모드 최단경로와 달리 멀티모달·다중 제약·불확실성(지연/취소)·개인화 선호를 반영해야 하고, 동적 재계산과 설명가능성이 함께 요구된다.

데이터 레이어: 정적과 실시간을 함께 본다

정적 데이터는 노선망 그래프, 시간표, 운임, 환승 규칙, 서비스 레벨, 정책 제약을 관리한다. 실시간 데이터는 혼잡·지연, 재고·좌석, 가격 변동, 폐쇄·이벤트를 수집·스트리밍 처리한다. 데이터 신뢰도 스코어, 결측·오류 보정, 스냅샷 버저닝으로 품질을 관리한다.

최적화 엔진과 오케스트레이션

알고리즘은 MIP/CP-SAT, 라벨 세팅(시간 의존 최단경로), 메타휴리스틱(탭서치·유전), 하이브리드 방식을 적용한다. 다목적화는 가중합·ε-제약·파레토 프론티어로 후보를 생성하고 지표를 표준화·정규화한다. 가속화는 다중 수준 그래프, 전처리 프루닝, 캐시·비드-다이렉션·에지 랭크로 처리한다.

오케스트레이션 계층은 요청 스키마 검증, 선호·정책 머지, 시나리오 파라미터화를 처리하고, 이전 결과를 워밍 캐시로 활용해 증분 계산을 하며 장애 시 페일세이프 경로를 제공한다. SLA 관리는 타임박싱 탐색과 품질-지연 트레이드오프 정책 스위치로 한다.

설명·경험과 모니터링

경로 설명은 환승 이유, 비용 분해, 지연 민감도, 대안 비교를 제공하고, "시간/비용/환승 최소화" 가중치 슬라이더 같은 제어 레버로 하드·소프트 제약을 구분해 노출한다. 데이터 신뢰도와 예측 불확실성을 시각화하면 사용자 신뢰를 확보할 수 있다.

운영 지표는 응답지연, 성공률, 도착 정시율·환승 횟수 같은 라우팅 품질을 추적한다. 사용자 선택 로그를 기반으로 가중치를 업데이트하는 학습 루프와 A/B 실험을 병행하고, 실시간 성능 저하나 데이터 드리프트는 이상 탐지로 알림·자동 완화한다.

절차 다이어그램

⤢✕

실무에서는 어떻게 쓰이나

OTA·항공·철도 예약은 다구간 여정에서 최소 환승·최소 비용의 균형을 맞추고 좌석·운임을 실시간 반영한다. GDS/API 쿼터·지연 문제는 캐시 계층과 인기 오리진-데스티네이션 사전 계산으로 완화한다. 라이드셰어·풀링 디스패치는 다중 픽업/드롭, 시간 창·차량 용량 제약 아래 지연 패널티를 최소화하고, 수요 피크에는 타임박스 휴리스틱과 근사 해·동적 요금으로 대응한다. 필드 서비스·라스트마일은 기사 스케줄링과 SLA·부하 균형, 고객 약속 시간 준수가 핵심이며 노쇼·지연에는 재계산 트리거·버퍼링·확률적 소요시간으로 대응한다. 화물·인터모달 운송은 해상-철도-트럭 연계에서 허브 제약·커트오프, 리스크·관세를 최적화하고 포트 혼잡에는 시나리오 최적화와 대체 허브 자동 제안으로 대응한다.

아키텍처와 트레이드오프

마이크로서비스로 데이터 수집, 그래프 빌더, 라우터, 랭커를 분리하면 독립 확장이 가능한 대신 호출 지연이 늘어난다. L1 인메모리·L2 분산 캐시 전략은 지연을 줄이지만 정합성 관리가 필요하고, 그래프 스냅샷을 원자적으로 교체하며 버저닝하면 반복가능성은 좋아지지만 저장 비용이 늘어난다.

성능·확장성은 전처리 히에라키 그래프, 다중 시작점 A*, 라벨 도미넌스 프루닝으로 확보하고, 타임박스·품질 스위치(정확→휴리스틱→캐시)로 SLA를 보장한다. 데이터·보안 측면에서는 PII를 분리 저장·토큰화하고 전송·저장을 암호화하며 감사 로그를 남긴다. 외부 API 쿼터는 레이트리밋·서킷브레이커·백오프·폴백으로 보호한다. 신뢰성은 분산락과 early refresh로 캐시 스탬피드를 방지하고 카나리 롤아웃·자동 롤백, 실험군/대조군 트래픽 격리로 확보한다.

알고리즘 선택 비교

접근	성능	확장성	일관성	안정성	운영 편의
정수계획/MIP·CP	중~고, 최적 보장(소규모)	저~중(문제 크기 민감)	높음(반복성 우수)	중(파라미터 민감)	중(모델 유지 필요)
메타휴리스틱(A*, 탭서치, 유전)	중~고(타임박스 유리)	고(대규모 병렬)	중(근사 해 변동)	고(노이즈 견고)	고(튜닝 체계화 용이)
학습 기반(랭킹/강화학습)	중(데이터 의존)	고(서빙 효율)	중(데이터 드리프트 영향)	중(개선-리스크 공존)	중(피드백 파이프라인 필요)

실무 체크리스트로는 필수 하드 제약과 소프트 패널티를 분리하고 가중치 기본값을 문서화하는 것, 타임박스·폴백 단계(최적→근사→캐시→기본 경로)를 정의하는 것, 사용자 선택 로그를 랭킹 학습 루프로 연결하고 오프라인 리플레이 테스트를 구축하는 것을 꼽을 수 있다.

코드 예시: 시간 창을 가진 소형 여정 최적화

전제는 Python 3.10+, ortools >= 9.8이며, 목적은 시간 창을 갖는 소형 여정(픽업 포인트 5곳)의 최소 이동 시간 경로를 산출하는 것이다.

# pip install ortools
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

# 거리/시간 행렬(분)
time_matrix = [
    [0, 7, 9, 9, 8, 6],
    [7, 0, 4, 2, 7, 5],
    [9, 4, 0, 3, 6, 8],
    [9, 2, 3, 0, 4, 6],
    [8, 7, 6, 4, 0, 5],
    [6, 5, 8, 6, 5, 0],
]
# 각 노드 시간 창(분) [earliest, latest]
time_windows = [
    (0, 60),  # depot
    (5, 20),
    (0, 25),
    (10, 30),
    (0, 40),
    (0, 50),
]

manager = pywrapcp.RoutingIndexManager(len(time_matrix), 1, 0)  # 1 vehicle, depot=0
routing = pywrapcp.RoutingModel(manager)

def time_callback(from_index, to_index):
    f = manager.IndexToNode(from_index)
    t = manager.IndexToNode(to_index)
    return time_matrix[f][t]

transit_cb = routing.RegisterTransitCallback(time_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_cb)

# 시간 차원 추가(대기 허용, 최대 100분)
routing.AddDimension(transit_cb, 30, 100, False, "Time")
time_dim = routing.GetDimensionOrDie("Time")

# 시간 창 제약 적용
for node, (e, l) in enumerate(time_windows):
    index = manager.NodeToIndex(node)
    time_dim.CumulVar(index).SetRange(e, l)

# 검색 파라미터
params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
params.time_limit.FromSeconds(2)  # 타임박스

solution = routing.SolveWithParameters(params)
if solution:
    index = routing.Start(0)
    route, total_time = [], 0
    while not routing.IsEnd(index):
        node = manager.IndexToNode(index)
        t = solution.Value(time_dim.CumulVar(index))
        route.append((node, t))
        next_index = solution.Value(routing.NextVar(index))
        total_time += routing.GetArcCostForVehicle(index, next_index, 0)
        index = next_index
    node = manager.IndexToNode(index)
    t = solution.Value(time_dim.CumulVar(index))
    route.append((node, t))
    print("Route (node, arrival_time):", route)
    print("Total travel time:", total_time)
else:
    print("No solution found")

하드 제약은 시간 창과 차량 수이고, 소프트 제약인 지연 패널티는 비용 가중치로 반영할 수 있다. 타임박스 설정으로 SLA를 보장하고, 불가능한 경우 근사해 반환 로직을 구현하는 것이 좋다.

수치로 보면

멀티모달 환승 최적화를 기준으로 평균 여정 시간이 8~~15% 단축되는데, 이는 기존 규칙 기반 대비 내부 벤치마크 가정이다. 환승 횟수는 10~~20% 감소하고 정시 도착률은 3~~7%p 향상되며, 설명·대안 제공 효과로 OTA 전환율이 2~~5%p 개선되고 캐시·프루닝으로 API 비용이 15~30% 절감된다. 정성적으로는 설명가능성과 선호 반영으로 사용성·신뢰성이 높아지고 운영 의사결정이 자동화되며, 폴백·부분 최적을 수용하는 장애 회복력과 실험·학습 기반의 지속 개선이 뒤따른다.

데이터 품질 관리, 다목적 최적화 엔진, 오케스트레이션·설명 체계를 함께 갖추면 SLA와 품질을 동시에 달성할 수 있다. 단계적 폴백과 관측·학습 루프를 갖춘 아키텍처로 도입하는 것이 안전하다.