배송 경로 최적화 (외판원 문제 TSP 라우팅)
지점 좌표(평면 X·Y 또는 위도·경도)를 입력·붙여넣기하거나 지도를 눌러 추가하면 최단 방문 순서, 총 거리, 소요 시간을 계산하고 근무 시간 안에 끝나는지 판정합니다. 13지점 이하는 정확한 최적해, 그 이상은 2-opt 개선 근사해입니다.
계산 근거
거리 = 평면 직선 거리(위경도는 Haversine 대권 거리, 지구 반지름 6,371km) × 도로 우회 계수. 경로는 모든 지점을 출발점으로 한 최근접 이웃 경로에 2-opt 개선을 적용해 가장 짧은 것을 고르고, 지점이 13개 이하면 Held-Karp 동적계획법으로 정확한 최적해를 구합니다. 그보다 많으면 1-tree 하한과의 차이를 표시합니다. 소요 시간 = 거리 ÷ 평균 속도 + 지점 수 × 정차 시간. 근무 시간 90% 초과 주의는 이 도구의 판정 기준입니다.
이 도구가 업무에 도움이 됐나요?
의견 감사합니다.
자주 묻는 질문 (FAQ)
TSP가 뭔가요?
Travelling Salesman Problem 외판원 문제. 출발지에서 모든 지점을 한 번씩 방문하고 돌아오는 최단 경로. NP-hard 고전 문제. 배송·영업 라우팅·관광 코스 등 광범위 응용.
왜 휴리스틱?
지점이 n개면 가능한 순서는 (n−1)!/2 가지라 25지점이면 약 3.1×10²³ 가지입니다. 이 도구는 지점(출발지 포함)이 13개 이하면 Held-Karp 동적계획법으로 정확한 최적해를 구하고, 그보다 많으면 모든 지점을 출발점으로 한 최근접 이웃 경로에 2-opt 개선을 적용한 근사해를 냅니다. 근사해일 때는 1-tree 하한(최적 경로보다 항상 짧거나 같은 값)과의 차이를 함께 보여 주므로, 진짜 최적은 그 차이 안에 있습니다.
2-opt가 뭔가요?
경로에서 간선 두 개를 골라 그 사이 순서를 뒤집었을 때 길이가 줄면 바꾸는 방법입니다. 모든 간선 쌍을 반복해서 더 줄일 수 없을 때까지 돌립니다. 결과 경로는 서로 교차하는 구간이 없어지며, Lin–Kernighan 같은 고급 기법의 기반이 됩니다.
실무 활용?
택배·영업 일일 라우팅, 정비 순회, 다지점 출장. 실제 도로망은 직선 거리와 다르나 좌표 기반 1차 분석 충분. 정밀 라우팅은 OR-Tools, OptimoRoute, Routific 등 SaaS 활용.
Nearest Neighbor만 쓰면 왜 부족한가요?
Nearest Neighbor는 매 순간 가장 가까운 지점만 고르는 탐욕 방식이라 초반에는 효율적이지만 마지막에 멀리 남은 지점 때문에 크게 돌아오는 경우가 많습니다. 이 도구의 기본 예시(지점 10개)에서도 가까운 곳부터 도는 순서는 180.3km, 2-opt 로 개선한 최적 경로는 162.0km 로 약 10% 차이가 납니다. 결과 화면의 "가까운 곳부터 대비" 수치로 내 데이터에서의 차이를 바로 확인할 수 있습니다.
실제 도로 거리와 시간은 어떻게 반영하나요?
좌표 사이 직선 거리(위경도는 대권 거리)에 "도로 우회 계수"를 곱해 도로 거리를 근사합니다. 내비게이션으로 몇 구간의 실제 거리를 재서 직선 대비 비율을 넣으세요. 소요 시간은 거리 ÷ 평균 속도 + 지점 수 × 정차 시간으로 계산해 근무 시간 한도와 비교합니다. 좌표는 엑셀에서 "이름, X, Y" 또는 "이름, 위도, 경도" 순서로 붙여넣을 수 있고, 평면 좌표는 km·m 단위를 고를 수 있습니다.
차량이 여러 대이거나 시간 제약이 있으면?
차량 여러 대 배차는 VRP(Vehicle Routing Problem), 방문 시간대 제약이 붙으면 VRPTW로 확장되며 TSP보다 훨씬 복잡합니다. 용량·근무시간·시간창 제약을 다루려면 Google OR-Tools 같은 전용 솔버가 필요합니다. 본 도구는 차량 1대·제약 없는 순수 TSP 기준이므로 단일 라우트 1차 검토용으로 활용하세요.
한 바퀴 시간이 근무 시간을 넘으면 어떻게 하나요?
도구는 넘치는 시간을 지점 수로 환산해 몇 곳을 빼야 하는지 알려 주므로, 출발지에서 먼 쪽 지점부터 다른 차량이나 다음 날 경로로 넘기는 것이 출발점입니다. 한 구간이 전체 거리의 25%를 넘게 차지하면 그 지점을 다른 권역 경로로 묶는 방안도 함께 제시합니다. 정차 시간 합이 운전 시간보다 길면 경로를 바꾸기보다 상하차·서명 같은 지점별 절차를 줄이는 쪽이 효과가 큽니다. 근무 시간의 90%를 넘는 경로는 교통 체증 한 번에 한도를 넘길 수 있어 주의로 표시됩니다.
물류를 최적화하다
적재·경로·창고 운영을 데이터로 개선하는 스마트 물류·WMS/SCM 구축.
함께 보면 좋은 아티클
생산계획, 왜 늘 어긋날까 — 제조 현장 생산계획 실무 5단계와 계획-실행 괴리 줄이기제조업 생산계획(Production Planning)이 매번 어긋나는 이유와, 수요예측부터 상세 스케줄까지 5단계 프로세스, 현장에서 자주 터지는 문제와 대응, 수기에서 APS·AI까지 개선 로드맵을 중소·중견 제조 실무자 관점으로 정리했습니다.
창고는 있는데 재고를 못 찾는 이유 — WMS 실무 5단계와 입출고 가시화종이 입고증·엑셀 대장으로 재고가 안 맞는 이유와, 로케이션·FIFO부터 피킹·실사까지 5단계, 현장에서 자주 터지는 위치 미부여·장부 불일치 문제와 수기에서 WMS까지 로드맵을 중소·중견 제조 창고 실무자 관점으로 정리했습니다.
실무 도구·자료 업데이트 받기
새 계산기·체크리스트와 스마트팩토리·제조혁신 실무 자료를 이메일로 보내드립니다. 언제든 수신거부할 수 있습니다.