🚚 허브 간 최단 경로 탐색 알고리즘 구현 + Kakao Map Api 연동 (Spring Boot)

 

 

물류 관리 및 배송 시스템을 위한 MSA 기반 플랫폼 개발 프로젝트로 물류 관리 및 배송 시스템을 만들게 되었다. 

 

그중 hub 파트를 맡게 되어 사용자가 주문을 완료하여 배송이 시작되면 특정 허브에서 도착 허브까지 가장 빠르고 효율적인 경로를 찾아 응답해 주는 코드를 구현해야 한다.

처음에는 거리만 기준으로 정렬하는 단순 탐색을 고려했지만, 실제 배송에서는 다음 요소들을 모두 고려해야 했다. 즉 가중치 기반 최단 경로 문제였고, 자연스럽게 다익스트라(Dijkstra) 알고리즘을 채택하게 되었다.

• 이동 거리 (distance)
• 소요 시간 (duration)

출발지의 위도 경도값, 도착지의 위도 경도값을 Kakao Map Api에 경로 탐색을 요청해 응답을 받아오며,

해당 결과가 있는 상태에서 동일 경로 탐색이 요청이 들어왔을 때 기존 결과와 시간차가 5분이 지나지 않은 상태이면 값을 재사용하여 응답 시간을 줄임

 

 

허브들의 정보 (p_hub)와 물류 허브 사이의 이동 데이터는 p_hub_info 테이블에 UUID로 연관 지어 저장해두고 있으며 연결 정보제약사항은 다음과 같다.

 

 

 

제약사항

• “연결된” 허브간 배송만 가능합니다. 예를 들어, 서울-부산 배송 시 서울-경기남부-대구-부산 순으로 배송해야 합니다.
• 17개 센터는 아래와 같이 연결되어 있습니다.
  • 경기남부: 경기북부, 서울, 인천, 강원도, 경상북도, 대전, 대구
  • 대전: 충청남도, 충청북도, 세종, 전라북도, 광주, 전라남도, 경기남부, 대구
  • 대구: 경상북도, 경상남도, 부산, 울산, 경상북도, 경기남부, 대전
  • 경상북도: 경기남부, 대구

 

 

 

 

 

 

---

 

Code

 

엔티티 테이블은 총 4개 존재

Hub

public class Hub extends BaseEntity {

    @Id
    @GeneratedValue(generator = "uuidv7")
    @GenericGenerator(
            name = "uuidv7",
            strategy = "lib.id.UUIDv7Generator"
    )
    @Column(name = "id", columnDefinition = "BINARY(16)")
    private UUID id;

    @Column(name = "name", nullable = false, length = 20)
    private String name;

    @Column(name = "hub_manager_id", nullable = false, columnDefinition = "BINARY(16)")
    private UUID hubManagerId;

    @Column(name = "postal_code", nullable = false, length = 20)
    private String postalCode;

    @Column(name = "country", nullable = false, length = 50)
    private String country;

    @Column(name = "region", nullable = false, length = 50)
    private String region;

    @Column(name = "city", nullable = false, length = 50)
    private String city;

    @Column(name = "district", length = 50)
    private String district;

    @Column(name = "road_name", nullable = false, length = 100)
    private String roadName;

    @Column(name = "building_name", length = 50)
    private String buildingName;

    @Column(name = "detail_address", length = 100)
    private String detailAddress;

    @Column(name = "full_address", nullable = false, length = 100)
    private String fullAddress;

    @Column(name = "latitude", nullable = false, precision = 10, scale = 7)
    private BigDecimal latitude;

    @Column(name = "longitude", nullable = false, precision = 10, scale = 7)
    private BigDecimal longitude;
}

 

 

 

HubInfo

@Getter
@Entity
@Table(name = "p_hub_info")
public class HubInfo extends BaseEntity {

