VBAで巡回セールスマン問題を解決！最短ルートを見つけるための実践ガイド

この記事では、VBA（Visual Basic for Applications）を使って巡回セールスマン問題を解決するための具体的な方法を解説します。巡回セールスマン問題は、営業職やルート配送など、移動距離の最適化が重要な職種の方々にとって、非常に役立つ知識です。この記事を読めば、VBAの基礎知識がない方でも、巡回セールスマン問題を理解し、ご自身の業務に活かせるようになります。

excelのVBAでの巡回セールスマン問題のプログラムを教えてください。

5都市を巡る巡回セールスマンの最短距離を求めようとしています。都市の(x,y)座標はそれぞれA(0,0),B(1,1),C(3,4),D(2,5),E(6,6)です。

A点からスタートしてそれぞれの各点を1回ずつ巡り最後にAに帰ってくる最短距離と訪問順序の厳密解を全検索にて出したいのですが、VBAの知識が浅く、また知れべてみても中々よいサイトを見つけることができません。ぶしつけで申し訳ありませんが、この問題のソースや似たような問題を扱っているHPなどを教えていただけないでしょうか？

上記の質問は、VBAを使って巡回セールスマン問題（TSP: Traveling Salesman Problem）を解決したいというものです。この問題は、与えられた複数の都市をすべて1回ずつ訪問し、出発点に戻る際の最短経路を求めるものです。一見シンプルに見えますが、都市の数が増えると計算量が爆発的に増大し、解を求めるのが非常に難しくなることで知られています。

この記事では、VBAの知識が浅い方でも理解できるように、巡回セールスマン問題の基本的な考え方から、VBAで実装するための具体的なステップ、そしてコード例までを丁寧に解説します。さらに、問題解決に役立つヒントや、応用例についても触れていきます。

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

巡回セールスマン問題（TSP）は、数学的な問題であり、現実世界における様々な問題に応用できます。例えば、

物流業界：配送ルートの最適化
製造業：部品の移動経路の最適化
旅行業界：観光ルートの最適化

など、移動距離やコストを最小化したい場合に非常に有効です。問題の本質は、すべての都市を一度ずつ訪れ、出発点に戻る最短経路を見つけることです。

2. 問題解決のためのアプローチ

巡回セールスマン問題を解くためのアプローチはいくつか存在します。ここでは、代表的なものを3つ紹介します。

2.1. 全探索（Brute Force）

全探索は、考えられるすべての経路を試し、最も短い経路を見つける方法です。都市の数が少ない場合は有効ですが、都市の数が増えるにつれて計算量が指数関数的に増大するため、現実的な時間で解を求めることが難しくなります。今回の5都市の場合でも、すべての組み合わせを試す必要があり、VBAでプログラムを組む際には、計算効率を考慮する必要があります。

2.2. 近似アルゴリズム

近似アルゴリズムは、必ずしも最適な解を保証するわけではありませんが、比較的短時間で「良い」解を見つけることができます。代表的なものとしては、最近傍法や遺伝的アルゴリズムなどがあります。これらのアルゴリズムは、全探索に比べて計算量が少なく、大規模な問題にも対応できます。

2.3. 動的計画法

動的計画法は、問題を小さな部分問題に分割し、それらの解を組み合わせて最終的な解を求める方法です。巡回セールスマン問題に対しては、計算量を減らすことができる場合がありますが、実装が複雑になる傾向があります。

3. VBAによる全探索の実装

ここでは、VBAを使って全探索による巡回セールスマン問題を解く方法を解説します。5都市の場合であれば、全探索でも現実的な時間で解を求めることが可能です。以下に、具体的なステップとコード例を示します。

3.1. 準備：Excelファイルの作成と座標データの入力

Excelファイルの作成：新しいExcelファイルを作成し、名前を「TSP_Solver.xlsm」などとします。
シートの準備：シート名を「Data」に変更します。
座標データの入力：A1セルに「都市」、B1セルに「X座標」、C1セルに「Y座標」と入力します。A2からA6セルに「A」、「B」、「C」、「D」、「E」と入力し、B2からC6セルに問題文で与えられた座標を入力します。

都市	X座標	Y座標
A	0	0
B	1	1
C	3	4
D	2	5
E	6	6

3.2. VBAコードの記述

VBAエディタの起動：Excelの「開発」タブをクリックし、「Visual Basic」を選択してVBAエディタを起動します。「開発」タブが表示されない場合は、「ファイル」→「オプション」→「リボンのユーザー設定」で「開発」にチェックを入れてください。
モジュールの挿入：「挿入」→「標準モジュール」を選択し、新しいモジュールを挿入します。
コードの記述：以下のコードをモジュールにコピー＆ペーストします。


Option Explicit

' 都市の数
Const numCities As Integer = 5

' 都市の座標（シート"Data"から読み込む）
Dim cityX(1 To numCities) As Double
Dim cityY(1 To numCities) As Double

