Map Matching

Map matching is the process of aligning a sequence of GPS coordinates with a corresponding road network, resulting in a reconstructed and smoothed trajectory. The aim of map matching is to take a series of GPS points and match each point to the closest road segment on a digital road network. This reconstructed route can then be used to determine the actual path taken by the vehicle, which can be used for a wide range of applications such as traffic analysis, routing, etc.

Map matching algorithms typically involve a probabilistic approach that incorporates several sources of information. The algorithms consider a set of possible paths that could correspond to the vehicle’s actual path and evaluate the likelihood of each path using various criteria such as distance. The path with the highest likelihood is then selected as the reconstructed route.

Map matching is important because GPS trajectories can have significant noise, which can lead to inaccuracies in determining the actual path taken by a vehicle. By using map matching, it is possible to improve the accuracy and obtain a more precise understanding of the vehicle’s route. This can be important for various applications, such as transportation planning, logistics, and many more.

Valhalla

Valhalla is a routing engine that provides APIs and libraries to allow developers to add customizable and flexible routing capabilities to their applications. It is an open-source project that uses OpenStreetMap (OSM) data and offers a suite of tools and services for map matching, time and distance matrix computation, and more. It was created by Mapzen, a company that aimed to provide free and open access to high-quality mapping tools and data.

Valhalla utilizes a tiled hierarchical data structure, allowing for a small memory footprint, offline routing, and partial updates. It is C++ based, so it is swift and efficient. It also allows dynamic, runtime pricing of edges and nodes within the graph through a plugin architecture, allowing for modification and alternate trajectory generation.

Valhalla is released under the MIT license, meaning that it can be used freely for both commercial and non-commercial purposes. The project has a growing community of contributors and users, and its documentation and resources are continuously updated and improved.

Meili

Meili is a map-matching engine developed by Valhalla. The Meili engine consists of several algorithms, which are used to determine the best match for a given GPS trajectory. It uses Hidden Markov Model (HMM) approach, proposed by Paul Newson and John Krumm in 2009 which is used to determine the solution to the map matching problem. Furthermore, it uses the Viterbi algorithm to find the most likely sequence in HMM. The Viterbi Algorithm functions similarly to the Breath-First-Search (BFS) algorithm in that it examines the objective level by level. It recalls each node’s optimal solution and utilizes it to discover optimal solutions for the next level during the search/expansion. You can learn more about the algorithms Meili employs by visiting this page.

Using gis-ops’s Docker Image

Because all of the map matching is done in a docker container, you need to install docker and build the following container. Valhalla provides a docker image to facilitate the deployment of its tools. However, the gis-ops/docker-valhalla docker image provides a lightweight and customizable environment that can be tailored to specific needs and requirements. By using gis-ops’s docker image, it is possible to build and deploy a map-matching container that suits your specific use case. Here is an example of the docker-compose file:

version: '3.0'
services:
  valhalla:
    image: gisops/valhalla:latest  # gis-ops/docker-valhalla image.
    container_name: valhalla_container_name  # The name of the container.
    ports:
      - 8002:8002
    deploy:
      resources:
        limits:
          memory: 16g
    volumes:
      - ./custom_files/:/custom_files  # The location where all data will be stored.
    environment:
      - tile_urls=https://download.geofabrik.de/europe/greece-latest.osm.pbf  # The location of the trajectories you want to be map matched. 
      - server_threads=1  # Determines how many threads will be used to run the valhalla server.
      - serve_tiles=True  # If True, starts the service. If false, stops after building the graph.
      - use_tiles_ignore_pbf=True  # Load existing valhalla_tiles.tar directly.
      - tileset_name=valhalla_tiles  # Name of the resulting graph on disk.
      - build_elevation=False  # Build elevation with "True" or "Force": will download only the elevation for areas covered by the graph tiles.
      - build_admins=False  # Build admins db with "True" or "Force".
      - build_time_zones=False  # Build timezone db with "True" or "Force".
      - build_tar=True  # Build an indexed tar file from the tile_dir for faster graph loading times.
      - force_rebuild=False  # Forces a rebuild of the routing tiles with "True".

