マルティスープ
Staff Blog

2017.02.11

Directions API で巡回セールスマン問題を解決する

みなさん、こんにちは。
今回は、Google Maps Directions API で、巡回セールスマン問題を解決する方法を解説します！

巡回セールスマン問題とは、複数の地点をどのように回れば一番効率的かを解く課題解決のことです。
Wikipediaでの説明
Directions APIでは、この問題をパラメータ1つで解決することができます。

早速、デモをご覧ください。
出発地、経由地1-5、到着地を入力し、まずは「ルートを最適化する」にチェックを入れないで検索を実行します。
次に「ルートを最適化する」にチェックを入れ、検索を実行してください。

「最適化なし」の結果です。

マルティスープ→東京タワー→スカイツリー→池袋サンシャインビル→東京都庁→お台場→六本木ヒルズ
総距離： 58.1 ㎞
総時間： 176.0 分

「最適化あり」の結果です。

マルティスープ→東京タワー→お台場→スカイツリー→池袋サンシャインビル→東京都庁→六本木ヒルズ
総距離： 50.4 ㎞
総時間： 152.5 分

「最適化あり」ですと、約8㎞、25分程度短縮した結果となりました。

では、具体的にコードを見てみましょう。

var _map;

// 地図の初期化
var initMap = function() {
	_map = new google.maps.Map(document.getElementById("map"), {
		zoom : 13,
		center: new google.maps.LatLng(35.692141, 139.759844),
		mayTypeId: google.maps.MapTypeId.ROADMAP
	});
};

// ルート検索実行
var calcRoute = function() {	
	// 経由地の配列を生成
	var wayPoints = new Array();
	wayPoints.push({location: '東京タワー'});
	wayPoints.push({location: 'スカイツリー'});
	wayPoints.push({location: '池袋サンシャインビル'});
	wayPoints.push({location: '東京都庁'});
	wayPoints.push({location: 'お台場'});

	// DirectionsService生成
	var directionsService = new google.maps.DirectionsService();

	// DirectionｓRenderer生成
	var directionsRenderer = new google.maps.DirectionsRenderer();
	directionsRenderer.setPanel(document.getElementById('route-panel'));
	directionsRenderer.setMap(_map);

	// ルート検索実行
	directionsService.route({
		origin: 'マルティスープ',  // 出発地
		destination: '六本木ヒルズ',  // 到着地
		avoidHighways: true, // 高速は利用しない
		travelMode: google.maps.TravelMode.DRIVING, // 車モード
		optimizeWaypoints: true, // 最適化を有効
		waypoints: wayPoints // 経由地
	}, function(response, status) {
		console.log(response);
		if (status === google.maps.DirectionsStatus.OK) {
			directionsRenderer.setDirections(response);
			var legs = response.routes[0].legs;
			
			// 総距離と総時間の合計する
			var dis = 0;
			var sec = 0;
			$.each(legs, function(i, val) {
				sec += val.duration.value;
				dis += val.distance.value;
			});
			console.log("distance=" + dis + ", secound=" + sec);
		} else {
			alert('Directions 失敗(' + status + ')');
		}
	});	
};	

最適化を有効するには、ルート検索を実行する際のオプション「optimizeWaypoints: true」と設定するだけです。これで、Google が一番最適なルートを返してくれるようになります。

また、以前のブログで紹介した渋滞状況を考慮したルート検索も使用可能です。こちらの機能を使用すれば、未来の日時を指定し、交通状況を考慮した最適なルートを算出することもできます。

スタンダードプランでは、経由地に設定できる数が 8 個までとなっております。しかし、プレミアムプランではその数が 23 個まで増加いたします。

是非、この機会にプレミアムプランもご検討ください。プレミアムプランの詳しい内容は、下記のページに記載しています。

Google Maps API プレミアムプランとは

本日ご紹介した内容は、Google Cloud Japan が提供する Youtube の動画でも紹介されています。
Youtube チャンネル

是非こちらも参考にしてください！