# (6) - HERE Waypoints Sequence - Optimal Destination Sorting


### Meet HERE Waypoints Sequence

Travelling salesman problem, or TSP for short, is a very classic problem in the algorithm. Simply put, we can assume that we are a salesman or a salesman, and there are a series of customers that need to be visited. Need to decide an optimal sequence to save time or travel distance.

Use Google to search for "Travelling salesman problem", you can see a lot of picture explanations:


In real life scenes, we actually have a lot of opportunities to encounter such problems, for example, the order of attractions when planning a self-guided trip; or when sharing a ride with a colleague to decide the order of pick-up; or during holidays To send gifts to many customers and so on. In many cases, how to decide the order is a very important issue.


The Waypoints Sequence API provided by HERE is the product used to solve this problem. The main features of this product are:

1. Support route calculation for cars, trucks and pedestrians.
2. Support the calculation of the route considering the real-time traffic/historical traffic
3. You can choose whether to avoid toll roads, high-speed roads or ferries.
4. You can choose to avoid specific roads or areas.
5. You can choose to recommend the order according to a shorter time or a shorter distance.
6. If you are calculating trucks, you can support many detailed truck attributes, such as length, width, height, number of axles, cargo, etc.
7. You can specify the stay time of each location, and the final calculated result will also include the estimated time of arrival and departure.
8. You can specify the time point or time period of each location, so you can calculate a sequence that meets the time requirements.
9. The capacity and operating cost of the vehicle can be set.
10. With the setting of capacity, the cargo space required for "pickup" or "drop" can be calculated. If the remaining capacity of the vehicle is insufficient, you can skip a specific pickup point.
11. You can even define the break time (many countries have continuous driving time restrictions).

### Implement the best sorting of the first route

Let's do it below. But you must have a HERE developer account and a valid HERE APIKEY. You can refer to [Quickly build a map service-Use HERE Studio / Data Hub (1)](https://ithelp.ithome.com.tw/articles /10235386) and [Quickly build a map service-Use HERE Studio / Data Hub (4)](https://ithelp.ithome.com.tw/articles/10235399) to apply for a HERE developer account and generate a valid APIKEY.

After obtaining the APIKEY, we can make a very simple request for sorting destinations. If there is no special requirement, we only need to enter the latitude and longitude of each location. We depart from Taipei Main Station (25.04717 121.51706) and depart for Taipei City. The three locations are 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}

The returned result will look like this. You can see that the best order is to start from start, go to destination3 first, then go to destination2, and finally destination1. The "distance" below tells you that the length of the entire trip is 11829 meters, and "time" is also time, which took 1607 seconds in total.

In addition, the travel time and distance between each destination are also listed in detail. For example, the travel distance from start to destination3 in the first part of the journey is 4368.0 meters and the time is 570.0 seconds.

{
    "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
}

### Add more parameters

But in real life, we often need to estimate the stay time and specify the departure/arrival time, so we can add additional parameters to the above case. For example, we can use the "departure" parameter to specify the departure time of the entire journey. For example, it is December 12, 2020, which is exactly one o'clock in the morning, Greenwich Mean Time, or nine o'clock in the morning when converted to Taiwan time. We can also use the "st" parameter on each path point to set the stay time. For example, we set destination1-3 to stay for 30 minutes, which is 1800 seconds.

We can also name each location so that we can interpret the returned results more efficiently. For example, we can name destination1 "Customer Mr. Li". Add "traffic:enabled" to "mode" to consider the congestion of the road, and the calculated time will be more in line with the actual situation.

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}

The returned results are as follows. You will find that compared with the results of the last time, there are some more information. For example, "estimatedArrival" represents the estimated time of arrival, and "estimatedDeparture" represents the estimated time of departure, so we can interpret that this journey will be in Depart at 9am that day and arrive at our first destination "Mr. Chen" at 9:11 in the morning. After staying for 30 minutes, leave "Mr. Chen" at 9:41 in the morning and go to the next destination. "Customer Miss Wang", and so on.

