カテゴリー
SugiBlog Webエンジニアのためのお役立ちTips

ルート検索 最適経路

この記事は最終更新日から1年以上経過しています。

営業の仕事をしていると、複数の場所を効率よく回りたい、という要求が出てくるかと思います。
GoogleMap APIを利用すれば出発地点、到着地点、8ヶ所の経由地を指定し、効率よく回るルートを検索することができます。
所謂巡回セールスマン問題を踏まえた結果を返してくれます。
その際はリクエストプロパティの「optimizeWaypoints」にtrueを設定しておきます。

しかし、経由地8ヶ所以上の検索はできません。
費用が発生してよいならば、23ヶ所まで検索できるようです。
では、費用をかけずに8ヶ所以上検索したい場合はどうしたらよいでしょうか？

どうにか自前でできないかと色々調べました。
巡回セールスマン問題、組み合わせ最適化、パス表現法、ナップサック問題、欲張り法、遺伝的アルゴリズム等々。

巡回セールスマン問題、組み合わせ最適化を踏まえた最適ルートの検索で、何通りのルートを計測すればいいかと言いますと、以下の通り

n!/2n

nを10とすると(10×9×8×7×6×5×4×3×2×1)÷(2×10)で181,440通りとなります。

更にnが増加すると莫大な計算量になってしまうので、日常のプログラムとして使用するには
現実的ではありませんし、スーパーコンピューターでも100億年かかるという計算量になってしまいます。

…無理です。。。

何か打開策はないかと、物理の仕事（仕事率）も応用してみようと試みましたが、力(N)に当たるものが
ないので、比較する値としては単純な速さとなってしまうので最適な結果は得られず断念。

最終的に、遺伝的アルゴリズムを見ていると、ルートをランダムに作成するしかないのか、
という結論に至り、研究は終了しました。

というわけで、PHPとJavaScriptを使いプログラムを作成しました。

※注意！
計測結果はその都度変わる可能性があり、常に結果は変動します。
このプログラムはその都度計測した距離とランダムなルートによる総移動距離が最も短いルートを最適ルートとして返します。
算出された最適ルートが最も効率のよいルートであるとは限りませんので予めご了承ください。

まず、HTMLとCSSファイルを作成します。
CSSは特に必須ではありませんので無しでも結構です。
【route_search.html】

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>ルート検索</title>

<link rel="stylesheet" type="text/css" href="./route_search.css">

<script src="http://maps.google.com/maps/api/js?sensor=false" type="text/javascript"></script>
<script src="./route_search_ajax.js" type="text/javascript" charset="utf-8"></script>
<script src="./route_search.js" type="text/javascript" charset="utf-8"></script>

</head>
<body>

<h1>ルート検索</h1>

<hr>

<input type="radio" id="highway1" name="highway" value="1" checked="checked" onclick="highway_change(this.value);"><label for="highway1">高速を利用する</label>
<input type="radio" id="highway2" name="highway" value="2" onclick="highway_change(this.value);"><label for="highway2">高速をなるべく利用しない</label><br>

処理間隔：
<input type="radio" id="ms0" name="sleep_ms" value="0" onclick="sleep_ms_change(this.value);"><label for="ms0">0秒</label>
<input type="radio" id="ms1500" name="sleep_ms" value="1500" checked="checked" onclick="sleep_ms_change(this.value);"><label for="ms1500">1.5秒</label>
<input type="radio" id="ms3000" name="sleep_ms" value="3000" onclick="sleep_ms_change(this.value);"><label for="ms3000">3秒</label>
<input type="radio" id="ms6000" name="sleep_ms" value="6000" onclick="sleep_ms_change(this.value);"><label for="ms6000">6秒</label><br>

<input type="button" id="exec" value="計測開始" onclick="execute();">

<hr>

<h3>計測結果を反映した順序</h3>

<div id="order"></div>

<hr>

<h3>計測結果</h3>

<div id="status"></div>

<div id="res"></div>

</body>
</html>

【route_search.css】

