VBA（Excel）巡回セールスマン問題でキャリアアップ！最短ルートを求めるプログラミング術

この記事では、Excel VBA（ビジュアルベーシックアプリケーション）を使って、巡回セールスマン問題を解決するためのプログラミング方法について解説します。特に、キャリアチェンジやスキルアップを目指す方々が、プログラミングスキルを活かして、業務効率化や新しい働き方を実現するためのヒントを提供します。巡回セールスマン問題の基本的な考え方から、具体的なプログラムの実装方法、そしてキャリアに繋げるための活用事例まで、幅広く掘り下げていきます。

excelのVBA（ビジュアルベーシックアプリケーション）での巡回セールスマン問題のプログラムを教えてください。

10都市を巡る巡回セールスマンの最短距離を求めようとしています。1≧x,y≧0のマス内に10点選びそれぞれの点に1度ずつ巡るというのを解こうとしています。全検索のプログラムとニューラルネットワーク、または遺伝的アルゴリズムで出したいのですが自分の理解が足らず取り掛かりもどうしたらわかりません。

それぞれの都市間の距離を最初にすべて出しておいてそれをプログラムに入れてあげてプログラムを作成しようと考えているのですがこの方法は正しいでしょうか？

自分の理解不足で全くわからない状況です。プログラムですのでややこしくなると思いますが教えていただけたら幸いです。よろしく願います。

巡回セールスマン問題とは？

巡回セールスマン問題（Traveling Salesman Problem、TSP）は、与えられた複数の都市をすべて1度ずつ訪れ、出発点に戻る最短のルートを見つけるという、有名な最適化問題です。一見シンプルに見えますが、都市の数が増えると計算量が爆発的に増大し、解を求めるのが非常に難しくなることで知られています。この問題は、物流、配送計画、回路設計など、さまざまな分野で応用されています。

なぜVBAで巡回セールスマン問題を解くのか？

VBA（Visual Basic for Applications）は、Microsoft ExcelなどのOffice製品で利用できるプログラミング言語です。VBAを使うことで、Excelの機能を拡張し、複雑な計算や処理を自動化できます。巡回セールスマン問題をVBAで解くことには、以下のようなメリットがあります。

手軽さ: Excelは多くの人が日常的に使用しているツールであり、VBAも比較的簡単に習得できます。
可視化: Excelのグラフ機能などを使って、ルートや結果を視覚的に表現できます。
業務効率化: 配送ルートの最適化など、実際の業務に役立てることができます。

VBAで巡回セールスマン問題を解くためのステップ

巡回セールスマン問題をVBAで解くためには、以下のステップで進めます。

問題の定義: 巡回する都市の数、各都市の座標（x, y）を設定します。
距離計算: 各都市間の距離を計算します。
ルート生成: すべての都市を巡るルートを生成します。
距離計算: 各ルートの総距離を計算します。
最適ルートの特定: 最も短い距離のルートを特定します。
結果の表示: 最適ルートと総距離を表示します。

1. 問題の定義とデータの準備

まず、巡回する都市の数と、各都市の座標を決定します。ここでは例として、10都市の場合を考えます。Excelシートに都市の座標を入力し、VBAコードでこのデータを読み込みます。

都市	X座標	Y座標
1	10	20
2	30	40
3	50	10
4	70	30
5	20	50
6	40	60
7	60	20
8	80	50
9	10	70
10	90	10

このデータをExcelシートに入力し、VBAコードで参照できるようにします。

2. 距離計算の実装

各都市間の距離を計算するために、以下の数式を使用します（三平方の定理）。

距離 = √((x2 – x1)^2 + (y2 – y1)^2)

VBAコードでは、この数式を関数として実装します。


Function CalculateDistance(x1 As Double, y1 As Double, x2 As Double, y2 As Double) As Double
    CalculateDistance = Sqr((x2 - x1) ^ 2 + (y2 - y1) ^ 2)
End Function

3. ルート生成の方法

巡回セールスマン問題を解くためのルート生成には、いくつかの方法があります。ここでは、基本的な考え方として、全検索（総当たり）と、より効率的なアルゴリズムについて解説します。

3.1 全検索（総当たり）

全検索は、すべての可能なルートを生成し、それぞれの距離を計算して、最も短いルートを見つける方法です。都市数が少ない場合は有効ですが、都市数が増えると計算量が爆発的に増大するため、現実的な方法ではありません。10都市の場合でも、約360万通りのルートを計算する必要があります。

