Google Maps Distance Matrix API 開發應用筆記
大约 6 分鐘
Google Maps Distance Matrix API 開發應用筆記
前言
最近接了一個旅遊網站的案子，
有個需求是要將旅遊景點計算最短路徑，
因為有點燒腦......所以就把步驟寫下來。
專案目標
給定一個旅遊景點的陣列資料，包含上車地點、遊玩景點、下車地點，
經由 Google Maps Distance Matrix API 計算各景點的距離，
取得景點距離矩陣後重新排序並輸出。
參考資料格式
初始資料格式如下：
起點 ID 為 0 ，終點 ID 為 -1，中間的景點 ID 是對應資料庫的景點 PK。
{
[
{
"id": 0,
"title": "豐田車站",
"address": "974花蓮縣壽豐鄉"
},
{
"id": 30,
"title": "AWOS農場",
"address": "962台東縣長濱鄉八桑安路65之1號"
},
{
"id": 40,
"title": "鯉魚潭SUP立式划槳・獨木舟",
"address": "972花蓮縣秀林鄉海濱路1-8號"
},
{
"id": 44,
"title": "多羅滿海洋賞鯨",
"address": "970花蓮縣花蓮市華東15號"
},
{
"id": 46,
"title": "太魯閣布拉旦飛行傘",
"address": "971花蓮縣新城鄉33-12號"
},
{
"id": -1,
"title": "花蓮火車站",
"address": "970花蓮縣花蓮市國聯一路100號"
}
]
}
呼叫距離矩陣請求
以下是 PHP 的呼叫範例，$waypoints是一個地址陣列，origins 傳入出發地，destinations 傳入目的地，用|符號做分隔。
因為終點是最後會走的路線，所以可以不需要傳入 Distance Matrix API。
/**
* 取得多個目的地的交通時間和距離的矩陣
* rows = origins 數量
* elements = destinations 數量
* 會有 rows x elements 種結果
*/
public function callDistanceMatrixAPI(array $waypoints)
{
// 構建請求
$endpoint = 'https://maps.googleapis.com/maps/api/distancematrix/json';
$params = array(
'origins' => implode('|', $waypoints),
'destinations' => implode('|', $waypoints),
'language' => 'zh-TW',
'key' => env('GOOGLEMAP_API_KEY', '') // 請換成您自己的 API 金鑰
);
$url = $endpoint . '?' . http_build_query($params);
// 發送請求並獲取響應
$response = file_get_contents($url);
$data = json_decode($response);
return $data;
}
呼叫距離矩回應
呼叫後得到以下回應
{
"destination_addresses": ["974台灣花蓮縣壽豐鄉豐田車站", "962台灣台東縣長濱鄉八桑安", "97253台灣花蓮縣秀林鄉海濱路1-8號", "970台灣花蓮縣花蓮市華東", "971台灣花蓮縣新城鄉新城"],
"origin_addresses": ["974台灣花蓮縣壽豐鄉豐田車站", "962台灣台東縣長濱鄉八桑安", "97253台灣花蓮縣秀林鄉海濱路1-8號", "970台灣花蓮縣花蓮市華東", "971台灣花蓮縣新城鄉新城"],
"rows": [
{
"elements": [
{
"distance": {
"text": "1 公尺",
"value": 0
},
"duration": {
"text": "1 分鐘",
"value": 0
},
"status": "OK"
},
{
"distance": {
"text": "87.6 公里",
"value": 87578
},
"duration": {
"text": "1 小時 40 分鐘",
"value": 6015
},
"status": "OK"
},
{
"distance": {
"text": "42.8 公里",
"value": 42755
},
"duration": {
"text": "59 分鐘",
"value": 3560
},
"status": "OK"
},
{
"distance": {
"text": "25.4 公里",
"value": 25449
},
"duration": {
"text": "35 分鐘",
"value": 2101
},
"status": "OK"
},
{
"distance": {
"text": "25.2 公里",
"value": 25249
},
"duration": {
"text": "39 分鐘",
"value": 2351
},
"status": "OK"
}
]
},
{
"elements": [
{
"distance": {
"text": "87.5 公里",
"value": 87477
},
"duration": {
"text": "1 小時 38 分鐘",
"value": 5886
},
"status": "OK"
},
{
"distance": {
"text": "1 公尺",
"value": 0
},
"duration": {
"text": "1 分鐘",
"value": 0
},
"status": "OK"
},
{
"distance": {
"text": "122 公里",
"value": 121791
},
"duration": {
"text": "2 小時 21 分鐘",
"value": 8438
},
"status": "OK"
},
{
"distance": {
"text": "99.8 公里",
"value": 99827
},
"duration": {
"text": "1 小時 53 分鐘",
"value": 6803
},
"status": "OK"
},
{
"distance": {
"text": "103 公里",
"value": 103124
},
"duration": {
"text": "2 小時 3 分鐘",
"value": 7353
},
"status": "OK"
}
]
},
{
"elements": [
{
"distance": {
"text": "42.8 公里",
"value": 42796
},
"duration": {
"text": "1 小時 1 分鐘",
"value": 3648
},
"status": "OK"
},
{
"distance": {
"text": "122 公里",
"value": 121744
},
"duration": {
"text": "2 小時 23 分鐘",
"value": 8593
},
"status": "OK"
},
{
"distance": {
"text": "1 公尺",
"value": 0
},
"duration": {
"text": "1 分鐘",
"value": 0
},
"status": "OK"
},
{
"distance": {
"text": "22.2 公里",
"value": 22162
},
"duration": {
"text": "30 分鐘",
"value": 1825
},
"status": "OK"
},
{
"distance": {
"text": "17.7 公里",
"value": 17674
},
"duration": {
"text": "24 分鐘",
"value": 1410
},
"status": "OK"
}
]
},
{
"elements": [
{
"distance": {
"text": "26.0 公里",
"value": 26006
},
"duration": {
"text": "37 分鐘",
"value": 2214
},
"status": "OK"
},
{
"distance": {
"text": "100 公里",
"value": 100402
},
"duration": {
"text": "1 小時 56 分鐘",
"value": 6967
},
"status": "OK"
},
{
"distance": {
"text": "22.3 公里",
"value": 22273
},
"duration": {
"text": "28 分鐘",
"value": 1709
},
"status": "OK"
},
{
"distance": {
"text": "1 公尺",
"value": 0
},
"duration": {
"text": "1 分鐘",
"value": 0
},
"status": "OK"
},
{
"distance": {
"text": "5.7 公里",
"value": 5744
},
"duration": {
"text": "11 分鐘",
"value": 667
},
"status": "OK"
}
]
},
{
"elements": [
{
"distance": {
"text": "25.4 公里",
"value": 25441
},
"duration": {
"text": "39 分鐘",
"value": 2343
},
"status": "OK"
},
{
"distance": {
"text": "103 公里",
"value": 102699
},
"duration": {
"text": "2 小時 2 分鐘",
"value": 7321
},
"status": "OK"
},
{
"distance": {
"text": "17.7 公里",
"value": 17657
},
"duration": {
"text": "22 分鐘",
"value": 1317
},
"status": "OK"
},
{
"distance": {
"text": "5.9 公里",
"value": 5911
},
"duration": {
"text": "11 分鐘",
"value": 688
},
"status": "OK"
},
{
"distance": {
"text": "1 公尺",
"value": 0
},
"duration": {
"text": "1 分鐘",
"value": 0
},
"status": "OK"
}
]
}
],
"status": "OK"
}
矩陣表格
上面那一大串我們整理成以下表格，表格內為距離，這樣就比較好理解矩陣
| 豐田車站 | A-WOS 農場 | 鯉魚潭立槳 | 多羅滿賞鯨 | 布拉旦飛行傘 | |
|---|---|---|---|---|---|
| 豐田車站 | 0 公里 | 87.6 公里 | 42.8 公里 | 25.4 公里 | 25.2 公里 |
| A-WOS 農場 | 87.5 公里 | 0 公里 | 122 公里 | 99.8 公里 | 103 公里 |
| 鯉魚潭立槳 | 42.8 公里 | 122 公里 | 0 公里 | 22.2 公里 | 17.7 公里 |
| 多羅滿賞鯨 | 26.0 公里 | 100 公里 | 22.3 公里 | 0 公里 | 5.7 公里 |
| 布拉旦飛行傘 | 25.4 公里 | 103 公里 | 17.7 公里 | 5.9 公里 | 0 公里 |
最短路徑
這邊會用到「動態規劃（dynamic programming）」的觀念來計算最短路徑。
本次演算法需要定義以下變數
- 一個指向目前列的指針
- 一個結果陣列來記錄指針的順序
演算規則如下
- 除了自身景點的最短距離
- 已經出現在結果陣列要跳過
- 當陣列的數量等於景點數量就結束
第一步當然是起點，也就是表格最左上角。
指針會在第 1 列，接著從第一列找到除了自己以外距離最短的景點，
結果是布拉旦飛行傘，此時要將指針移到第 5 列。
第二步要從布拉旦飛行傘那一列找最短路徑，
結果會是多羅滿賞鯨，此時要將指針移到第 4 列
由於目前結果陣列已經有 豐田車站 和 布拉旦飛行傘
多羅滿賞鯨 可用以比較的景點剩下 A-WOS 農場 和 鯉魚潭立槳
引此答案就是鯉魚潭立槳 最後就是 A-WOS 農場
// 計算最佳路徑
public function getShortestPath(array $matrix)
{
// 紀錄經過的路徑初次起點為上車地點
$path = collect();
// 起始點為表格最左上角
$currentPath = $matrix[0][0];
$path->push(['order' => 1, 'id' => $currentPath['destinationId'], 'title' => $currentPath['destinationTitle'], 'address' => $currentPath['destinationAddress']]);
// 第一次執行定義的索引
$currentIndex = 0;
do {
$minDrationValue = 999999;
foreach ($matrix[$currentIndex] as $key => $value) {
$originId = $value['originId'];
$destinationId = $value['destinationId'];
$distanceValue = $value['distanceValue'];
$durationValue = $value['durationValue'];
$isContains = $path->contains('id', $destinationId);
if ($originId != $destinationId && $distanceValue > 0 && $durationValue > 0 && $minDrationValue > $durationValue && !$isContains) {
$minDrationValue = $durationValue;
$currentIndex = $key;
$currentPath = $value;
}
}
$path->push(['order' => count($path) + 1, 'id' => $currentPath['destinationId'], 'title' => $currentPath['destinationTitle'], 'address' => $currentPath['destinationAddress']]);
} while (count($path) < count($matrix) );
return $path;
}