@charset "utf-8";

body
{
    font-family: sans-serif, "MS Pゴシック";
    font-size: 80%;
    letter-spacing: 0.4px;
    line-height: 1.5em;
}

hr
{
    border: 0px;
    height: 1px;
    color: #cbcbcb;
    background-color: #cbcbcb;
}

次に、ランダムルートを作成するPHPを作成します。

生成するランダムルートの数は、出発地点と到着地点を除いた数、つまり経由地の数を
デクリメント（1ずつ減算）しながら加算した数としています。
計測するルート数の適当な値を得るために、階乗の乗算を加算に置き換えた方法ですので、公式な方法ではありません。
【route_search.php】

<?php

// ヘッダー
header("Content-Type: text/html; charset=utf-8\n");

// 出発地点、到着地点を含む地点数パラメータ受け取り
$n = $_POST["n"];


// 出発地点、到着地点を除くインデックスの配列を作成
for($i = 1; $i < ($n - 1); $i++) {
    $num_list[] = $i;
}


$start_spot = 0;      //出発地点
$end_spot   = $n - 1; //到着地点


// 生成するランダムルートの数を算出
// n = 10とすると 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36
$n = count($num_list); //経由地の件数
$m = $n;
$n = 0;
for($j = 0; $j < count($num_list); $j++) {
    $n += $m;
    $m--;
}


// ランダムルートを生成
for($i = 0; $i < $n; $i++) {
    shuffle($num_list); //配列をランダムに並べ替え
    echo "R[".$i."] = [ ".$start_spot.", ".@implode(", ", $num_list).", ".$end_spot." ];\n";
}

?>

例えば$nに適当な値を代入し、このPHPプログラムにアクセスすれば
どういったルートが作成されるかを確認することができます。

計測するルートを極端に削減しているとはいえ、20件以下にすることをお勧めします。

PHPプログラムからランダムルート情報を取得するAjaxプログラムを作成
【route_search_ajax.js】


// Ajaxクラス
var myAjax = {

    make: function()
    {
        var xmlHttp;

        if(navigator.userAgent.indexOf("Mac") != -1 || navigator.userAgent.indexOf("Opera") != -1 || navigator.userAgent.indexOf("Firefox") != -1 || navigator.userAgent.indexOf("Chrome") != -1)
        {
            // Ajaxクラスのインスタンス生成(Mac用)
            xmlHttp = new XMLHttpRequest();
        }
        else
        {
            // Ajaxクラスのインスタンス生成(Win用)
            xmlHttp = new ActiveXObject("Microsoft.XMLHTTP");
        }

        return xmlHttp;
    },

    post: function(url, param)
    {
        var ajax = this.make();

        ajax.open("POST", url, true);
        ajax.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded; charset=UTF-8');
        ajax.onreadystatechange = function()
        {
            if(ajax.readyState == 4)
            {
                var data = ajax.responseText;
                eval(data);
            }
        }
        ajax.send(param);
    }

}

わざわざAjaxを使っているのは、プログラムとHTMLが混在しないようにするためです。

さて、いよいよ大詰めです。
GoogleMap APIを利用して距離を計測し、最適ルートを検索するJavaScriptを作成していきます。
【route_search.js】
まずは初期設定から

var number = []; //名称配列
var G      = []; //座標配列

//各地点を判別するための名称の配列を作成
number = ["新大阪駅（出発地点）", "JR大阪駅", "地下鉄なんば駅", "地下鉄天王寺駅", "USJ", "阪急三ノ宮駅（到着地点）"];

//出発地点、到着地点、経由地を配列に追加します
G.push(new google.maps.LatLng(34.73307796637832,  135.4985475540161));  //新大阪駅（出発地点）
G.push(new google.maps.LatLng(34.70203587328282,  135.4947924613952));  //JR大阪駅
G.push(new google.maps.LatLng(34.667081944219476, 135.50030708312988)); //地下鉄なんば駅
G.push(new google.maps.LatLng(34.64704868826271,  135.5146837234497));  //地下鉄天王寺駅
G.push(new google.maps.LatLng(34.666499547861335, 135.43202877044678)); //USJ
G.push(new google.maps.LatLng(34.69427352939781,  135.19470691680908)); //阪急三ノ宮駅（到着地点）