VBAコードで全検索を実装する場合、再帰処理やPermutations（順列）のアルゴリズムを使用します。


Sub 全検索_TSP()
    Dim cities() As Integer
    Dim numCities As Integer
    Dim i As Integer, j As Integer
    Dim minDistance As Double
    Dim currentDistance As Double
    Dim bestRoute() As Integer
    Dim route() As Integer

    ' 都市の数
    numCities = 10

    ' 都市の番号を配列に格納
    ReDim cities(1 To numCities)
    For i = 1 To numCities
        cities(i) = i
    Next i

    ' 最小距離の初期化
    minDistance = Double.MaxValue

    ' すべての順列を生成し、距離を計算
    route = generatePermutations(cities)
    For i = 1 To UBound(route, 2)
        currentDistance = 0
        For j = 1 To numCities - 1
            currentDistance = currentDistance + CalculateDistance( _
                Cells(route(j), 2), Cells(route(j), 3), _
                Cells(route(j + 1), 2), Cells(route(j + 1), 3))
        Next j
        currentDistance = currentDistance + CalculateDistance( _
            Cells(route(1), 2), Cells(route(1), 3), _
            Cells(route(numCities), 2), Cells(route(numCities), 3))

        ' 最小距離を更新
        If currentDistance < minDistance Then
            minDistance = currentDistance
            ReDim bestRoute(1 To numCities)
            For j = 1 To numCities
                bestRoute(j) = route(j)
            Next j
        End If
    Next i

    ' 結果の表示
    MsgBox "最短距離: " & minDistance
    ' 最適ルートの表示
    Dim routeString As String
    For i = 1 To numCities
        routeString = routeString & bestRoute(i) & " -> "
    Next i
    routeString = Left(routeString, Len(routeString) - 4)
    MsgBox "最適ルート: " & routeString
End Sub

このコードでは、generatePermutationsという関数を使って順列を生成しています。この関数は別途実装する必要があります。全検索は計算時間がかかるため、都市の数が多い場合は、他のアルゴリズムを検討する必要があります。

3.2 遺伝的アルゴリズム

遺伝的アルゴリズム（Genetic Algorithm、GA）は、生物の進化の過程を模倣した最適化手法です。巡回セールスマン問題のような複雑な問題に対して、効率的に解を求めることができます。GAは、以下のステップで進みます。

初期個体の生成: ランダムなルートを複数生成します。
評価: 各ルートの距離を計算し、評価します。
選択: 評価の高いルート（親）を選択します。
交叉: 選択された親から新しいルート（子）を生成します。
突然変異: 一部のルートにランダムな変更を加えます。
世代交代: 古いルートを新しいルートに置き換え、次の世代を生成します。
繰り返し: 評価、選択、交叉、突然変異、世代交代を繰り返し、最適解に近づけます。

VBAでGAを実装する場合、乱数生成、ルートの表現、交叉と突然変異の実装などが必要になります。


Sub 遺伝的アルゴリズム_TSP()
    Dim cities() As Integer
    Dim numCities As Integer
    Dim populationSize As Integer
    Dim generation As Integer
    Dim i As Integer, j As Integer
    Dim routes()() As Integer
    Dim distances() As Double
    Dim bestRoute() As Integer
    Dim minDistance As Double
    Dim currentDistance As Double
    Dim parent1 As Integer, parent2 As Integer
    Dim crossoverPoint As Integer
    Dim temp As Integer

    ' 都市の数
    numCities = 10
    ' 個体数
    populationSize = 100
    ' 世代数
    generation = 1000

    ' 都市の番号を配列に格納
    ReDim cities(1 To numCities)
    For i = 1 To numCities
        cities(i) = i
    Next i

    ' ルートと距離の初期化
    ReDim routes(1 To populationSize, 1 To numCities)
    ReDim distances(1 To populationSize)

    ' 初期個体の生成
    For i = 1 To populationSize
        routes(i, ) = generateRandomRoute(cities)
        distances(i) = calculateRouteDistance(routes(i, ), numCities)
    Next i

    ' 世代ごとの処理
    For i = 1 To generation
        ' 評価
        For j = 1 To populationSize
            distances(j) = calculateRouteDistance(routes(j, ), numCities)
        Next j

        ' 最小距離の更新
        minDistance = Application.WorksheetFunction.Min(distances)
        bestRoute = routes(Application.WorksheetFunction.Match(minDistance, distances, 0), )

        ' 選択、交叉、突然変異
        Dim nextRoutes() As Integer
        ReDim nextRoutes(1 To populationSize, 1 To numCities)
        For j = 1 To populationSize
            ' 選択
            parent1 = selectParent(distances)
            parent2 = selectParent(distances)

            ' 交叉
            crossoverPoint = Int(Rnd * (numCities - 2)) + 1
            For k = 1 To crossoverPoint
                nextRoutes(j, k) = routes(parent1, k)
            Next k
            For k = crossoverPoint + 1 To numCities
                nextRoutes(j, k) = routes(parent2, k)
            Next k

            ' 突然変異
            If Rnd < 0.05 Then ' 突然変異率
                Dim city1 As Integer, city2 As Integer
                city1 = Int(Rnd * (numCities - 1)) + 1
                city2 = Int(Rnd * (numCities - 1)) + 1
                temp = nextRoutes(j, city1)
                nextRoutes(j, city1) = nextRoutes(j, city2)
                nextRoutes(j, city2) = temp
            End If
        Next j

        ' 世代交代
        routes = nextRoutes
    Next i

    ' 結果の表示
    MsgBox "最短距離: " & minDistance
    ' 最適ルートの表示
    Dim routeString As String
    For i = 1 To numCities
        routeString = routeString & bestRoute(i) & " -> "
    Next i
    routeString = Left(routeString, Len(routeString) - 4)
    MsgBox "最適ルート: " & routeString