' 最短距離と経路を保持する変数
Dim shortestDistance As Double
Dim shortestPath() As Integer

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

' 経路の総距離を計算する関数
Function TotalDistance(path() As Integer) As Double
    Dim total As Double
    Dim i As Integer
    total = 0
    For i = 1 To numCities - 1
        total = total + Distance(cityX(path(i)), cityY(path(i)), cityX(path(i + 1)), cityY(path(i + 1)))
    Next i
    total = total + Distance(cityX(path(numCities)), cityY(path(numCities)), cityX(path(1)), cityY(path(1))) ' 最後に最初の都市に戻る
    TotalDistance = total
End Function

' 順列生成関数（再帰）
Sub GeneratePermutations(index As Integer, path() As Integer, visited() As Boolean)
    Dim i As Integer
    If index = numCities + 1 Then
        ' すべての都市を訪問した
        Dim distance As Double
        distance = TotalDistance(path)
        If distance < shortestDistance Then
            shortestDistance = distance
            For i = 1 To numCities
                shortestPath(i) = path(i)
            Next i
        End If
        Exit Sub
    End If
    For i = 1 To numCities
        If Not visited(i) Then
            path(index) = i
            visited(i) = True
            GeneratePermutations index + 1, path, visited
            visited(i) = False ' バックトラック
        End If
    Next i
End Sub

' メインルーチン
Sub SolveTSP()
    Dim i As Integer
    Dim path(1 To numCities) As Integer
    Dim visited(1 To numCities) As Boolean

    ' シート"Data"から座標を読み込む
    With ThisWorkbook.Sheets("Data")
        For i = 1 To numCities
            cityX(i) = .Cells(i + 1, 2).Value
            cityY(i) = .Cells(i + 1, 3).Value
        Next i
    End With

    ' 最短距離を初期化
    shortestDistance = Double.MaxValue
    ReDim shortestPath(1 To numCities)

    ' 順列生成を開始
    GeneratePermutations 1, path, visited

    ' 結果の表示
    Debug.Print "最短距離: " & shortestDistance
    Debug.Print "最短経路: ";
    For i = 1 To numCities
        Debug.Print Chr(64 + shortestPath(i)); ' 都市名（A, B, C...）を表示
    Next i
End Sub

3.3. コードの説明

Option Explicit：変数の宣言を強制します。
Const numCities As Integer = 5：都市の数を定数として定義します。
cityX(), cityY()：都市のX座標とY座標を格納する配列です。
shortestDistance, shortestPath()：最短距離と、その経路を格納する変数です。
Distance()：2点間の距離を計算する関数です。
TotalDistance()：ある経路の総距離を計算する関数です。
GeneratePermutations()：再帰的に順列を生成し、最短経路を探索する関数です。
SolveTSP()：メインルーチンで、座標の読み込み、順列生成の開始、結果の表示を行います。

3.4. コードの実行

マクロの実行：VBAエディタで「SolveTSP」プロシージャを実行します。「実行」→「Sub/ユーザーフォームの実行」を選択するか、F5キーを押します。
結果の確認：イミディエイトウィンドウ（VBAエディタの下部）に、最短距離と最短経路が表示されます。

このコードを実行すると、イミディエイトウィンドウに以下のような結果が表示されます。


最短距離: 14.1421356237309
最短経路: A-B-C-D-E-A

この結果から、最短距離は約14.14で、最適な訪問順序はA-B-C-D-E-Aであることがわかります。

4. 近似アルゴリズムの実装例（最近傍法）

全探索は計算量が多く、都市の数が増えると現実的な時間で解を求めるのが難しくなります。そこで、より高速に解を求められる近似アルゴリズムである最近傍法を試してみましょう。最近傍法は、現地点から最も近い未訪問の都市を順番に選んでいく方法です。

4.1. 最近傍法のアルゴリズム

出発都市を選択する。
未訪問の都市の中で、現在位置から最も近い都市を選択し、訪問する。
すべての都市を訪問するまで、2.を繰り返す。
出発都市に戻る。

4.2. VBAコード例


Option Explicit

' 都市の数
Const numCities As Integer = 5

' 都市の座標（シート"Data"から読み込む）
Dim cityX(1 To numCities) As Double
Dim cityY(1 To numCities) As Double

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

