api-dispatch

Table of Contents

1. Introduction
   1. The problem
   2. The solution
2. Project structure
3. How does it work
   1. Geospatial Indexing
   2. Ingestion
   3. Querying
4. Getting started

Introduction

A proof-of-concept dispatch service.

The problem

Given a known list of drivers and their geographic whereabouts, and given a known location for a trip pickup, how do we select the nearest drivers? Conversely, how do we select the best trips for drivers?

The solution

A combination of h3 (a hexagonal hierarchical geospatial indexing system) and distance matrix APIs, such as Google Maps or Open Source Routing Machine (OSRM).

Project structure

Directory	Description
./cmd	CLI for making gRPC requests
./idl	Protobufs (Interface Definition Language)
./internal/app	App dependency injection / initialization
./internal/idl	Auto-generated protobufs
./internal/models	Auto-generated ORM / models
./internal/service	Service layer / Business logic
./schema	SQL migration scripts
./pkg/grpc	gRPC interceptors
./pkg/maps	Geo-related logic (e.g., geocoding, distance matrix)

How does it work

Ingestion

See ./docs/ingestion.md.

Geospatial Indexing

H3 is covered in more detail in ./docs/h3.md.

Briefly, H3 tessellatees the world into hexagons at various resolutions. We rank by distance using the concept of k-rings, which are akin to concentric circles.

Querying

There are two sorting/ranking passes. The first pass is for general reachability. The second pass is to precisely rank results based on distance/duration.

The first sorts by k-ring (concentric circle). Results that are in tighter concentric circles, at finer (more zoomed in) resolutions, will rank higher.

The second pass sorts based on the duration it would take the driver to travel to the pickup point. For this, we use a Distance Matrix request.

A third ranking phase could potentially take place downstream, where other non-geographical factors are considered, such as a driver's rating or seniority, or a trip's expected payment, start time, expected duration, etc.

Getting started

First, spin everything up:

# Step 1: Start containers in detached (background) mode
docker-compose up -d

# Step 2: Create the database schema
make migrate-up

# Step 3: Start app (you can optionally specify a API_KEY env var for Google Maps)
go run main.go

# Step 4: Seed trips
go run cmd/dispatch/*.go ingest trips --file seed-trips.json

# Step 5: Seed drivers
go run cmd/dispatch/*.go ingest drivers --file seed-drivers.json

Finally, hit the API (using HTTPie)

http POST \
  http://localhost:8081/coop.drivers.dispatch.v1beta1.DispatchService/GetNearestDrivers \
    limit=2 \
    pickup_location:='{"latitude": 40.73010864595388, "longitude": -73.95094555260256}'

Here we're requesting a pickup at Key Food Supermarkets (Greenpoint).

Notice how drivers in neighboring hex cells at higher (finer) resolutions appear above those who neighbor the pickup location in lower (coarser) resolutions.

(See these results in Google Maps)

{
   "results": [
      {
         "driver": {
            "driverId": "GPT-Christinas",
            "mostRecentHeartbeat": "0001-01-01T00:00:00Z",
            "currentLocation": {
               "latitude": 40.729116923462385,
               "longitude": -73.95392251222499
            }
         },
         "distanceMeters": 471,
         "duration": "227s",
         "location": {
            "latitude": 40.729116923462385,
            "longitude": -73.95392251222499
         },
         "address": "853 Manhattan Ave, Brooklyn, NY 11222, USA",
         "resolution": 10,
         "kValue": 2
      },
      {
         "driver": {
            "driverId": "GPT-Pelicana-Chicken",
            "mostRecentHeartbeat": "0001-01-01T00:00:00Z",
            "currentLocation": {
               "latitude": 40.731416756150395,
               "longitude": -73.95470131162523
            }
         },
         "distanceMeters": 706,
         "duration": "292s",
         "location": {
            "latitude": 40.731416756150395,
            "longitude": -73.95470131162523
         },
         "address": "941 Manhattan Ave, Brooklyn, NY 11222, USA",
         "resolution": 9,
         "kValue": 2
      }
   ],
   "pickupAddress": "216 Greenpoint Ave, Brooklyn, NY 11222, USA"
}