TSP (Traveling Salesman Problem)

Excel VBA 응용

TSP (Traveling Salesman Problem)

kwangpal 2023. 11. 30. 02:49

TSP (Traveling Salesman Problem)

TSP는 모든 도시들을 한번씩 방문하고 원래 시작점으로 돌아오는

최단 경로의 이동 순서를 구하는 것이다.

Excel에서도 이 문제를 간단하게 풀 수 있는데

해찾기 추가 기능을 이용하면 된다.

해찾기 추가 기능은 수동으로 추가해야 사용할 수 있다.

Excel 옵션의 추가 기능 창 하단의 관리에서

Excel 추가 기능을 선택하고 이동 버튼을 누르면

추가 기능 창이 나타난다.

해 찾기 추가 기능을 체크하고 확인 버튼을 누르면

다음과 같이 해 찾기 추가 기능을 사용할 수 있게 된다.

리본 메뉴의 [데이터] 탭 오른쪽 가장자리에 [해 찾기] 버튼이 생겼다.

해 찾기 버튼을 눌러서 다음과 같은 창이 나타나면 성공이다.

이제 시트에 다음과 같이 입력하고

빨간 버튼의 이름은 Random_Points

파란 버튼의 이름은 Solve_TSP 라고 정한다.

가운데에는 직선 및 표식이 있는 분산형 차트를 넣고

차트의 이름은 Chart_1 이라고 정한다.

빨간 버튼에 다음 코드를 연결한다.

Sub Random_Points_Click()

    Dim i As Long
    Dim Num_Points As Long
    Dim rng1 As Range
    
    Num_Points = [C4]
    
    [E3:G12] = ""
    [P3:T102] = ""
    
    [C8] = "=SUM(R3:R" & Num_Points + 2 & ")"
    
    Application.Calculation = xlCalculationManual
    
    For i = 0 To Num_Points - 1
        Cells(i + 3, 5) = i
        Cells(i + 3, 6) = Rnd
        Cells(i + 3, 7) = Rnd
        Cells(i + 3, 16) = i
        Cells(i + 3, 17) = "=P" & i + 4
        Cells(i + 3, 18) = "=((OFFSET($F$3,P" & i + 3 & ",0)-OFFSET($F$3,Q" & i + 3 & ",0))^2+(OFFSET($G$3,P" & i + 3 & ",0)-OFFSET($G$3,Q" & i + 3 & ",0))^2)^0.5"
        Cells(i + 3, 19) = "=OFFSET($F$3,P" & i + 3 & ",0)"
        Cells(i + 3, 20) = "=OFFSET($G$3,P" & i + 3 & ",0)"
    Next i
    
    Cells(Num_Points + 3, 19) = [S3]
    Cells(Num_Points + 3, 20) = [T3]
    
    Application.Calculation = xlCalculationAutomatic
    
    Set rng1 = Range(Cells(3, 19), Cells(3 + Num_Points, 20))
    
    ActiveSheet.ChartObjects("Chart_1").Activate
    With ActiveChart
        .SetSourceData Source:=rng1
        .FullSeriesCollection(1).ApplyDataLabels Type:=xlDataLabelsShowLabel
        .FullSeriesCollection(1).DataLabels.Format.TextFrame2.TextRange.InsertChartField msoChartFieldRange, "=Sheet1!$P$3:$P$" & Num_Points + 2, 0
        .FullSeriesCollection(1).DataLabels.ShowCategoryName = False
        .FullSeriesCollection(1).HasLeaderLines = False
    End With
    
    [A1].Select

End Sub

파란 버튼에 다음 코드를 연결한다.

Sub Solve_TSP_Click()

    Dim Num_Points As Long
    
    Num_Points = [C4]
    
    SolverAdd CellRef:="$P$4:$P$" & Num_Points + 2, Relation:=6, FormulaText:="AllDifferent"
    SolverOk SetCell:="$C$8", MaxMinVal:=2, ValueOf:=0, ByChange:="$P$4:$P$" & Num_Points + 2, _
        Engine:=3, EngineDesc:="Evolutionary"
    SolverSolve
    SolverDelete CellRef:="$P$4:$P$" & Num_Points + 2, Relation:=6, FormulaText:="AllDifferent"

End Sub

위 코드에서 Relation:=6 이란 dif 를 의미한다.

드롭다운 메뉴에서 6번째에 있어서 6이다.