Travelling salesman problem 簡稱 TSP，也有人翻譯成「旅行業務員問題」，是演算法非常經典的問題，簡單來說，就是我們可以假想成一個業務員，或推銷員，有一連串的客戶需要拜訪，因此需要決定一個最佳的順序，以節省時間或旅行距離。
使用 Google 搜尋「Travelling salesman problem」，就可以看到很多的圖片解說：
在實際生活的場景中，我們其實有很多的機會遇到這樣的問題，例如，在規劃自助旅行的時候的景點順序；或是跟同事約共乘要決定接人的順序；或是逢年過節要到許多客戶那邊送禮物等等。很多時候，要怎麼決定先後順序都是很重要的問題。
HERE 提供的 Waypoints Sequence API 就是用來解決這個問題的產品。這個產品的主要特色有：
以下我們就來進行實做。不過您必須要有 HERE 開發者帳號，以及一個有效的 HERE APIKEY，您可以參閱 快速建構地圖服務 - 使用 HERE Studio / Data Hub（一） 以及 快速建構地圖服務 - 使用 HERE Studio / Data Hub（四） 的內容來申請 HERE 開發者帳號以及產生一個有效的 APIKEY。
取得 APIKEY 之後，我們可以進行一個非常簡單的目的地排序的請求，沒有特殊需求的狀況下，只要輸入每個地點的經緯度就可以了，我們從台北車站（25.04717 121.51706）出發，並且出發到台北市的三個地點，分別是destination1-3：
WW
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）出發，接著列出幾個我們想去的景點如下：
於是我們可以把相關參數放進 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 網路定位服務
iThome鐵人賽
看影片追技術