var sleep_ms = 1500; //処理間隔(ms)

var N = []; //距離配列
var i = 0;  //距離配列用の開始ポインタ
var j = 0;  //距離配列用の終了ポインタ

var route = []; //最適ルート配列
route.push(0);  //出発地点を最適ルートに追加

var D = []; //合計距離用配列


//ランダムルート配列を作成
var R = [];
myAjax.post("route_search.php", "n=" + number.length);

// Googleルート検索用のリクエストプロパティ
var request = {
    origin: null,      //出発地点
    destination: null, //到着地点

    // DRIVING=自動車,BICYCLING=自転車,TRANSIT=電車,WALKING=徒歩
    travelMode: google.maps.DirectionsTravelMode.DRIVING,

    avoidHighways: false, //trueの場合、ルートサービスで可能な場合は高速道路を避けるように指示します。省略可能
    avoidTolls: false,    //trueの場合、ルートサービスで可能な場合は有料道路を避けるように指示します。省略可能

    provideRouteAlternatives: false, //代替ルートを提供するかどうかを指定します。省略可能

    //距離を表示する際に使用される、優先単位系。デフォルトでは、出発地点の国で使用される単位系です。
    //IMPERIAL=距離をヤード法の単位で表すよう指定,METRIC=距離をメートル法の単位で表すよう指定
    unitSystem: google.maps.UnitSystem.METRIC
};

高速利用と処理間隔の切り替え関数

//高速利用切り替え
function highway_change(value)
{
    switch (value) {
        case "1":
            request.avoidHighways = false;
            request.avoidTolls = false;
            break;

        case "2":
            request.avoidHighways = true;
            request.avoidTolls = true;
            break;
    }
}

//Googleへのリクエスト間隔設定
function sleep_ms_change(ms)
{
    sleep_ms = ms;
}

GoogleMap APIを利用した距離計算のメソッド

function getDistance()
{
    var directionsService = new google.maps.DirectionsService();

    request.origin      = G[i];
    request.destination = G[j];

    directionsDisplay = new google.maps.DirectionsRenderer();

    directionsService.route(request, function(response, status) {
        if (status == google.maps.DirectionsStatus.OK) {

            if ( i < (G.length - 2 ) ) {
                document.getElementById("status").innerHTML = "計測中... あと" + (G.length - i - 1) + "件 Google Direction Service Response: " + status;
            } else {
                document.getElementById("status").innerText = "";
            }

            directionsDisplay.setDirections(response);

            currentDirections = directionsDisplay.getDirections();

            var route = currentDirections.routes[0];

            for(var n = 0; n < route.legs.length; n++)
            {
                dur = route.legs[n].duration.value;
                dis = route.legs[n].distance.value;
            }

            if ( typeof N[i] == "undefined") N[i] = [];
            if ( typeof N[j] == "undefined") N[j] = [];

            N[i][j] = { duration: dur, distance: dis };
            N[j][i] = { duration: dur, distance: dis };

            //計測状況を表示
            //{
                document.getElementById("res").innerHTML += number[i] + "～" + number[j];
                document.getElementById("res").innerHTML += " （時間：" + Math.ceil(dur/60) + "分, 距離：" + dis/1000 + "km）<br>";
            //}

            calc(); //次の計測へ

        } else if (status == google.maps.DirectionsStatus.OVER_QUERY_LIMIT) {

            if(confirm("短期間にリクエストの制限回数を超えました。\n続行しますか？\n\n何度もこのメッセージが表示される場合は、件数が多過ぎる可能性があります。\n処理間隔を変えて実行すると正常に実行できる場合があります。")) {
                id = setTimeout("calc()", sleep_ms); //計測を待機時間後に続行
            } else {
                document.getElementById("res").innerHTML    = "";
                document.getElementById("order").innerHTML  = "";
                document.getElementById("status").innerText = "";

                document.getElementById("exec").disabled = "";
            }

        } else if (status == google.maps.DirectionsStatus.ZERO_RESULTS) {

            //alert("出発地と目的地の間にルートが見つかりませんでした。");

            //計測状況を表示
            //{
                document.getElementById("res").innerHTML += number[i] + "～" + number[j] + " 計測不能<br>";
            //}

            calc(); //次の計測へ

        }

    });

};

