[Android] 배송 순서 최적화하기 with TSP

개요

운영하고 있는 앱의 기능 중에서 사용자가 배송 순서를 설정할 수 있는데, 고객사에서 이 배송 순서를 현재 사용자 위치에서 가장 가까운 곳을 자동 설정하여 순서를 정렬해 줄 수는 없냐고 요청이 왔다. 이 내용을 들었을 때 현재 위치 좌표와 배송지의 좌표를 알고 있으니 두 좌표 간의 직선거리를 구하면 바로 될 거 같은데..? 라는 생각이 들었다. 예전에 아래 작업을 했던 게 도움이 된 것 같다.

(※ 교통 상황같은 변수는 고려하지 않았다.)

[Android] 내비게이션의 다음 경로 정보 구하기#1

---

거리 계산

저번 작업에서는 SK Open API의 '직선거리 계산 API'를 사용했는데, 이번에는 안드로이드의 Location 클래스에서 제공하는  함수를 사용했다. Location 클래스에서 제공하는 distanceBetween()과 distanceTo()를 사용하면 직선거리를 간단하게 구할 수 있다. 거리를 계산하는 방법은 아래와 같다.

// distanceBetween 직선 거리 구하기
val distance = FloatArray(1)
Location.distanceBetween(
    currentLat, currentLng, destinationLat, destinationLng, distance
)
distance[0] // 거리 값


// distanceTo 직선 거리 구하기
val startLocation = Location("start").apply {
    latitude = currentLat
    longitude = currentLng
}
val destinationLocation = Location("destination").apply {
    latitude = destinationLat
    longitude = destinationLng
}
startLocation.distanceTo(destinationLocation) // 거리 값

distanceBetween()과 distanceTo()의 차이점이라면 distanceBetween은 Array를 반환하는데 첫 번째 인덱스는 거리 값을 나타내고 두 번째와 세 번째 인덱스는 방위각 값이라고 한다. distanceTo는 거리 계산에 사용할 Location 객체가 필요하여 생성해야 하지만 결과로 거리 값만을 반환해 준다.

---

TSP

도착지까지의 거리를 계산했으니 거리 순서로 정렬 후 번호를 1번부터 부여하면 간단한 작업이라고 생각할 수 있다. 하지만 배송지에 도착했을 때 문제가 생긴다. 배송 작업을 하나 마치고 기존에 계산했던 배송 순서를 보면 지금 기준에서는 다른 배송지가 더 가까운 일이 생길 수 있다.

(왼)현재 위치로부터 배송 순서 최적화 / (오)2번까지 배송 작업을 마친 후

위의 이미지를 보면 현재 위치에서 배송지까지 거리 순서로 번호를 매겼을 때 1~7번이 되는데, 문제는 2번까지 작업을 했을 때 보인다. 2번 배송 작업을 마치고서 다음 배송지인 3번을 가려는데 3번보다 4번이 더 가깝다. 게다가 3번을 가게 되면 다른 배송지들까지의 동선이 매우 낭비된다. 이런 문제 때문에 지금 작업한 배송 순서 작업은 앱 사용에 있어서 오히려 혼란을 줄 수 있다.

 

이런 문제를 방지하고자 외판원 문제(TSP, Traveling Salesman Problem) 알고리즘이 사용된다. TSP는 조합 최적화 문제의 일종으로, 출발 정점에서 다른 모든 정점들을 방문하고 원래의 출발 정점으로 되돌아오는 순환 경로들 중에서 가중치의 합이 최소가 되는 경로를 구하는 문제라고 정의할 수 있다. 이 문제를 풀기 위해서 최근접 이웃(Nearest Neighbor) 알고리즘을 사용했다.

---

최근접 이웃 알고리즘(Nearest Neighbor)

val remainedDvList = dvList.toMutableList() // 거리 계산이 남은 리스트
val newDvList = mutableListOf<DeliveryItem>() // 가까운 순서로 저장할 리스트
var currentLat = myLocation.latitude // 기준 위도, 시작은 현재 위도
var currentLng = myLocation.longitude // 기준 경도, 시작은 현재 경도

// 계산할 항목이 없을 때까지
while (remainedDvList.isNotEmpty()) {
    // 거리가 가장 가까운 항목 찾기
    val nearestItem = remainedDvList.minByOrNull {
        val distance = FloatArray(1)
        Location.distanceBetween(
            currentLat, currentLng,
            it.latitude, it.longitude,
            distance
        )
        distance[0] // 거리 값
    }
    if (nearestItem != null) {
        remainedDvList.remove(nearestItem) // 계산한 항목 제거
        newDvList.add(nearestItem) // 계산한 항목 추가
        currentLat = nearestItem.latitude // 계산한 항목의 위도로 업데이트
        currentLng = nearestItem.longitude // 계산한 항목의 경도로 업데이트
    }
}

// 가까운 순서로 저장한 리스트의 index로 번호 부여
newDvList.forEachIndexed { index, sortedItem ->
    dvList.find { it.ivNo == sortedItem.invoiceNumber}?.order = index + 1
}

1. 현재 위치에서 남은 목적지 리스트 중 가장 가까운 목적지를 찾는다.
2. 찾은 목적지를 remainedDvList에서는 제거하고 newDvList에 추가한다.
3. 찾은 목적지로 위치를 이동했다고 생각하고 위도, 경도 값을 업데이트한다.
4. remainedDvList가 빈 값이 될 때까지 반복한다.
5. 계산 작업이 마무리되면 newDvList의 index로 번호를 부여한다.

 

최근접 이웃 알고리즘을 적용한 배송 순서

 

최근접 이웃 알고리즘을 적용했을 때 배송 순서가 확실히 나아졌음을 느낀다. TSP를 푸는 다른 알고리즘도 있고, 구글의 Directions API에 최적 경로 정렬 옵션이 있다고 하는데 아직까진 지금의 단계에서도 충분해 보인다.