    @Id
    @GeneratedValue(generator = "uuidv7")
    @GenericGenerator(
            name = "uuidv7",
            strategy = "lib.id.UUIDv7Generator"
    )
    @Column(name = "id", columnDefinition = "BINARY(16)")
    private UUID id;

    @Column(name = "start_hub_id", nullable = false, columnDefinition = "BINARY(16)")
    private UUID startHubId;

    @Column(name = "end_hub_id", nullable = false, columnDefinition = "BINARY(16)")
    private UUID endHubId;

    @Column(name = "delivery_duration")
    private Integer deliveryDuration;
    // 배송 예측 소요 시간

    @Column(name = "distance", precision = 10, scale = 3)
    private BigDecimal distance;
    // 배송 거리 km 단위

    public static HubInfo create(UUID startHubId, UUID endHubId) {
        HubInfo hubInfo = new HubInfo();
        hubInfo.startHubId = startHubId;
        hubInfo.endHubId = endHubId;
        return hubInfo;
    }

    // 시간, 거리 넣기
    public void updateDeliveryInfo(Integer deliveryDuration, BigDecimal distance) {
        this.deliveryDuration = deliveryDuration;
        this.distance = distance;
    }


    // false면 기존 값 재사용
    public boolean checkUpdateTime(LocalDateTime updateTime) {
        LocalDateTime updatedAt = this.getUpdatedAt();
        if (updatedAt == null) {
            return true;
        }

        if (this.deliveryDuration == null || this.distance == null) {
           return true;
       }
        // 두 시간 차이를 분 단위로 계산
        long diffMinutes = Duration.between(updatedAt, updateTime).toMinutes();

        // 5분 이상 차이가 난다면 true
        return diffMinutes >= 5;
    }


    public void updateHubInfo(UUID startHubId, UUID endHubId) {
        if(startHubId != null) this.startHubId = startHubId;
        if(endHubId != null) this.endHubId = endHubId;
    }

}

 

 

 

HubRouteLog (출발지와 목적지)

@Getter
@Entity
@Table(name = "p_hub_route_log")
public class HubRouteLog extends BaseEntity {

    @Id
    @GeneratedValue(generator = "uuidv7")
    @GenericGenerator(
            name = "uuidv7",
            strategy = "lib.id.UUIDv7Generator"
    )
    @Column(name = "id", columnDefinition = "BINARY(16)")
    private UUID id;

    @Column(name = "start_hub_id", nullable = false, columnDefinition = "BINARY(16)")
    private UUID startHubId;

    @Column(name = "end_hub_id", nullable = false, columnDefinition = "BINARY(16)")
    private UUID endHubId;

    @Column(name = "total_duration")
    private Integer totalDuration;
    //총 소요 시간

    @Column(name = "total_distance", precision = 10, scale = 3)
    private BigDecimal totalDistance;
    // 총 거리 km

    public static HubRouteLog create(
        UUID startHubId,
        UUID endHubId,
        Integer totalDuration,
        BigDecimal totalDistance
    ){
        HubRouteLog log = new HubRouteLog();
        log.startHubId = startHubId;
        log.endHubId = endHubId;
        log.totalDuration = totalDuration;
        log.totalDistance = totalDistance;
        return log;
    }

}

 

 

HubRouteLogStop  (허브 경로 정보)

@Getter
@Entity
@Table(name = "p_hub_route_log_stop")

public class HubRouteLogStop extends BaseEntity {

    @Id
    @GeneratedValue(generator = "uuidv7")
    @GenericGenerator(
            name = "uuidv7",
            strategy = "lib.id.UUIDv7Generator"
    )
    @Column(name = "id", columnDefinition = "BINARY(16)")
    private UUID id;

    @Column(name = "hub_id", nullable = false, columnDefinition = "BINARY(16)")
    private UUID hubId;
    // 경로 허브 id

    @Column(name = "hub_route_log_id", nullable = false, columnDefinition = "BINARY(16)")
    private UUID hubRouteLogId;
    // 출발허브 || 도착허브 정보