各地点の相互間距離を全て計測するためのループして呼ばれる関数

function calc()
{

    if ( i < (G.length - 2) ) {

        if ( j < (G.length - 1) ) {

            //開始地点は同じで、別の地点への距離を計測

            j++; //距離配列用の終了ポインタを次へ

            id = setTimeout("getDistance()", sleep_ms); //計測を待機時間後に実行

        } else {

            //距離計測の開始地点を次へ移動

            i++;       //距離配列用の開始ポインタを１つ次へ
            j = i + 1; //距離配列用の終了ポインタを開始ポインタの次へ

            id = setTimeout("getDistance()", sleep_ms); //計測を待機時間後に実行

        }

    } else {

        //全て計測し終わったら結果を解析
        response_analyze();

    }

}

ルート検索の実行を開始する関数

function execute()
{
    document.getElementById("res").innerHTML   = "";
    document.getElementById("order").innerHTML = "";

    document.getElementById("exec").disabled = "disabled";

    calc();
}

結果処理 ランダムルートの総移動距離による判定

function response_analyze()
{
    var d;                  //総移動距離
    var better = -1;        //最短移動距離
    var better_index;       //最短ルートのインデックス
    var better_number = []; //最短ルートの名称配列

    document.getElementById("res").innerHTML += "<hr>";
    document.getElementById("res").innerHTML += R.length + "通りのルートを計測します。<br>";

    for(var p = 0; p < R.length; p++) { //ランダムルートの数だけ繰り返し

        d = 0; //総移動距離を初期化

        document.getElementById("res").innerHTML += "<hr>";
        document.getElementById("res").innerHTML += "ルート" + (p + 1) + ": " + R[p] + "<br>";

        for(var q = 0; q < (R[p].length - 1); q++) { //ルート内の地点数だけ繰り返し

            document.getElementById("res").innerHTML += R[p][q] + "～" + R[p][(q+1)] + "";
            document.getElementById("res").innerHTML += "(" + N[R[p][q]][R[p][(q+1)]].distance + ")";

            d += N[R[p][q]][R[p][(q+1)]].distance; //移動距離を加算

        }

        document.getElementById("res").innerHTML += "<br>";
        document.getElementById("res").innerHTML += "合計距離：" + d + "m<br>";

        D[p] = d/1000; //合計距離を配列に追加

    }

    //ランダムルートの内、最短ルートを探す
    for(var q = 0; q < D.length; q++) {

        if(better == -1 || D[q] < better) {
            better = D[q];    //最短距離
            better_index = q; //最短距離ルートのインデックス
        }

    }

    //最短ルートの名称配列を作成
    for(var q = 0; q < R[better_index].length; q++) {
        better_number.push(number[R[better_index][q]]);
    }

    document.getElementById("order").innerHTML += "最短ルート：ルート" + (better_index + 1) + " （" + R[better_index] + "）<br>\n";
    document.getElementById("order").innerHTML += "[ " + better_number.join(" -> ") + " ]<br>\n";
    document.getElementById("order").innerHTML += "距離：" + better + "km<br>";


    document.getElementById("exec").disabled = "";

    alert("終了しました。");
}

長々お疲れ様でした。
以上で作成は完了です。

このプログラムで得られた結果は、パス表現法のように交叉しない経路が得られるはずですが、
あくまでも100％ではありませんのでご注意ください。

この記事がお役に立ちましたらシェアお願いします
, , , , ,
9,023 views
≪ ≫

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です