快速建構地圖服務（六）- HERE Waypoints Sequence 路徑最佳排序

認識 HERE Waypoints Sequence

Travelling salesman problem 簡稱 TSP，也有人翻譯成「旅行業務員問題」，是演算法非常經典的問題，簡單來說，就是我們可以假想成一個業務員，或推銷員，有一連串的客戶需要拜訪，因此需要決定一個最佳的順序，以節省時間或旅行距離。

使用 Google 搜尋「Travelling salesman problem」，就可以看到很多的圖片解說：

在實際生活的場景中，我們其實有很多的機會遇到這樣的問題，例如，在規劃自助旅行的時候的景點順序；或是跟同事約共乘要決定接人的順序；或是逢年過節要到許多客戶那邊送禮物等等。很多時候，要怎麼決定先後順序都是很重要的問題。

HERE 提供的 Waypoints Sequence API 就是用來解決這個問題的產品。這個產品的主要特色有：

1. 支援汽車、卡車與行人的路徑計算。
2. 支援考慮即時路況/歷史路況來進行路徑的計算。
3. 可以選擇是否避開收費道路、高快速道路或渡輪。
4. 可以選擇避開特定的道路或區域。
5. 可以選擇依照較短時間或較短距離來推薦順序。
6. 如果是計算卡車，可以支援許多詳細的卡車屬性，例如長、寬、高、軸數、載運物等。
7. 可以指定每個地點的停留時間，最後算出的結果也會包含預計到達時間與離開時間。
8. 可以指定每個地點的時間點或時間段，因此可以算出一個符合時間需求的順序。
9. 可以設定車輛的容量與運作成本。
10. 搭配容量的設定，可以計算「pickup（取貨/上車）」或「drop（送貨/下車）」所需要的貨物空間。如果車輛的剩餘容量不足，可以略過特定的取貨點。
11. 您甚至可以定義中途休息的時間（許多國家有連續駕駛時間的限制）。

實做第一個路徑最佳排序

以下我們就來進行實做。不過您必須要有 HERE 開發者帳號，以及一個有效的 HERE APIKEY，您可以參閱 快速建構地圖服務 - 使用 HERE Studio / Data Hub（一） 以及 快速建構地圖服務 - 使用 HERE Studio / Data Hub（四） 的內容來申請 HERE 開發者帳號以及產生一個有效的 APIKEY。

取得 APIKEY 之後，我們可以進行一個非常簡單的目的地排序的請求，沒有特殊需求的狀況下，只要輸入每個地點的經緯度就可以了，我們從台北車站（25.04717 121.51706）出發，並且出發到台北市的三個地點，分別是destination1-3：

https://wse.ls.hereapi.com/2/findsequence.json?
start=25.04717,121.51706
&destination1=25.04985,121.57717
&destination2=25.03314,121.5669
&destination3=25.02665,121.53461
&mode=fastest;car
&apiKey={API_KEY}

回傳的結果會像這樣，您可以看到，最佳的順序是從 start 開始後，先前往 destination3，再前往 destination2，最後才是 destination1。在下方的「distance」就告訴您整趟行程跑完的路程長度是 11829 公尺，「time」也又是時間，總共耗費 1607 秒。

另外，每一個目的地之間的移動時間與距離也都詳細列出，例如第一段旅程從 start 到 destination3 的移動距離是 4368.0 公尺，時間為 570.0 秒。

{
    "results": [
        {
            "waypoints": [
                {
                    "id": "start",
                    "lat": 25.04717,
                    "lng": 121.51706,
                    "sequence": 0,
                    "estimatedArrival": null,
                    "estimatedDeparture": null,
                    "fulfilledConstraints": []
                },
                {
                    "id": "destination3",
                    "lat": 25.02665,
                    "lng": 121.53461,
                    "sequence": 1,
                    "estimatedArrival": null,
                    "estimatedDeparture": null,
                    "fulfilledConstraints": []
                },
                {
                    "id": "destination2",
                    "lat": 25.03314,
                    "lng": 121.5669,
                    "sequence": 2,
                    "estimatedArrival": null,
                    "estimatedDeparture": null,
                    "fulfilledConstraints": []
                },
                {
                    "id": "destination1",
                    "lat": 25.04985,
                    "lng": 121.57717,
                    "sequence": 3,
                    "estimatedArrival": null,
                    "estimatedDeparture": null,
                    "fulfilledConstraints": []
                }
            ],
            "distance": "11829",
            "time": "1607",
            "interconnections": [
                {
                    "fromWaypoint": "start",
                    "toWaypoint": "destination3",
                    "distance": 4368.0,
                    "time": 570.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "destination3",
                    "toWaypoint": "destination2",
                    "distance": 4364.0,
                    "time": 636.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "destination2",
                    "toWaypoint": "destination1",
                    "distance": 3097.0,
                    "time": 401.0,
                    "rest": 0.0,
                    "waiting": 0.0
                }
            ],
            "description": "Targeted best time; without traffic",
            "timeBreakdown": {
                "driving": 1607,
                "service": 0,
                "rest": 0,
                "waiting": 0
            }
        }
    ],
    "errors": [],
    "processingTimeDesc": "61ms",
    "responseCode": "200",
    "warnings": null,
    "requestId": null
}