    @Column(name = "sequence_num", nullable = false)
    private Integer sequenceNum;

    public static HubRouteLogStop create(UUID hubRouteLogId, UUID hubId, int sequenceNum) {
        HubRouteLogStop stop = new HubRouteLogStop();
        stop.hubRouteLogId = hubRouteLogId;
        stop.hubId = hubId;
        stop.sequenceNum = sequenceNum;
        return stop;
    }

}

 

 

 

 

 

 

허브 간 Edge 가중치를 계산하는 서비스 – HubEdgeWeightService

• p_hub_info 테이블에서 허브 간 연결 정보(HubInfo) 를 조회
• 최근 5분 이내에 계산된 캐시 된 거리/시간이 있으면 그대로 재사용
• 캐시가 없거나 오래되었으면 Kakao Map API를 호출해서 실제 거리/시간을 다시 계산
• 새로 계산한 값은 HubInfo 엔티티에 업데이트해서 DB 기반 캐시처럼 재사용
• 최종적으로 EdgeWeight VO로 (시작 허브, 도착 허브, 소요 시간, 거리)를 반환

@Service
@Slf4j
@RequiredArgsConstructor
public class HubEdgeWeightService implements HubEdgeWeightProvider {

    private final HubInfoRepository hubInfoRepository;
    private final HubRepository hubRepository;
    private final KakaoMapClient kakaoMapClient;

    @Override
    public EdgeWeight getWeight(UUID startHubId, UUID endHubId) {

        HubInfo hubInfo = hubInfoRepository.findByStartHubIdAndEndHubId(startHubId, endHubId)
            .orElseThrow(()-> new BusinessException(ErrorCode.HUB_INFO_NOT_FOUND));

        LocalDateTime now = LocalDateTime.now();

        // 1) 5분 이내의 캐시가 있으면 기존 값 그대로 사용
        if (hubInfo.getDeliveryDuration() != null && hubInfo.getDistance() != null && !hubInfo.checkUpdateTime(now)) {

            log.info("[HubEdgeWeight] cache hit: {} -> {} ({}h {}m, {} km)",
                startHubId, endHubId, hubInfo.getDeliveryDuration()/3600, hubInfo.getDeliveryDuration() % 3600 / 60, hubInfo.getDistance());

            return new EdgeWeight(startHubId, endHubId, hubInfo.getDeliveryDuration(), hubInfo.getDistance());
        }

        // 2) 아니면 Kakao API로 실제 거리/시간 계산
        // 허브 존재 여부 확인
        Hub startHub = hubRepository.findById(hubInfo.getStartHubId())
            .orElseThrow(() -> new BusinessException(ErrorCode.HUB_NOT_FOUND));
        Hub endHub = hubRepository.findById(hubInfo.getEndHubId())
            .orElseThrow(() -> new BusinessException(ErrorCode.HUB_NOT_FOUND));

        // 해당 허브들에 위도, 경도값 추출
        String origin = startHub.getLongitude() + "," + startHub.getLatitude();
        String destination = endHub.getLongitude() + "," + endHub.getLatitude();

        DirectionInfoResponseV1 direction = kakaoMapClient.getDirection(
            origin,
            destination,
            2,          // carType
            "DIESEL",   // carFuel
            true        // carHipass
        );

        // Kakao 응답은 초 단위
        int durationSec = (int) direction.duration();
        BigDecimal distanceKm = BigDecimal
            .valueOf(direction.distance() / 1000.0)
            .setScale(3, RoundingMode.HALF_UP);

        hubInfo.updateDeliveryInfo(durationSec, distanceKm);

        log.info("[HubEdgeWeight] cache hit: {} -> {} ({}h {}m, {} km)",
            startHubId, endHubId, hubInfo.getDeliveryDuration() / 3600, hubInfo.getDeliveryDuration() % 3600 / 60, hubInfo.getDistance());

        return new EdgeWeight(startHubId, endHubId, durationSec, distanceKm);
    }
}

 

 

 

