カテゴリー
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を使いプログラムを作成しました。

続きを読む…»

この記事がお役に立ちましたらシェアお願いします

6,533 views

ページのトップへスクロールする

現在のページのトップへスクロールする小技です。
jQueryを使って実装します。

JavaScriptライブラリをダウンロード
jQuery

まずheadタグ内でjQueryライブラリを読み込みます。

<script type="text/javascript" src="./lib/jquery-1.7.2.min.js"></script>

bodyタグにIDを付けます

<body id="top">

ID付のdivタグで括ってリンクを作成します。

<div id="to_pagetop">
    <a href="#top">上に戻る</a>
</div>

最後に任意の場所に以下のコードを記述します。 続きを読む…»

この記事がお役に立ちましたらシェアお願いします

780 views

jQueryプラグイン Excolo-Slider

Excolo-Sliderはシンプルなスライドショーを実装してくれるプラグインです。
シンプルではありますが、オプションも多様に用意されていて、スマホのタッチ操作にも対応しているので
非常に使い勝手が良いです。

JavaScriptライブラリをダウンロード
jQuery
Excolo-Slider

headタグ内でダウンロードしたライブラリを読み込みます。

<script type="text/javascript" src="./jquery-1.9.1.min.js"></script>
<script type="text/javascript" src="./excolo-slider/js/jquery.excoloSlider.js"></script>
<link rel="stylesheet" href="./excolo-slider/css/jquery.excoloSlider.css">

HTMLを用意します。

<div id="eslider" class="slider">
    <a href="#"><img src="./images/example1.gif" width="260" height="100" alt=""></a>
    <a href="#"><img src="./images/example2.gif" width="260" height="100" alt=""></a>
    <a href="#"><img src="./images/example3.gif" width="260" height="100" alt=""></a>
    <img src="./images/example4.gif" width="260" height="100" alt="">
</div>

続きを読む…»

この記事がお役に立ちましたらシェアお願いします

1,161 views

jQueryプラグイン Masonry

「Masonry」とはJavaScriptグリッドレイアウトライブラリです。
高さの違う要素を、パネルを敷き詰めるようにレイアウトしてくれるというものです。

ウィンドウのサイズが変われば、アニメーションしながら並び替えという動作も行ってくるので、
レスポンシブWEBデザインとしても利用できます。

JavaScriptライブラリをダウンロード
jQuery
jQuery masonry

headタグ内でダウンロードしたライブラリを読み込みます。

<script type="text/javascript" src="./jquery-1.7.2.min.js"></script>
<script type="text/javascript" src="./masonry.pkgd.min.js"></script>

続きを読む…»

この記事がお役に立ちましたらシェアお願いします

1,367 views

レスポンシブwebデザインのCSS

簡単なレスポンシブwebデザインを実装してみましょう。
以下のようなHTMLがあったとします。

<!DOCTYPE HTML>
<html lang="ja">
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>

<div class="content">
    sample
</div>

</body>
</html>

まず、どんな画面サイズでも共通となるスタイルを記述します。

@charset "utf-8";

*
{
    margin: 0;
    pading: 0;
}

各画面サイズに適用するスタイルをMediaQueryを使って指定していきます。
続きを読む…»

この記事がお役に立ちましたらシェアお願いします

1,025 views