End Sub

このコードでは、generateRandomRoute、calculateRouteDistance、selectParentといった関数を別途実装する必要があります。遺伝的アルゴリズムは、全検索に比べて計算時間が大幅に短縮され、より現実的な方法です。

3.3 その他のアルゴリズム

巡回セールスマン問題を解くためのアルゴリズムは、他にもいくつか存在します。例えば、

最近傍法: 現在地から最も近い都市を順番に選んでいく方法。
2-opt法: ルートの一部を入れ替えることで、距離を短くする方法。
3-opt法: 2-opt法を拡張したもので、より複雑なルートの入れ替えを行う方法。

これらのアルゴリズムは、遺伝的アルゴリズムよりも単純で、実装も比較的容易です。問題の規模や要求される精度に応じて、適切なアルゴリズムを選択することが重要です。

4. 距離計算とルートの評価

ルートが生成されたら、各ルートの総距離を計算し、評価する必要があります。これは、各都市間の距離を計算し、それらを合計することで行います。


Function calculateRouteDistance(route() As Integer, numCities As Integer) As Double
    Dim distance As Double
    Dim i As Integer

    distance = 0
    For i = 1 To numCities - 1
        distance = distance + CalculateDistance( _
            Cells(route(i), 2), Cells(route(i), 3), _
            Cells(route(i + 1), 2), Cells(route(i + 1), 3))
    Next i
    distance = distance + CalculateDistance( _
        Cells(route(1), 2), Cells(route(1), 3), _
        Cells(route(numCities), 2), Cells(route(numCities), 3))

    calculateRouteDistance = distance
End Function

5. 最適ルートの特定と結果の表示

すべてのルートの距離を計算したら、最も短い距離のルートを特定し、結果を表示します。Excelのセルに結果を表示したり、グラフでルートを可視化することもできます。


Sub 表示_TSP()
    ' 結果の表示
    MsgBox "最短距離: " & minDistance
    ' 最適ルートの表示
    Dim routeString As String
    For i = 1 To numCities
        routeString = routeString & bestRoute(i) & " -> "
    Next i
    routeString = Left(routeString, Len(routeString) - 4)
    MsgBox "最適ルート: " & routeString

    ' 結果をExcelシートに表示
    Cells(1, 6).Value = "最短距離: " & minDistance
    Cells(2, 6).Value = "最適ルート: " & routeString
End Sub

6. プログラミングスキルをキャリアアップに活かす

VBAを使った巡回セールスマン問題の解決は、プログラミングスキルを向上させるだけでなく、キャリアアップにも繋がる可能性があります。以下に、具体的な活用例と、キャリアアップのためのヒントを紹介します。

6.1 業務効率化と自動化

巡回セールスマン問題の解決を通じて得られたプログラミングスキルは、日々の業務効率化に役立ちます。例えば、

データ分析の自動化: Excel VBAを使って、データの集計や分析を自動化し、作業時間を短縮できます。
レポート作成の効率化: 定型的なレポートの作成を自動化し、人的ミスを減らし、正確性を向上させます。
業務プロセスの改善: 複雑な業務プロセスをVBAで自動化し、業務全体の効率を改善します。