최단 경로 탐색 + 로그 저장 – findFastestRouteAndLog

• 경로 탐색(findFastestRoute)과 로그 저장(logRoute)을 하나의 트랜잭션 안에서 처리

    /**
     * 최단 시간 기준 경로 탐색 + 로그 저장
     */
    @Transactional
    public HubRouteResult findFastestRouteAndLog(UUID startHubId, UUID endHubId) {

        HubRouteResult result = findFastestRoute(startHubId, endHubId);
        logRoute(result);
        
        return result;
    }

 

 

최단 시간 기준 경로 탐색 – findFastestRoute

• HubInfo에 잇는 모든 정보를 findAll하여 가져오고
• Map <허브 ID, List <Edge>> 형태로 인접 리스트를 구성한다.
• 허브 간 시간/거리는 HubEdgeWeightProvider(= HubEdgeWeightService)를 통해 가져옴
• 다익스트라 알고리즘 호출

    /**
     * 최단 시간 기준 경로 탐색 (Dijkstra)
     */
    @Transactional(readOnly = true)
    public HubRouteResult findFastestRoute(UUID startHubId, UUID endHubId) {

        List<HubInfo> connections = hubInfoRepository.findAll();

        if (connections.isEmpty()) {
            log.warn("[HubRoute] no hub connections in DB");
            throw new BusinessException(ErrorCode.HUB_ROUTE_NOT_FOUND);
        }


        // 1. 인접 리스트 그래프 구성 (duration 기준 weight)
        Map<UUID, List<Edge>> graph = new HashMap<>();

        for (HubInfo info : connections) {
            UUID from = info.getStartHubId();
            UUID to = info.getEndHubId();

            // computeInfAbsent -> Map에서 key가 없을 때만 value를 생성해서 넣어주는 메서드
            graph.computeIfAbsent(from, k -> new ArrayList<>()).add(new Edge(to, info));

        }

        // 2. 다익스트라 실행
        return dijkstraByDuration(graph, startHubId, endHubId);
    }

 

 

 

 

다익스트라 구현 – dijkstraByDuration

• 가중치를 “시간(durationSec)”으로 고정해서 “최단 시간 경로”를 계산
• dist: 시작 허브로부터 각 허브까지의 최소 소요 시간을 저장
• prev: 나중에 실제 경로를 복원하기 위해 “이 허브로 오기 직전 허브”를 저장
• PriorityQueue <Node>: 현재까지의 누적 시간이 가장 짧은 허브부터 탐색하기 위해 우선순위 큐를 사용