加上更多參數

但在實際生活中，我們經常會需要預估停留的時間，以及指定出發/抵達的時間，因此我們可以在上面這個案例中加入額外的參數。例如我們可以用「departure」這個參數來指定整個旅程的出發時間，以此為例是 2020 年的 12 月 12 日，格林威治時間早上一點整，換算台灣時間則是早上九點。我們也可以在每個路徑點上面用「st」這個參數來設定停留時間，例如我們設定 destination1-3 都停留 30 分鐘，也就是 1800 秒。

我們也可以為每個地點命名，這樣我們在解讀回傳的結果會更有效率，例如我們可以把 destination1 命名為「客戶李先生」。在「mode」中加入「traffic:enabled」，來考慮道路的堵塞狀況，算出來的時間也會更加符合實際狀況。

https://wse.ls.hereapi.com/2/findsequence.json?
start=台北車站;25.04717,121.51706
&destination1=客戶李先生;25.04985,121.57717;st:1800
&destination2=客戶王小姐;25.03314,121.5669;st:1800
&destination3=供應商陳先生;25.02665,121.53461;st:1800
&departure=2020-12-12T01:00:00Z
&mode=fastest;car;traffic:enabled
&apiKey={API_KEY}

回傳的結果如下，您會發現這些跟上一次的結果比起來，多了一些資訊，例如「estimatedArrival」代表預計抵達時間，「estimatedDeparture」代表預計離開時間，因此我們可以解讀這一趟旅程會在當天早上九點出發，並且在早上 9:11 抵達我們的第一個目的地「供應商陳先生」，停留三十分鐘後，在早上 9:41 離開「供應商陳先生」，前往下一個目的地「客戶王小姐」。依此類推，整趟旅程會在

{
    "results": [
        {
            "waypoints": [
                {
                    "id": "台北車站",
                    "lat": 25.04717,
                    "lng": 121.51706,
                    "sequence": 0,
                    "estimatedArrival": null,
                    "estimatedDeparture": "2020-12-12T01:00:00Z",
                    "fulfilledConstraints": []
                },
                {
                    "id": "供應商陳先生",
                    "lat": 25.02665,
                    "lng": 121.53461,
                    "sequence": 1,
                    "estimatedArrival": "2020-12-12T01:11:18Z",
                    "estimatedDeparture": "2020-12-12T01:41:18Z",
                    "fulfilledConstraints": [
                        "st:1800"
                    ]
                },
                {
                    "id": "客戶王小姐",
                    "lat": 25.03314,
                    "lng": 121.5669,
                    "sequence": 2,
                    "estimatedArrival": "2020-12-12T01:54:19Z",
                    "estimatedDeparture": "2020-12-12T02:24:19Z",
                    "fulfilledConstraints": [
                        "st:1800"
                    ]
                },
                {
                    "id": "客戶李先生",
                    "lat": 25.04985,
                    "lng": 121.57717,
                    "sequence": 3,
                    "estimatedArrival": "2020-12-12T02:33:08Z",
                    "estimatedDeparture": null,
                    "fulfilledConstraints": [
                        "st:1800"
                    ]
                }
            ],
            "distance": "12271",
            "time": "7388",
            "interconnections": [
                {
                    "fromWaypoint": "台北車站",
                    "toWaypoint": "供應商陳先生",
                    "distance": 4332.0,
                    "time": 678.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "供應商陳先生",
                    "toWaypoint": "客戶王小姐",
                    "distance": 4364.0,
                    "time": 781.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "客戶王小姐",
                    "toWaypoint": "客戶李先生",
                    "distance": 3575.0,
                    "time": 529.0,
                    "rest": 0.0,
                    "waiting": 0.0
                }
            ],
            "description": "Targeted best time; with , improvement for traffic",
            "timeBreakdown": {
                "driving": 1988,
                "service": 5400,
                "rest": 0,
                "waiting": 0
            }
        }
    ],
    "errors": [],
    "processingTimeDesc": "465ms",
    "responseCode": "200",
    "warnings": null,
    "requestId": null
}