{
    "results": [
        {
            "waypoints": [
                {
                    "id": "Taipei Main Station",
                    "lat": 25.04717,
                    "lng": 121.51706,
                    "sequence": 0,
                    "estimatedArrival": null,
                    "estimatedDeparture": "2020-12-12T01:00:00Z",
                    "fulfilledConstraints": []
                },
                {
                    "id": "Supplier Mr. Chen",
                    "lat": 25.02665,
                    "lng": 121.53461,
                    "sequence": 1,
                    "estimatedArrival": "2020-12-12T01:11:18Z",
                    "estimatedDeparture": "2020-12-12T01:41:18Z",
                    "fulfilledConstraints": [
                        "st:1800"
                    ]
                },
                {
                    "id": "Client Miss Wang",
                    "lat": 25.03314,
                    "lng": 121.5669,
                    "sequence": 2,
                    "estimatedArrival": "2020-12-12T01:54:19Z",
                    "estimatedDeparture": "2020-12-12T02:24:19Z",
                    "fulfilledConstraints": [
                        "st:1800"
                    ]
                },
                {
                    "id": "Customer Mr. Li",
                    "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": "Taipei Main Station",
                    "toWaypoint": "Supplier Mr. Chen",
                    "distance": 4332.0,
                    "time": 678.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "Supplier Mr. Chen",
                    "toWaypoint": "Client Miss Wang",
                    "distance": 4364.0,
                    "time": 781.0,
                    "rest": 0.0,
                    "waiting": 0.0
                },
                {
                    "fromWaypoint": "Customer Miss Wang",
                    "toWaypoint": "Customer Mr. Li",
                    "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
}

### Practical case: Sorting of free travel spots

Then we will actually use the Waypoints Sequence API to implement a travel itinerary planning case, which is more life-like and easy to understand. We can set passengers to depart from Silks Place Yilan (24.75374,121.75067) at 8 o'clock in the morning, and then list a few attractions we want to go as follows:

* Cheng Huang breakfast (https://bit.ly/3doeFRw), stay for 40 minutes and have breakfast leisurely. (24.7588975, 121.7526904)
* Yilan Railway Station Jimi Square (https://bit.ly/3cwtS3B), stay for 30 minutes, take pictures. (24.75475, 121.7576)
* The foyer of the old Yilan Prison (https://bit.ly/3ryPsJ3) , stay for 10 minutes, take photos. (24.75371, 121.7515)
* Memorial Hall of Founding of Yilan Administration (https://bit.ly/2PHucUg), stay for 30 minutes, leisurely. (24.75528, 121.74901)
* Agrioz Candied Fruit Museum (https://bit.ly/3u5GgNP), stay for 60 minutes. (24.7797106, 121.7373771)
* Toucheng Old Street (https://bit.ly/3sN034F), stop at 12 noon to 2 pm, stay for 60 minutes, have lunch. (24.85697, 121.8241578)
* Ajon Babu (https://bit.ly/3wjN0tF), stop between 12 noon and 2 pm, stay for 20 minutes, eat ice after lunch (must be behind Toucheng Old Street). (24.8587948, 121.8259636)
* Longtan Lake Scenic Area (https://bit.ly/3m4O7bV), stay for 120 minutes, arrive in the afternoon, ride a bicycle and walk. (24.7920844, 121.7398288)
* Leshan Hot Spring Ramen (https://bit.ly/3cz9GOr), stay for 40 minutes, book a table at 7 pm, have dinner. (24.8312227, 121.7757601)
* Chun Shui Ji Hot Spring(https://bit.ly/3ru5fZy) , stay for 90 minutes, and take a bath after eating (must be after Leshan Hot Spring Ramen). (24.831647, 121.770149)
* Return to Silks Place Yilan (24.75374,121.75067).

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

https://wse.ls.hereapi.com/2/findsequence.json?
start=Silks Place Yilan (Starting Point);24.75374,121.75067
&destination1=Cheng Huang breakfast;24.7588975,121.7526904;st:2400;acc:sa00:00:00Z|sa01:00:00Z
&destination2=Yilan Railway Station Jimi Square;24.75475,121.7576;st:1800
&destination3=The foyer of the old Yilan Prison;24.75371,121.7515;st:600
&destination4=Memorial Hall of Founding of Yilan Administration;24.75528,121.74901;st:1800
&destination5=Agrioz Candied Fruit Museum;24.7797106,121.7373771;st:3600
&destination6=Toucheng Old Street;24.85697,121.8241578;st:3600;acc:sa04:00:00Z|sa06:00:00Z;before:destination7
&destination7=Ajon Babu;24.8587948,121.8259636;st:1200;acc:sa04:00:00Z|sa06:00:00Z
&destination8=Longtan Lake Scenic Area;24.7920844,121.7398288;st:7200;acc:sa06:00:00Z|sa08:00:00Z
&destination9=Leshan Hot Spring Ramen;24.8312227,121.7757601;st:2400;at:2020-12-12T11:00:00Z;before:destination10
&destination10=Chun Shui Ji Hot Spring;24.831647,121.770149;st:5400
&end=Silks Place Yilan (End Point);24.75374,121.75067
&departure=2020-12-12T00:00:00Z
&mode=fastest;car;traffic:enabled
&apiKey={API_KEY}

According to the returned results, we can arrange the following order:

Silks Place Yilan (Starting Point): Depart at 08:00 in the morning.


Foyer of the old Yilan Prison: Arrive at 08:00 in the morning and leave at 08:10 in the morning.


Cheng Huang Breakfast (Breakfast): Arrive at 08:14 in the morning and leave at 08:54 in the morning.


Memorial Hall of Founding of Yilan Administration: Arrive at 08:57 in the morning and leave at 09:27 in the morning.


Yilan Railway Station Jimi Square: Arrive at 09:31 in the morning and leave at 10:01 in the morning.


Agrioz Candied Fruit Museum: Arrive at 10:13 in the morning and leave at 11:13 in the morning.


Toucheng Old Street (lunch): Arrive at 11:44 in the morning and leave at 13:00 in the afternoon.


Ajon Babu: Arrive at 01:01 in the afternoon and leave at 01:21 in the afternoon.


Longtan Lake Scenic Area: Arrive at 01:51 in the afternoon and leave at 04:00 in the afternoon.


Leshan Hot Spring Ramen (Dinner): Arrive at 04:21 in the afternoon and leave at 07:40 in the afternoon.


Chun Shui Ji Hot Spring: Arrive at 07:42 in the afternoon and leave at 09:12 in the afternoon.


Silks Place Yilan (End Point): Arrive at 09:37 in the afternoon.

The completed postback results are as follows:

{"results":[{"waypoints":[{"id":"Silks Place Yilan (Starting Point)","lat":24.75374,"lng":121.75067,"sequence":0,"estimatedArrival":null,"estimatedDeparture":"2020-12-12T00:00:00Z","fulfilledConstraints":[]},{"id":"The foyer of the old Yilan Prison","lat":24.75371,"lng":121.7515,"sequence":1,"estimatedArrival":"2020-12-12T00:00:54Z","estimatedDeparture":"2020-12-12T00:10:54Z","fulfilledConstraints":["st:600"]},{"id":"Cheng Huang breakfast","lat":24.7588975,"lng":121.7526904,"sequence":2,"estimatedArrival":"2020-12-12T00:14:07Z","estimatedDeparture":"2020-12-12T00:54:07Z","fulfilledConstraints":["acc:sa00:00:00+00:00|sa01:00:00+00:00;st:2400"]},{"id":"Yilan Railway Station Jimi Square","lat":24.75475,"lng":121.7576,"sequence":3,"estimatedArrival":"2020-12-12T00:57:32Z","estimatedDeparture":"2020-12-12T01:27:32Z","fulfilledConstraints":["st:1800"]},{"id":"Memorial Hall of Founding of Yilan Administration","lat":24.75528,"lng":121.74901,"sequence":4,"estimatedArrival":"2020-12-12T01:32:00Z","estimatedDeparture":"2020-12-12T02:02:00Z","fulfilledConstraints":["st:1800"]},{"id":"Toucheng Old Street","lat":24.85697,"lng":121.8241578,"sequence":5,"estimatedArrival":"2020-12-12T02:32:49Z","estimatedDeparture":"2020-12-12T05:00:00Z","fulfilledConstraints":["acc:sa04:00:00+00:00|sa06:00:00+00:00;st:3600","before:destination7"]},{"id":"Ajon Babu","lat":24.8587948,"lng":121.8259636,"sequence":6,"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":"Longtan Lake Scenic Area","lat":24.7920844,"lng":121.7398288,"sequence":7,"estimatedArrival":"2020-12-12T05:52:15Z","estimatedDeparture":"2020-12-12T08:00:00Z","fulfilledConstraints":["acc:sa06:00:00+00:00|sa08:00:00+00:00;st:7200"]},{"id":"Agrioz Candied Fruit Museum","lat":24.7797106,"lng":121.7373771,"sequence":8,"estimatedArrival":"2020-12-12T08:07:39Z","estimatedDeparture":"2020-12-12T09:07:39Z","fulfilledConstraints":["st:3600"]},{"id":"Leshan Hot Spring Ramen","lat":24.8312227,"lng":121.7757601,"sequence":9,"estimatedArrival":"2020-12-12T09:29:09Z","estimatedDeparture":"2020-12-12T11:40:00Z","fulfilledConstraints":["at:2020-12-12T11:00:00Z;st:2400","before:destination10"]},{"id":"Chun Shui Ji Hot Spring","lat":24.831647,"lng":121.770149,"sequence":10,"estimatedArrival":"2020-12-12T11:42:44Z","estimatedDeparture":"2020-12-12T13:12:44Z","fulfilledConstraints":["st:5400"]},{"id":"Silks Place Yilan (End Point)","lat":24.75374,"lng":121.75067,"sequence":11,"estimatedArrival":"2020-12-12T13:37:06Z","estimatedDeparture":null,"fulfilledConstraints":[]}],"distance":"57694","time":"49026","interconnections":[{"fromWaypoint":"Silks Place Yilan (Starting Point)","toWaypoint":"The foyer of the old Yilan Prison","distance":155.0,"time":54.0,"rest":0.0,"waiting":0.0},{"fromWaypoint":"The foyer of the old Yilan Prison","toWaypoint":"Cheng Huang breakfast","distance":641.0,"time":193.0,"rest":0.0,"waiting":0.0},{"fromWaypoint":"Cheng Huang breakfast","toWaypoint":"Yilan Railway Station Jimi Square","distance":957.0,"time":205.0,"rest":0.0,"waiting":0.0},{"fromWaypoint":"Yilan Railway Station Jimi Square","toWaypoint":"Memorial Hall of Founding of Yilan Administration","distance":972.0,"time":268.0,"rest":0.0,"waiting":0.0},{"fromWaypoint":"Memorial Hall of Founding of Yilan Administration","toWaypoint":"Toucheng Old Street","distance":17470.0,"time":1849.0,"rest":0.0,"waiting":5231.0},{"fromWaypoint":"Toucheng Old Street","toWaypoint":"Ajon Babu","distance":340.0,"time":88.0,"rest":0.0,"waiting":0.0},{"fromWaypoint":"Ajon Babu","toWaypoint":"Longtan Lake Scenic Area","distance":15624.0,"time":1847.0,"rest":0.0,"waiting":465.0},{"fromWaypoint":"Longtan Lake Scenic Area","toWaypoint":"Agrioz Candied Fruit Museum","distance":2494.0,"time":459.0,"rest":0.0,"waiting":0.0},{"fromWaypoint":"Agrioz Candied Fruit Museum","toWaypoint":"Leshan Hot Spring Ramen","distance":8375.0,"time":1290.0,"rest":0.0,"waiting":5451.0},{"fromWaypoint":"Leshan Hot Spring Ramen","toWaypoint":"Chun Shui Ji Hot Spring","distance":797.0,"time":164.0,"rest":0.0,"waiting":0.0},{"fromWaypoint":"Chun Shui Ji Hot Spring","toWaypoint":"Silks Place Yilan (End Point)","distance":9869.0,"time":1462.0,"rest":0.0,"waiting":0.0}],"description":"Targeted best time; with , improvement for traffic","timeBreakdown":{"driving":7879,"service":30000,"rest":0,"waiting":11147}}],"errors":[],"processingTimeDesc":"3142ms","responseCode":"200","warnings":null,"requestId":null}

Welcome to the HERE developer website to learn more about Waypoints Sequence: [https://developer.here.com/documentation/routing-waypoints/](https://developer.here.com/documentation/routing-waypoints/ )