これらのスキルは、あなたの職場での評価を向上させ、昇進や昇給に繋がる可能性があります。

6.2 キャリアチェンジと副業

プログラミングスキルは、キャリアチェンジや副業にも役立ちます。例えば、

データ分析の仕事: VBAで培ったデータ分析スキルを活かして、データアナリストやデータサイエンティストへのキャリアチェンジを目指せます。
Webアプリケーション開発: VBAの知識を基盤に、Webアプリケーション開発のスキルを習得し、副業としてWebサイト制作やシステム開発に携わることも可能です。
フリーランス: プログラミングスキルを活かして、フリーランスとして独立し、自分のペースで仕事をする道も開けます。

プログラミングスキルは、あなたのキャリアの可能性を大きく広げます。

6.3 スキルアップのための学習方法

プログラミングスキルをさらに向上させるためには、継続的な学習が不可欠です。以下に、スキルアップのための学習方法を紹介します。

オンライン学習: Udemy、Coursera、Udacityなどのオンラインプラットフォームで、VBAや他のプログラミング言語を学ぶことができます。
書籍: VBAに関する書籍や、プログラミングの基礎を学ぶための書籍を読み、知識を深めます。
実践的なプロジェクト: 実際にVBAを使って、業務効率化ツールや、Webアプリケーションを作成することで、実践的なスキルを習得できます。
コミュニティへの参加: プログラミングに関するコミュニティに参加し、他のプログラマーと交流することで、情報交換やモチベーション維持に繋がります。

継続的な学習を通じて、プログラミングスキルを向上させ、キャリアアップを実現しましょう。

もっとパーソナルなアドバイスが必要なあなたへ

この記事では一般的な解決策を提示しましたが、あなたの悩みは唯一無二です。
AIキャリアパートナー「あかりちゃん」が、LINEであなたの悩みをリアルタイムに聞き、具体的な求人探しまでサポートします。

今すぐLINEで「あかりちゃん」に無料相談する

無理な勧誘は一切ありません。まずは話を聞いてもらうだけでも、心が軽くなるはずです。

7. 成功事例

実際に、VBAやプログラミングスキルを活かしてキャリアアップを実現した人々の事例を紹介します。

7.1 業務効率化による昇進

ある営業職の社員は、VBAを使って顧客管理システムを構築し、営業活動の効率を大幅に改善しました。これにより、彼は売上を向上させ、上司から高い評価を得て、昇進を果たしました。彼の事例は、プログラミングスキルが業務効率化に役立ち、キャリアアップに繋がることを示しています。

7.2 キャリアチェンジによる成功

ある事務職の女性は、VBAを独学で学び、データ分析スキルを習得しました。その後、データ分析の仕事に転職し、キャリアチェンジに成功しました。彼女の事例は、プログラミングスキルが新しいキャリアへの道を開くことを示しています。

7.3 副業による収入アップ

ある会社員は、VBAやWeb開発のスキルを活かして、副業でWebサイト制作やシステム開発の仕事を受注しました。これにより、彼は収入を増やし、経済的な余裕を得ることができました。彼の事例は、プログラミングスキルが副業収入に繋がり、自己実現を可能にすることを示しています。

8. 専門家からのアドバイス

キャリア支援の専門家からのアドバイスを紹介します。

目標設定: まずは、自分がどのようなキャリアを築きたいのか、明確な目標を設定しましょう。
スキル習得: 目標達成に必要なスキルを特定し、計画的に学習を進めましょう。
情報収集: キャリアに関する情報を収集し、最新の動向を把握しましょう。
ネットワーキング: 積極的に人脈を広げ、キャリアに関する情報を共有しましょう。
自己PR: 自分のスキルや経験を効果的にアピールできるように、自己PRを磨きましょう。

専門家のアドバイスを参考に、計画的にキャリアアップを進めましょう。

9. まとめ

この記事では、Excel VBAを使った巡回セールスマン問題の解決方法と、プログラミングスキルをキャリアアップに活かすための方法について解説しました。巡回セールスマン問題をVBAで解くことは、プログラミングスキルを向上させるだけでなく、業務効率化、キャリアチェンジ、副業など、様々な可能性を広げます。この記事を参考に、プログラミングスキルを習得し、あなたのキャリアアップを実現してください。

10. 付録: VBAコードサンプル