주석을 자세히 보시면 편합니다.

    private HubRouteResult dijkstraByDuration(Map<UUID, List<Edge>> graph, UUID startHubId, UUID endHubId) {

        Map<UUID, Integer> dist = new HashMap<>();  // 최소 시간
        Map<UUID, UUID> prev = new HashMap<>();     // 경로 복원용

        // 우선순위 큐로 Node 객체를 비교할 때 n.time (노드까지의 누적 시간)을 기준으로 정렬해서 넣음
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.time));


        // 시작 허브의 거리를 0으로 두고, 나머지는 모두 무한대(최대값)로 초기화
        for (UUID hubId : graph.keySet()) {
            dist.put(hubId, Integer.MAX_VALUE);
        }

        // dist는 지금까지 발견된 최소 누적 시간으로 기록 저장소
        // 출발 시점은 0으로
        dist.put(startHubId, 0);

        // pq는 앞으로 탐색할 후보 노드 목록
        // 시작 허브를 시간 0으로 큐에 넣어서 다익스트라 탐색 시작
        pq.offer(new Node(startHubId, 0));


        // 가장 누적 시간이 짧은 허브부터 꺼내서, 허브에서 갈 수 있는 모든 인접 허브의 거리를 갱신
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            UUID curId = cur.hubId;


            // 최단 거리 알고리즘의 특성상, 목적지 허브가 PQ에서 꺼내졌다는 것은 그 시간 값이 최종 최소 시간이라는 의미
            if (curId.equals(endHubId)) {
                break;
            }

            // cur.time > dist.get(curId) 이면, 이미 더 짧은 경로가 존재하는 상태라서 스킵
            // 예: 더 긴 경로로 먼저 들어갔다가, 나중에 더 짧은 경로가 발견된 경우로
            // “현재 꺼낸 값이 dist 테이블에 저장된 최소 시간보다 크면 버림
            if (cur.time > dist.get(curId)) {
                continue;
            }


            // 현재 허브(curId)가 연결된 허브들의 목록을 가져온다. 없으면 빈 리스트 반환 (NPE 방지)
            // key: 현재 허브 ID,  value: 그 허브에서 갈 수 있는 인접 허브들로의 간선 목록
            List<Edge> edges = graph.getOrDefault(curId, List.of());

            // 현재 허브에서 직접 갈 수 있는 허브들만 순회
            for (Edge e : edges) {

                //인접 허브들까지 얼마나 걸리는지 시간 계산
                EdgeWeight weight = hubEdgeWeightProvider.getWeight(curId, e.toHubId);

                // cur.time = 출발 → e. 현재 허브까지 걸린 누적 시간
                int nextTime = cur.time + weight.durationSec();

                // 아직 도달한 적 없는 허브라면 → 현재 값 = ∞ 이고 nextTime이 기존 값보다 더 빠르면 저장
                // 목적지에 처음 도달했다고 끝나는 게 아니라 더 빠른 경로가 발견될 때까지 반복문 동안 dist를 계속 비교·갱신
                if (nextTime < dist.getOrDefault(e.toHubId, Integer.MAX_VALUE)) {
                    dist.put(e.toHubId, nextTime);

                    //prev.put(e.toHubId, curId); 를 통해 경로 추적용 역방향 링크를 기록
                    prev.put(e.toHubId, curId);
                    pq.offer(new Node(e.toHubId, nextTime));
                }
            }
            // dist에는 반복적으로 더해진 시간 nextTime가 들어감
        }


        // 도착 허브가 여전히 무한대라면, 실제 경로가 없다고 판단하고 예외처리
        if (!dist.containsKey(endHubId) || dist.get(endHubId) == Integer.MAX_VALUE) {
            log.warn("[HubRoute] no path found: {} -> {}", startHubId, endHubId);
            throw new BusinessException(ErrorCode.HUB_ROUTE_NOT_FOUND);
        }


        // 3. 경로 복원
        // prev 맵을 이용해 endHubId → ... → startHubId 방향으로 역추적을 진행
        // 리스트에 담고 나서 Collections.reverse(path)로 순서를 뒤집어 최종적으로 start → ... → end 순서의 경로를 얻음
        List<UUID> path = new ArrayList<>();
        UUID cur = endHubId;
        while (cur != null) {
            path.add(cur);
            cur = prev.get(cur);
        }
        Collections.reverse(path);

        // 4. 총 거리 합산
        // path 리스트를 인접한 두 개씩 (from, to) 쌍으로 묶어서 순회
        BigDecimal totalDistance = BigDecimal.ZERO;

        for (int i = 0; i < path.size() - 1; i++) {
            UUID from = path.get(i);
            UUID to = path.get(i + 1);

            // 그래프에서 from 의 인접 간선 목록을 가져와 to 로 가는 간선을 찾음
            List<Edge> edges = graph.getOrDefault(from, List.of());
            Edge edge = edges.stream()
                .filter(e -> e.toHubId.equals(to))
                .findFirst()
                .orElseThrow(() -> new BusinessException(ErrorCode.HUB_EDGE_NOT_FOUND));


            // 거리 합산은 다시 weight를 조회해서 distanceKm만 사용했다.
            // hubEdgeWeightProvider 내부 캐시 덕분에 Kakao API는 필요 시에만 호출되었다.
            EdgeWeight weight = hubEdgeWeightProvider.getWeight(from, to);
            // 해당 간선의 distanceKm 를 모두 더해 총 이동 거리를 계산
            totalDistance = totalDistance.add(weight.distanceKm());
        }

        int totalDuration = dist.get(endHubId);

        return new HubRouteResult(
            startHubId,
            endHubId,
            path,
            totalDuration,
            totalDistance
        );
    }

 

 

 

 

