1. docker compose up  --build
2. wait for preprocessing contraction hierarchies to complete (about 3 minutes) [you can check it with 'docker logs navigatorx -f', wait until the text 'Contraction Hierarchies + Bidirectional Dijkstra Ready!!' appears  ]

1. download the jogja & solo openstreetmap pbf file at: https://drive.google.com/file/d/1pEHN8wwUbB5XpuYMZm141fXQ_ZsIf4CO/view?usp=sharing
Note: or you can also use another openstreetmap file with the osm.pbf format (https://download.geofabrik.de/)
2.  put the download results into the root directory of this project
3.  go mod tidy &&  mkdir bin
4. CGO_ENABLED=1  go build -o ./bin/navigatorx .
5. ./bin/navigatorx
(Minimum free RAM 1 GB for the above data)
note: or you can also do it with "make run"
5.  wait for preprocessing contraction hierarchies to complete (about 3 minutes)

1. provide openstreetmap filename flag when running the program
 ./bin/navigatorx -f jakarta.osm.pbf
2. for docker setup, change the Filename args "MAP_FILE" and google drive file id "DRIVE_FILE_ID" in docker-compose
 args:
        MAP_FILE: solo_jogja
        DRIVE_FILE_ID: 1pEHN8wwUbB5XpuYMZm141fXQ_ZsIf4CO

1. wait until there is a log "server started at :5000". If you want the query to be >10x faster, wait for the Contraction Hierarchies preprocessing to complete.
2. request ke shortest path (source=surakarta , destination=pantai parangtritis) [untuk data openstreetmap pada step setup]
curl --location 'https://localhost:5000/api/navigations/shortest-path' \
--header 'Content-Type: application/json' \
--data '{
    "src_lat": -7.550261232598317,
    "src_lon":    110.78210790296636,
    "dst_lat": -8.024431446370416,
    "dst_lon":   110.32971396395838
}'

Note: Source & Destination Coordinates must be around Yogyakarta Province/Surakarta City/Klaten if using OpenStreetMap data in the setup step
5. Copy the polyline string path of the response endpoint result to https://valhalla.github.io/demos/polyline . Check Unsescape '\'. The shortest route will appear on the map. :)

1. wait until there is a log "server started at :5000". If you want the query to be >10x faster, wait for the Contraction Hierarchies preprocessing to complete.
2. request to the server with route list of gps coordinate data (or fake route coordinate data)
curl --location 'https://localhost:5000/api/navigations/map-matching' \
--header 'Content-Type: application/json' -d @gps_hmm_map_matching.json

Note:  GPS Coordinates must be around the Yogyakarta province/Surakarta city/Klaten if using OpenStreetMap data in the setup step
3. Copy the polyline string path of the response endpoint result to https://valhalla.github.io/demos/polyline . Centang Unsescape '\'. The map matching results in the form of a list of road network node coordinates will appear on the map. :)

1. Wait until Contraction Hierarchies preprocessing is complete
2. request query traveling salesman problem
curl --location 'https://localhost:5000/api/navigations/tsp' \
--header 'Content-Type: application/json' \
--data '{
    "cities_coord": [
        {
            "lat": -7.773700556142326,
            "lon": 110.37927594982729
        },
        {
            "lat": -7.687798280189743,
            "lon": 110.41397147030537
        },
        {
            "lat": -7.773714842796234,
            "lon": 110.38625612460329
        },
        {
            "lat": -7.7620859704046135,
            "lon": 110.40928883503045
        },
        {
            "lat": -7.559256385020671,
            "lon":  110.85624887436603
        },
        {
            "lat": -7.558529640984029,
            "lon": 110.73442218529993
        },
        {
            "lat": -7.5579561088085665,
            "lon":  110.85233572375333
        },
        {
            "lat":  -7.557649260722883,
            "lon": 110.77068956586514
        }
    ]
}'
Note:  "cities_coord" must be a place around the province of Yogyakarta/Surakarta/Klaten if using OpenStreetMap data in the setup step
3.  Copy the polyline string path of the response endpoint result to https://valhalla.github.io/demos/polyline . Check Unsescape '\'. The shortest (suboptimal) TSP route will be displayed on the map. :)

1. wait until preprocessing contraction hierarchies is complete
2. request  query many to many
curl --location 'https://localhost:5000/api/navigations/many-to-many' \
--header 'Content-Type: application/json' \
--data '{
    "sources": [{
        "lat": -7.550248257898637,
        "lon": 110.78217903249168
    },
    {
        "lat": -7.560347382387681,
        "lon": 110.78879587509478
    },
    {
        "lat": -7.5623445763181945,
        "lon": 110.81010426983109
    }
    ],
    "targets": [{
        "lat": -7.553672205152498,
        "lon": 110.79784256968716
    },
    {
        "lat": -7.564559782091322,
        "lon":  110.80455609811008
    },
    {
        "lat": -7.570135257838102,
        "lon": 110.82292649269334
    },
    {
        "lat": -7.598393719179397,
        "lon": 110.81555588473815
    }


    ]
}'

Note:  "sources" and "targets" must be around the province of Yogyakarta/Surakarta/Klaten if using OpenStreetMap data in the setup step
3.  Copy the polyline string path of the response endpoint result to https://valhalla.github.io/demos/polyline . Centang Unsescape '\'. Check Unsescape '\'. The shortest route of many to many query will be displayed on the map. :)

1. wait until there is a log "server started at :5000". If you want the query to be >10x faster, wait for the Contraction Hierarchies preprocessing to complete.
2. request query shortest path w/ alternative street
curl --location 'https://localhost:5000/api/navigations/shortest-path-alternative-street' \
--header 'Content-Type: application/json' \
--data '{
    "src_lat": -7.550261232598317,
    "src_lon":    110.78210790296636,
    "street_alternative_lat": -7.8409667827395815,
    "street_alternative_lon":   110.3472473375829,
      "dst_lat": -8.024431446370416,
    "dst_lon":   110.32971396395838
}'

Note:  "sources" and "targets" must be around the province of Yogyakarta/Surakarta/Klaten if using OpenStreetMap data in the setup step
3. Copy the polyline string path of the response endpoint result to https://valhalla.github.io/demos/polyline . Check Unsescape '\'. The shortest route will appear on the map. :)

- R. Geisberger, P. Sanders, D. Schultes, and D. Delling, “Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks,” in Experimental Algorithms, C. C. McGeoch, Ed., Berlin, Heidelberg: Springer, 2008, pp. 319–333. doi: 10.1007/978-3-540-68552-4_24.
-  “Hidden Markov Map Matching Through Noise and Sparseness - Microsoft Research.” Accessed: Oct. 24, 2024. [Online]. Available: https://www.microsoft.com/en-us/research/publication/hidden-markov-map-matching-noise-sparseness/
- https://en.wikipedia.org/wiki/Simulated_annealing#:~:text=Simulated%20annealing%20(SA)%20is%20a,can%20find%20the%20global%20optimum.
- https://jlazarsfeld.github.io/ch.150.project/sections/7-ch-overview/
- https://www.uber.com/en-ID/blog/engineering-routing-engine/
- https://www.uber.com/en-ID/blog/h3/
- https://www.uber.com/blog/mapping-accuracy-with-catchme/
- https://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html