We increase the amount of memory that the docker container can use to prevent any errors during the building process. 16 GB is sufficient for even the largest countries, but if you want to make a container with all of the world’s street data, you may need to increase the limit even further. We download our data from the download.geofabrik.de website, which provides free and open access to OpenStreetMap (OSM) data extracts in various formats and regions around the world.

OpenStreetMap is a collaborative and free map of the world created and maintained by volunteers and is often used as an alternative to proprietary maps such as Google Maps. The data on OpenStreetMap is constantly updated and improved by the community, which makes it a valuable resource for various applications, such as routing, geocoding, and data analysis.

Before we start building the container, we need to create an empty folder with the name custom_files that the container will use to store its data. Now we go to the location where the docker-compose file is stored and simply execute:

docker compose up

Now that our docker container is up and running, we need to create a function in python that takes our trajectory and returns us the map matched one.

def map_matching(df):
    meili_coordinates = df.to_json(orient='records')
    meili_head = '{"shape":'
    meili_tail = ""","search_radius": 50, "shape_match":"map_snap", "costing":"auto", "format":"osrm"}"""
    meili_request_body = meili_head + meili_coordinates + meili_tail
    url = "http://localhost:8002/trace_route"
    headers = {'Content-type': 'application/json'}
    data = str(meili_request_body)

    r = requests.post(url, data=data, headers=headers)

    if r.status_code == 200:
        response_text = json.loads(r.text)
        resp = str(response_text['tracepoints'])
        resp = resp.replace("None", "{'matchings_index': '#', 'name': '', 'waypoint_index': '#',"
                                    " 'alternatives_count': 0, ""'distance': 0, 'location': [0.0, 0.0]}")
        resp = resp.replace("'", '"')

        matched_df = df.copy()

        df_response = pd.read_json(resp)

        for i in range(len(df_response)):
            if matched_df['lon'].iat[i] != 0.0:
                matched_df['lon'].iat[i] = df_response['location'].iat[i][0]
                matched_df['lat'].iat[i] = df_response['location'].iat[i][1]

        return matched_df

The map_matching function takes a pandas DataFrame object as input, representing a GPS trajectory. The trajectory consists of a series of latitude and longitude coordinates recorded at different points in time, forming a path that the user has taken. The function then converts the DataFrame object into a JSON object, which is a common format for representing data in web applications. The JSON object is then passed to the Valhalla Meili service through an HTTP POST request to the local server running on port 8002.

The request body consists of the JSON object with a search radius of 50 meters, indicating how far away from the actual GPS points the Meili service should search for a matching road. The shape_match parameter is set to “map_snap”, which means that Meili will match the GPS points to the closest road segment in the map. The costing parameter is set to “auto”, which means that Meili will use the most appropriate routing profile based on the type of road, traffic conditions, and other factors. The format parameter is set to “osrm”, which is the format used by the Open Source Routing Machine (OSRM) routing engine.

Once the request is sent, the Meili service processes the GPS trajectory and returns a response that contains the matched coordinates for each point in the trajectory. The response is then parsed and converted to a pandas DataFrame object. The matched coordinates are then assigned to the DataFrame object and returned as the output of the function. If a GPS trajectory point cannot be matched to a road segment on the map, it remains unchanged and is not map matched.

There could be several reasons why Valhalla does not reply with a 200 status number. One possibility is that the GPS trajectory was not near enough to a road to conduct a map comparison. Another option is that the GPS trajectory was acquired in a country in which the required tiles have not been created. Finally, it is possible that the GPS trajectory is flawed.

Here are some visualized results of the map matching:

That’s all there is to map matching with Valhalla’s Meili. Stay informed because we will be delving deeper into spatial and vehicle data in the immediate future!