경로 로그 저장 – logRoute

• 경로를 찾는 것에서 끝내지 않고, 실제로 어떤 경로가 선택되었는지 DB에 남김

1. 헤더 로그 – HubRouteLog

• 출발 허브, 도착 허브
• 총 소요 시간, 총 이동 거리

2. 스텝 로그 – HubRouteLogStop

• 경로 상의 각 허브 ID
• seq 값을 통해 순서를 기록
  이렇게 하면 나중에 조인해서 실제 경로를 그대로 재구성

    /**
     * 경로 로그 테이블에 저장
     */
    @Transactional
    public void logRoute(HubRouteResult result) {

        HubRouteLog logEntity = HubRouteLog.create(
            result.startHubId(),
            result.endHubId(),
            result.totalDurationSec(),
            result.totalDistanceKm()
        );
        hubRouteLogRepository.save(logEntity);

        int seq = 0;
        for (UUID hubId : result.pathHubIds()) {
            HubRouteLogStop stop = HubRouteLogStop.create(
                logEntity.getId(),
                hubId,
                seq++
            );
            hubRouteLogStopRepository.save(stop);
        }

        log.info("[HubRoute] Logged route {} -> {} : {} sec, {} km, {} hops",
            result.startHubId(), result.endHubId(),
            result.totalDurationSec(), result.totalDistanceKm(),
            result.pathHubIds().size());
    }

 

 

 

 

Edge - 그래프의 한 간선을 의미

• 어떤 허브(toHubId)로 가는지
• 그때 걸리는 시간(durationSec)
• 그때 이동 거리(distanceKm)

 

Node - 우선순위 큐에서 사용할 “현재 위치 + 지금까지 누적된 시간”을 표현

 

    private static class Edge {
        private final UUID toHubId;
        private final HubInfo hubInfo;

        public Edge(UUID toHubId, HubInfo hubInfo) {
            this.toHubId = toHubId;
            this.hubInfo = hubInfo;
        }
    }

    private static class Node {
        private final UUID hubId;
        private final int time;

        private Node(UUID hubId, int time) {
            this.hubId = hubId;
            this.time = time;
        }
    }

 

 

 

 

 

결과

 

 

 

 

요구사항에 맞춰 서울에서 부산 hub까지의 요청인 경우

서울 -> 경기남부 -> 대구 -> 부산 순서로 올바르게 경로를 찾아 응답을 주고 있다.

 

첫 요청의 경우 연관 경로에 허브들끼리의 시간을 api를 보내 가져와야 하니 시간이 오래 걸리지만, 한번 결과를 가져온 상태에서 5분이 지나지 않은 경우 DB에서 가져와 빠른 응답을 주고 있다.

서울 -> 부산으로 결과가 나온 이후 5분이 지나지 않은 상태에서 경기남부 -> 부산으로 조회 시 빠른 도착 시간 조회가 가능하다.

 

 

 

구현이 완료 되었지만 Redis 캐시를 사용하고 있지 않다는 문제가 존재하여 다음 게시물에서 이를 보완하려 한다.

 

https://kimfishes.tistory.com/13?category=1262695

🚚 허브 간 최단 경로 탐색 캐시 스탬피드 (Cache Stampede) 발생+해결