東京はようやく桜が咲きそうです。桜並木の散歩が楽しみです。
今回は、巡回セールスマン問題です。複数の地点を訪れる際の最短経路を見つける問題です。時間の制約があり効率化が求められる現代ではより良い解が必要とされますね。可能であれば、時間を気にせず気の向くままに好きな方向に進んでいきたいですが。
では、巡回セールスマン問題の解法をGoogle Maps APIを利用して確認してみましょう。
設計
画面上で、以下5地点を指定し、Google Maps APIを呼び出して最短経路を取得・確認できるようにします。
- 出発地
- 経由地1
- 経由地2
- 経由地3
- 到着地
APIの構築
画面から呼び出すAPIをPython（Flaskフレームワークを利用）で構築します。
1. モジュールのインポート
from flask import Flask, render_template, request, jsonify import googlemaps from datetime import datetime import os
2. Google Maps APIを利用
google_maps_api_key = os.environ.get('GOOGLE_MAPS_API_KEY')
gmaps = googlemaps.Client(key=google_maps_api_key)
3. 初期表示用
@app.route('/') def index(): return render_template('index.html', google_maps_api_key=google_maps_api_key)
4. 経路計算API
画面からの入力（出発地、経由地、到着地）を受け取り、Google Maps Directions APIを呼び出して最適な経路を計算します。
@app.route('/compare_modes', methods=['GET']) def compare_modes(): # 出発地(origin)、到着地(destination)、経由地(waypoints)を取得 origin = request.args.get('origin') destination = request.args.get('destination') waypoints = filter(None, [request.args.get(f'waypoint{i}') for i in range(1, 4)]) optimize = request.args.get('optimize') == 'true' # 経由地の最適化オプション waypoints_str = '|'.join(waypoints) if waypoints else None optimize_waypoints = optimize try: # Google Maps Directions APIを呼び出す directions_result = gmaps.directions(origin, # 出発地 destination, # 到着地 mode="driving", # 移動手段：driving waypoints=waypoints_str, # 経由地 optimize_waypoints=optimize_waypoints, #最適化オプション departure_time=datetime.now(), # 出発時間：現在時刻 traffic_model='best_guess') # 交通状態を考慮した時間算出方法：正確に予測 # 所要時間と距離を合計 total_duration_seconds = sum(leg['duration']['value'] for leg in directions_result[0]['legs']) total_distance_meters = sum(leg['distance']['value'] for leg in directions_result[0]['legs']) # 所要時間の変換 total_hours, remainder = divmod(total_duration_seconds, 3600) total_minutes = remainder // 60 # 距離の変換 total_distance_km = total_distance_meters / 1000 # 所要時間と距離を整形 duration_text = f"{total_hours}時間{total_minutes}分" if total_hours else f"{total_minutes}分" distance_text = f"{total_distance_km:.2f}km" results = { "route": [step["html_instructions"] for leg in directions_result[0]["legs"] for step in leg["steps"]], "duration": duration_text, "distance": distance_text } # ログファイルを初期化して出力 with open('app.log', 'w') as f: f.write("") custom_print(duration=results['duration'], distance=results['distance']) except Exception as e: return jsonify({"error": str(e)}), 500 return jsonify(results)
5. ログ表示API
@app.route('/logs') def view_logs(): with open('app.log', 'r') as f: content = f.read() return content
画面の構築
FlaskのHTMLテンプレートを構築します。
1. HTML
<body> <div id="map"></div> <!-- 地図表示用 --> <div class="form-row"> <!-- ユーザー入力用 --> <div class="form-group"> <label for="start_location">出発地:</label> <input type="text" id="start_location" name="start_location" required> </div> <div class="form-group"> <label for="waypoint1">経由地1:</label> <input type="text" id="waypoint1" name="waypoint1" required> </div> <div class="form-group"> <label for="waypoint2">経由地2:</label> <input type="text" id="waypoint2" name="waypoint2" required> </div> <div class="form-group"> <label for="waypoint3">経由地3:</label> <input type="text" id="waypoint3" name="waypoint3" required> </div> <div class="form-group"> <label for="end_location">到着地:</label> <input type="text" id="end_location" name="end_location" required> </div> </div> <div> <div class="form-group"> <label for="optimize_route">ルートを最適化する:</label> <input type="checkbox" id="optimize_route" name="optimize_route"> </div> <div class="form-group"> <button onclick="callEndpoint()">ルート確認</button> <button onclick="reloadPage()">初期化</button> </div> </div> <!-- ログ表示セクション --> <div id="log-content"> <pre id="logs"></pre> </div> </body>
2. Style
<style> /* 地図表示領域 */ #map { width: 100%; height: 400px; margin-bottom: 20px; } /* フォームとボタンの配置 */ #main-container { display: flex; flex-direction: row; justify-content: space-between; align-items: flex-start; } .form-row { display: flex; justify-content: space-between; flex-grow: 1; } .form-group { margin-bottom: 15px; } input[type="text"] { margin-top: 5px; width: 90%; } button { background-color: #4CAF50; color: white; padding: 10px 15px; border: none; border-radius: 5px; cursor: pointer; margin-right: 10px; } button:hover { background-color: #45a049; } #log-content { font-size: 16px; } </style>
3. Javascript
<script> var map; // Google Mapオブジェクト var clickCount = 0; // 地図クリック回数 var directionsRenderer; // 経路表示を管理 // 地図の初期設定と表示 function initMap() { var mapProp = { center: new google.maps.LatLng(35.6895, 139.6917), // 地図の中心地点 zoom: 10, // ズームレベル }; map = new google.maps.Map(document.getElementById("map"), mapProp); directionsRenderer = new google.maps.DirectionsRenderer(); directionsRenderer.setMap(map); // 経路を地図上に表示するための設定 google.maps.event.addListener(map, 'click', function(event) { placeMarker(event.latLng); }); } // クリックされた地点の座標を入力 function placeMarker(location) { clickCount++; var latRounded = location.lat().toFixed(6); // 緯度を小数点以下6桁に丸める var lngRounded = location.lng().toFixed(6); // 経度を小数点以下6桁に丸める var locationRounded = latRounded + ',' + lngRounded; // 緯度・経度を結合 // 最初のクリックは出発地、2〜4回目のクリックは経由地、5回目のクリックは到着地に設定 if (clickCount === 1) { document.getElementById('start_location').value = locationRounded; } else if (clickCount >= 2 && clickCount <= 4) { document.getElementById('waypoint' + (clickCount - 1)).value = locationRounded; } else if (clickCount === 5) { document.getElementById('end_location').value = locationRounded; clickCount = 0; } } // 経路表示 function displayRoute(origin, destination, waypoints, optimize) { directionsRenderer.setDirections({routes: []}); // 前の経路をクリア var directionsService = new google.maps.DirectionsService(); var waypointArray = waypoints.filter(value => !!value).map(location => ({ location: location, stopover: true })); var request = { origin: origin, destination: destination, waypoints: waypointArray, optimizeWaypoints: optimize, // 経路の最適化 travelMode: 'DRIVING' // 移動手段はDRIVING }; directionsService.route(request, function(result, status) { if (status == 'OK') { directionsRenderer.setDirections(result); } }); } // 経路計算 function callEndpoint() { var startLocation = document.getElementById('start_location').value; var endLocation = document.getElementById('end_location').value; var waypoint1 = document.getElementById('waypoint1').value; var waypoint2 = document.getElementById('waypoint2').value; var waypoint3 = document.getElementById('waypoint3').value; var optimizeRoute = document.getElementById('optimize_route').checked; if (!startLocation || !endLocation || !waypoint1 || !waypoint2 || !waypoint3) { alert("すべて入力してください。"); return; } // compare_modes API を呼び出す fetch(`/compare_modes?origin=${startLocation}&destination=${endLocation}&waypoint1=${waypoint1}&waypoint2=${waypoint2}&waypoint3=${waypoint3}&optimize=${optimizeRoute}`) .then(response => response.json()) .then(data => { loadLogs(); }) .catch(error => console.error('Error:', error)); displayRoute(startLocation, endLocation, [waypoint1, waypoint2, waypoint3], optimizeRoute); } // ログ表示 function loadLogs() { // logs API を呼び出す fetch('/logs') .then(response => response.text()) .then(data => { document.getElementById('logs').textContent = data; }) .catch(error => console.error('Error:', error)); } // 初期化 function reloadPage() { location.reload(); } </script>
デモ
- 地図を表示します。
- 地図上で「出発地」、「経由地」、「到着地」をクリックして各地点の緯度・経度を入力します。
- 「ルート確認」ボタンをクリックすると、指定した経由地順のルートを表示します。
- 「ルートを最適化する」チェックを入れると、経由地を効率的に巡る最短ルートを表示します。
最適化するときれいな一本線になりますね！
業務の効率化はとても大事です。
ただ人生は、寄り道してその場所で精一杯がんばり、次の寄り道をするのも大事かと思います。あの時の大失敗、今思い返すといい思い出ですよね。