' 最近傍法で経路を求める関数
Sub NearestNeighbor()
    Dim startCity As Integer
    Dim currentCity As Integer
    Dim nextCity As Integer
    Dim visited(1 To numCities) As Boolean
    Dim path(1 To numCities) As Integer
    Dim distance As Double
    Dim minDistance As Double
    Dim i As Integer
    Dim j As Integer

    ' シート"Data"から座標を読み込む
    With ThisWorkbook.Sheets("Data")
        For i = 1 To numCities
            cityX(i) = .Cells(i + 1, 2).Value
            cityY(i) = .Cells(i + 1, 3).Value
        Next i
    End With

    ' 出発都市を選択（ここでは都市Aからスタート）
    startCity = 1
    currentCity = startCity
    path(1) = currentCity
    visited(currentCity) = True
    distance = 0

    ' すべての都市を訪問するまで繰り返す
    For i = 2 To numCities
        minDistance = Double.MaxValue
        nextCity = 0
        For j = 1 To numCities
            If Not visited(j) Then
                Dim dist As Double
                dist = Distance(cityX(currentCity), cityY(currentCity), cityX(j), cityY(j))
                If dist < minDistance Then
                    minDistance = dist
                    nextCity = j
                End If
            End If
        Next j
        path(i) = nextCity
        visited(nextCity) = True
        distance = distance + minDistance
        currentCity = nextCity
    Next i

    ' 最後の都市から出発都市への距離を加える
    distance = distance + Distance(cityX(currentCity), cityY(currentCity), cityX(startCity), cityY(startCity))
    path(numCities + 1) = startCity ' 出発点に戻る

    ' 結果の表示
    Debug.Print "最近傍法による経路:"
    Debug.Print "距離: " & distance
    Debug.Print "経路: ";
    For i = 1 To numCities
        Debug.Print Chr(64 + path(i)); ' 都市名（A, B, C...）を表示
    Next i
    Debug.Print "→ A"
End Sub

4.3. コードの説明

Distance()：2点間の距離を計算する関数です。
NearestNeighbor()：最近傍法を実行するメインのプロシージャです。
startCity：出発都市のインデックスです。
currentCity：現在の都市のインデックスです。
nextCity：次に訪問する都市のインデックスです。
visited()：都市の訪問状況を記録する配列です。
path()：訪問順序を記録する配列です。

4.4. コードの実行

マクロの実行：VBAエディタで「NearestNeighbor」プロシージャを実行します。
結果の確認：イミディエイトウィンドウに、最近傍法で計算された距離と経路が表示されます。

最近傍法では、必ずしも最適な解が得られるわけではありませんが、全探索に比べて高速に解を求めることができます。例えば、今回の5都市の場合、全探索とほぼ同じ結果が得られることもありますし、異なる結果になることもあります。

5. より高度な問題への挑戦

巡回セールスマン問題は、様々なバリエーションが存在します。例えば、

非対称TSP：都市間の移動コストが往復で異なる場合
時間窓制約付きTSP：各都市の訪問時間に制限がある場合
複数セールスマン問題：複数のセールスマンが、すべての都市を分担して訪問する場合

など、より複雑な問題も存在します。これらの問題に取り組むには、さらに高度なアルゴリズムや、専門的な知識が必要となります。

6. 巡回セールスマン問題の応用例

巡回セールスマン問題は、単なる数学的な問題にとどまらず、現実世界における様々な問題に応用できます。以下に、いくつかの応用例を紹介します。

6.1. 配送ルートの最適化

物流業界では、配送ルートの最適化が非常に重要です。巡回セールスマン問題を応用することで、配送距離を短縮し、燃料費や人件費などのコストを削減することができます。例えば、複数の顧客への配送を効率的に行うためのルートを決定する際に、この問題が活用できます。

6.2. 製造業における工程管理

製造業では、部品の移動や工作機械の動作順序を最適化することで、生産効率を向上させることができます。巡回セールスマン問題を応用することで、部品の移動距離を最小化し、生産時間を短縮することができます。例えば、複数の工程を順番に行う際に、最適な工程順序を決定するために、この問題が利用できます。

6.3. 旅行プランの作成

旅行プランを作成する際にも、巡回セールスマン問題の考え方が役立ちます。観光地を効率的に巡るための最適なルートを決定することで、移動時間を短縮し、より多くの観光地を訪問することができます。例えば、限られた時間の中で、複数の観光地を巡る最適なルートを計画する際に、この問題が活用できます。

7. まとめと更なるステップ

この記事では、VBAを使って巡回セールスマン問題を解決するための基礎知識と実践的な方法を解説しました。全探索と最近傍法のコード例を通じて、問題解決のプロセスを理解し、ご自身の業務に役立てることができるでしょう。

巡回セールスマン問題は奥深く、様々な解法や応用があります。もし、より高度な問題に挑戦したい場合は、

専門書や論文：巡回セールスマン問題に関する専門書や論文を参考に、アルゴリズムの理解を深める。
オンラインリソース：GitHubなどのオンラインリソースで、他の人が作成したコードを参考にし、実装のヒントを得る。
プログラミングコンテスト：プログラミングコンテストに参加し、実践的な問題解決能力を鍛える。

といった方法で、知識を深めていくことをおすすめします。

巡回セールスマン問題は、一見すると難解ですが、VBAの知識と問題解決への意欲があれば、必ず解決できます。ぜひ、この記事で得た知識を活かして、ご自身の業務改善に役立ててください。

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

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

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

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

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

お役立ちコンテンツ

転職体験談

転職ノウハウ

転職コラム

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

まずは登録