巡回セールスマン問題を解くためのVBAコードサンプルを以下に示します。このコードは、全検索と遺伝的アルゴリズムの基本的な実装例です。実際の問題に合わせて、コードを修正・拡張してください。


' 距離計算関数
Function CalculateDistance(x1 As Double, y1 As Double, x2 As Double, y2 As Double) As Double
    CalculateDistance = Sqr((x2 - x1) ^ 2 + (y2 - y1) ^ 2)
End Function

' 全検索用関数（順列生成）
Function generatePermutations(arr() As Integer) As Variant
    Dim n As Integer, i As Integer, j As Integer
    Dim temp As Integer
    Dim result() As Integer

    n = UBound(arr) - LBound(arr) + 1
    ReDim result(1 To n, 1 To Application.WorksheetFunction.Fact(n))
    Dim k As Integer
    k = 1

    ' 初期状態
    For i = 1 To n
        result(1, k) = arr(i)
    Next i
    k = k + 1

    ' 順列生成
    Dim fact As Integer
    fact = 1
    For i = 2 To n
        fact = fact * i
    Next i

    Dim p As Integer
    For i = 1 To fact - 1
        ' 逆順列生成
        Dim c As Integer
        c = n - 1
        Do While result(c, i) > result(c + 1, i)
            c = c - 1
        Loop
        Dim d As Integer
        d = n
        Do While result(c, i) > result(d, i)
            d = d - 1
        Loop

        ' 交換
        temp = result(c, i)
        result(c, i) = result(d, i)
        result(d, i) = temp

        ' 反転
        Dim left As Integer
        left = c + 1
        Dim right As Integer
        right = n
        Do While left < right
            temp = result(left, i)
            result(left, i) = result(right, i)
            result(right, i) = temp
            left = left + 1
            right = right - 1
        Loop
    Next i
    generatePermutations = result
End Function

' 遺伝的アルゴリズム用関数（ランダムルート生成）
Function generateRandomRoute(cities() As Integer) As Integer()
    Dim numCities As Integer
    Dim i As Integer, j As Integer
    Dim temp As Integer
    Dim randomIndex As Integer
    Dim route() As Integer

    numCities = UBound(cities)
    ReDim route(1 To numCities)
    For i = 1 To numCities
        route(i) = cities(i)
    Next i

    For i = 1 To numCities
        randomIndex = Int((numCities - i + 1) * Rnd + 1)
        temp = route(i)
        route(i) = route(i + randomIndex - 1)
        route(i + randomIndex - 1) = temp
    Next i

    generateRandomRoute = route
End Function

' 遺伝的アルゴリズム用関数（ルート距離計算）
Function calculateRouteDistance(route() As Integer, numCities As Integer) As Double
    Dim distance As Double
    Dim i As Integer

    distance = 0
    For i = 1 To numCities - 1
        distance = distance + CalculateDistance( _
            Cells(route(i), 2), Cells(route(i), 3), _
            Cells(route(i + 1), 2), Cells(route(i + 1), 3))
    Next i
    distance = distance + CalculateDistance( _
        Cells(route(1), 2), Cells(route(1), 3), _
        Cells(route(numCities), 2), Cells(route(numCities), 3))

    calculateRouteDistance = distance
End Function

' 遺伝的アルゴリズム用関数（親の選択）
Function selectParent(distances() As Double) As Integer
    Dim total As Double, i As Integer
    Dim probabilities() As Double
    Dim randomNumber As Double
    Dim selectedParent As Integer

    total = Application.WorksheetFunction.Sum(distances)
    ReDim probabilities(1 To UBound(distances))
    For i = 1 To UBound(distances)
        probabilities(i) = distances(i) / total
    Next i

    randomNumber = Rnd
    selectedParent = 1
    Dim cumulativeProbability As Double
    cumulativeProbability = probabilities(1)
    Do While cumulativeProbability < randomNumber And selectedParent < UBound(distances)
        selectedParent = selectedParent + 1
        cumulativeProbability = cumulativeProbability + probabilities(selectedParent)
    Loop

    selectParent = selectedParent
End Function

これらのコードサンプルは、あくまで基本的な実装例です。実際の問題に合わせて、コードを修正・拡張し、より効率的なアルゴリズムを検討してください。また、エラー処理や、ユーザーインターフェースの改善なども行うことで、より使いやすいツールを作成できます。

コメントするコメントをキャンセル

お役立ちコンテンツ

転職体験談

転職ノウハウ

転職コラム

コミュ力が、
最強の武器
になる。

まずは登録