Categories
SugiBlog ホームページ制作・システム開発

ルート検索 最適経路

営業の仕事をしていると、複数の場所を効率よく回りたい、という要求が出てくるかと思います。
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を使いプログラムを作成しました。

続きを読む…»

4,730 views

Ajax レスポンス処理の注意点

Ajaxを使用して通信し、得た結果を処理するときの注意点。

サーバーサイドでオブジェクト等を生成して返し、それをeval処理する際、
無効な改行が含まれるとエラーが発生することがあります。

具体的には「終了していない文字列型の定数です。」とスクリプトエラーが発生してしまいます。

例えば、PHPで単純に以下のようなデータを出力するとします。

echo "var a = \"文字列\";";

それをJavaScriptでeval処理すると

eval(responseText);
alert(a);

「文字列」というアラートが表示される。
続きを読む…»

2,838 views

GoogleMaps JavaScript API v3 日本語リファレンス

https://developers.google.com/maps/documentation/javascript/services?hl=ja

1,449 views

GoogleMap ルート案内

<form action="http://maps.google.co.jp/maps" method="get" target="_blank">
ここまでのルートを検索
出発地(住所・駅名):<input type="text" size="30" name="saddr" id="saddr" value="" />
交通手段:<input type="radio" name="dirflg" value="r" checked="checked" />電車
<input type="radio" name="dirflg" value="d" />車
<input type="hidden" name="daddr" value="lat,lon" />
<input type="submit" value="ルート検索" />
</form>

・アイコンクリックにイベントを追加

GEvent.addListener(marker, "click", function() {
marker.openInfoWindowHtml([上記HTML]);
});
974 views

Googlemap マウスホイールのズーム

GoogleMap v2.78以降

マウスホイールのズーム可否を指定するメソッド

enableScrollWheelZoom // 有効
disableScrollWheelZoom // 無効
920 views