實際案例：自由行景點排序

接著我們就來實際用 Waypoints Sequence API 來實做一個旅遊行程規劃的案例，這樣的用途比較生活化且容易理解。我們可以設定旅客早上八點整從蘭城晶英酒店（24.75374,121.75067）出發，接著列出幾個我們想去的景點如下：

• 城隍早餐（24.7588975,121.7526904），停留 40 分鐘，悠閒吃早餐。
• 宜蘭火車站幾米廣場（24.75475,121.7576），停留 30 分鐘，拍照。
• 舊宜蘭監獄門廳（24.75371,121.7515），停留 10 分鐘，快閃拍照。
• 宜蘭設治紀念館（24.75528,121.74901），停留 30 分鐘，悠閒停留。
• 橘之鄉蜜餞形象館（24.7797106,121.7373771），停留 60 分鐘。
• 頭城老街（24.85697,121.8241578），於 中午 12 點到 下午 2 點中間停留，停留 60 分鐘，吃午餐。
• 阿宗芋冰城（24.8587948,121.8259636），於 中午 12 點到 下午 2 點中間停留，停留 20 分鐘，吃完午餐之後吃冰（必須在頭城老街後面）。
• 龍潭湖風景區（24.7920844,121.7398288），停留 120 分鐘，下午抵達，騎腳踏車、散步。
• 樂山溫泉拉麵（24.8312227,121.7757601），停留 40 分鐘，訂位晚上 7 點，吃晚餐。
• 春水笈溫泉湯屋（24.831647,121.770149），停留 90 分鐘，吃完飯泡湯（必須在樂山溫泉拉麵後面）。
• 行程結束後，返回蘭城晶英酒店（24.75374,121.75067）。

於是我們可以把相關參數放進 Waypoints Sequence API 中，並送出請求：

https://wse.ls.hereapi.com/2/findsequence.json?
start=蘭城晶英酒店（起點）;24.75374,121.75067
&destination1=城隍早餐;24.7588975,121.7526904;st:2400;acc:sa00:00:00Z|sa01:00:00Z
&destination2=宜蘭火車站幾米廣場;24.75475,121.7576;st:1800
&destination3=舊宜蘭監獄門廳;24.75371,121.7515;st:600
&destination4=宜蘭設治紀念館;24.75528,121.74901;st:1800
&destination5=橘之鄉蜜餞形象館;24.7797106,121.7373771;st:3600
&destination6=頭城老街;24.85697,121.8241578;st:3600;acc:sa04:00:00Z|sa06:00:00Z;before:destination7
&destination7=阿宗芋冰城;24.8587948,121.8259636;st:1200;acc:sa04:00:00Z|sa06:00:00Z
&destination8=龍潭湖風景區;24.7920844,121.7398288;st:7200;acc:sa06:00:00Z|sa08:00:00Z
&destination9=樂山溫泉拉麵;24.8312227,121.7757601;st:2400;at:2020-12-12T11:00:00Z;before:destination10
&destination10=春水笈溫泉湯屋;24.831647,121.770149;st:5400
&end=蘭城晶英酒店（終點）;24.75374,121.75067
&departure=2020-12-12T00:00:00Z
&mode=fastest;car;traffic:enabled
&apiKey={API_KEY}

依照回傳的結果，我們可以排出以下的順序：

蘭城晶英酒店（起點）：早上 08:00 出發。

舊宜蘭監獄門廳：早上 08:00 抵達，早上 08:10 離開。

城隍早餐（早餐）：早上 08:14 抵達，早上 08:54 離開。

宜蘭設治紀念館：早上 08:57 抵達，早上 09:27 離開。

宜蘭火車站幾米廣場：早上 09:31 抵達，早上 10:01 離開。

橘之鄉蜜餞形象館：早上 10:13 抵達，早上 11:13 離開。

頭城老街（午餐）：早上 11:44 抵達，下午 13:00 離開。

阿宗芋冰城：下午 01:01 抵達，下午 01:21 離開。

龍潭湖風景區：下午 01:51 抵達，下午 04:00 離開。

樂山溫泉拉麵（晚餐）：下午 04:21 抵達，下午 07:40 離開。

春水笈溫泉湯屋：下午 07:42 抵達，下午 09:12 離開。

蘭城晶英酒店（終點）：下午 09:37 抵達。

完成的回傳結果如下：

    "results": [
        {
            "waypoints": [
                {
                    "id": "蘭城晶英酒店（起點）",
                    "lat": 24.75374,
                    "lng": 121.75067,
                    "sequence": 0,
                    "estimatedArrival": null,
                    "estimatedDeparture": "2020-12-12T00:00:00Z",
                    "fulfilledConstraints": []
                },
                {
                    "id": "舊宜蘭監獄門廳",
                    "lat": 24.75371,
                    "lng": 121.7515,
                    "sequence": 1,
                    "estimatedArrival": "2020-12-12T00:00:54Z",
                    "estimatedDeparture": "2020-12-12T00:10:54Z",
                    "fulfilledConstraints": [
                        "st:600"
                    ]
                },
                {
                    "id": "城隍早餐",
                    "lat": 24.7588975,
                    "lng": 121.7526904,
                    "sequence": 2,
                    "estimatedArrival": "2020-12-12T00:14:24Z",
                    "estimatedDeparture": "2020-12-12T00:54:24Z",
                    "fulfilledConstraints": [
                        "acc:sa00:00:00+00:00|sa01:00:00+00:00;st:2400"
                    ]
                },
                {
                    "id": "宜蘭設治紀念館",
                    "lat": 24.75528,
                    "lng": 121.74901,
                    "sequence": 3,
                    "estimatedArrival": "2020-12-12T00:57:20Z",
                    "estimatedDeparture": "2020-12-12T01:27:20Z",
                    "fulfilledConstraints": [
                        "st:1800"
                    ]
                },
                {
                    "id": "宜蘭火車站幾米廣場",
                    "lat": 24.75475,
                    "lng": 121.7576,
                    "sequence": 4,
                    "estimatedArrival": "2020-12-12T01:31:38Z",
                    "estimatedDeparture": "2020-12-12T02:01:38Z",
                    "fulfilledConstraints": [
                        "st:1800"
                    ]
                },
                {
                    "id": "橘之鄉蜜餞形象館",
                    "lat": 24.7797106,
                    "lng": 121.7373771,
                    "sequence": 5,
                    "estimatedArrival": "2020-12-12T02:13:59Z",
                    "estimatedDeparture": "2020-12-12T03:13:59Z",
                    "fulfilledConstraints": [
                        "st:3600"
                    ]
                },
                {
                    "id": "頭城老街",
                    "lat": 24.85697,
                    "lng": 121.8241578,
                    "sequence": 6,
                    "estimatedArrival": "2020-12-12T03:44:24Z",
                    "estimatedDeparture": "2020-12-12T05:00:00Z",
                    "fulfilledConstraints": [
                        "acc:sa04:00:00+00:00|sa06:00:00+00:00;st:3600",
                        "before:destination7"
                    ]
                },
                {
                    "id": "阿宗芋冰城",
                    "lat": 24.8587948,
                    "lng": 121.8259636,
                    "sequence": 7,
                    "estimatedArrival": "2020-12-12T05:01:28Z",
                    "estimatedDeparture": "2020-12-12T05:21:28Z",
                    "fulfilledConstraints": [
                        "acc:sa04:00:00+00:00|sa06:00:00+00:00;st:1200"
                    ]
                },
                {
                    "id": "龍潭湖風景區",
                    "lat": 24.7920844,
                    "lng": 121.7398288,
                    "sequence": 8,
                    "estimatedArrival": "2020-12-12T05:51:37Z",
                    "estimatedDeparture": "2020-12-12T08:00:00Z",
                    "fulfilledConstraints": [
                        "acc:sa06:00:00+00:00|sa08:00:00+00:00;st:7200"
                    ]
                },
                {
                    "id": "樂山溫泉拉麵",
                    "lat": 24.8312227,
                    "lng": 121.7757601,
                    "sequence": 9,
                    "estimatedArrival": "2020-12-12T08:21:17Z",
                    "estimatedDeparture": "2020-12-12T11:40:00Z",
                    "fulfilledConstraints": [
                        "at:2020-12-12T11:00:00Z;st:2400",
                        "before:destination10"
                    ]
                },
                {
                    "id": "春水笈溫泉湯屋",
                    "lat": 24.831647,
                    "lng": 121.770149,
                    "sequence": 10,
                    "estimatedArrival": "2020-12-12T11:42:43Z",
                    "estimatedDeparture": "2020-12-12T13:12:43Z",
                    "fulfilledConstraints": [
                        "st:5400"
                    ]
                },
                {
                    "id": "蘭城晶英酒店（終點）",
                    "lat": 24.75374,
                    "lng": 121.75067,
                    "sequence": 11,
                    "estimatedArrival": "2020-12-12T13:37:02Z",
                    "estimatedDeparture": null,
                    "fulfilledConstraints": []
                }
            ],
            "distance": "59170",
            "time": "49022",
            "interconnections": [
                {
                    "fromWaypoint": "蘭城晶英酒店（起點）",
                    "toWaypoint": "舊宜蘭監獄門廳",
                    "distance": 155.0,
                    "time": 54.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "舊宜蘭監獄門廳",
                    "toWaypoint": "城隍早餐",
                    "distance": 641.0,
                    "time": 210.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "城隍早餐",
                    "toWaypoint": "宜蘭設治紀念館",
                    "distance": 817.0,
                    "time": 176.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "宜蘭設治紀念館",
                    "toWaypoint": "宜蘭火車站幾米廣場",
                    "distance": 972.0,
                    "time": 258.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "宜蘭火車站幾米廣場",
                    "toWaypoint": "橘之鄉蜜餞形象館",
                    "distance": 4634.0,
                    "time": 741.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "橘之鄉蜜餞形象館",
                    "toWaypoint": "頭城老街",
                    "distance": 17468.0,
                    "time": 1825.0,
                    "rest": 0.0,
                    "waiting": 936.0
                },
                {
                    "fromWaypoint": "頭城老街",
                    "toWaypoint": "阿宗芋冰城",
                    "distance": 340.0,
                    "time": 88.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "阿宗芋冰城",
                    "toWaypoint": "龍潭湖風景區",
                    "distance": 15287.0,
                    "time": 1809.0,
                    "rest": 0.0,
                    "waiting": 503.0
                },
                {
                    "fromWaypoint": "龍潭湖風景區",
                    "toWaypoint": "樂山溫泉拉麵",
                    "distance": 8191.0,
                    "time": 1277.0,
                    "rest": 0.0,
                    "waiting": 9523.0
                },
                {
                    "fromWaypoint": "樂山溫泉拉麵",
                    "toWaypoint": "春水笈溫泉湯屋",
                    "distance": 796.0,
                    "time": 163.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "春水笈溫泉湯屋",
                    "toWaypoint": "蘭城晶英酒店（終點）",
                    "distance": 9869.0,
                    "time": 1459.0,
                    "rest": 0.0,
                    "waiting": 0.0
                }
            ],
            "description": "Targeted best time; with , improvement for traffic",
            "timeBreakdown": {
                "driving": 8060,
                "service": 30000,
                "rest": 0,
                "waiting": 10962
            }
        }
    ],
    "errors": [],
    "processingTimeDesc": "1414ms",
    "responseCode": "200",
    "warnings": null,
    "requestId": null
}

歡迎到 HERE 開發者網站了解更多關於 Waypoints Sequence 的詳情：https://developer.here.com/documentation/routing-waypoints/

「快速建構地圖服務」系列文章

快速建構地圖服務（一） - 認識 HERE Studio / Data Hub
快速建構地圖服務（二） - 認識 HERE Data Hub CLI / API
快速建構地圖服務（三） - 使用 QGIS 玩轉 HERE Data Hub
快速建構地圖服務（四） - 當 Leaflet JS 遇見 Data Hub
快速建構地圖服務（五） - 整合 HERE 地點搜尋 API
快速建構地圖服務（六）- HERE Waypoints Sequence 路徑最佳排序
快速建構地圖服務（七）- 認識 HERE Routing API - 路徑規劃
快速建構地圖服務（八）- 認識 Matrix Routing
快速建構地圖服務（九）- Isoline Routing
快速建構地圖服務（十）- HERE Tour Planning 物流路徑預排與成本精算
快速建構地圖服務（十一）- HERE Route Matching GPS 軌跡分析
快速建構地圖服務（十二）- HERE Custom Locations 地圖資料倉儲與查詢
快速建構地圖服務（十三）- HERE Geofencing 地理圍籬
快速建構地圖服務（十四）- HERE Custom Routes 自建路網 + Vector Tile 向量圖磚 + Map Image API 靜態地圖
快速建構地圖服務（十五）- HERE Positioning 網路定位服務