The sharing economy has introduced a new wave of online marketplace apps and business models, where consumers and sellers are matched across a unique differentiated set of product inventory. This contrasts with traditional e-commerce platforms, where inventory is standardized and sellers are few. Online multi-sided marketplaces range from Uber and Lyft in gig-economy transportation of people with unique routes to DoorDash and Postmates in restaurant delivery with unique orders, Instacart and GoPuff in grocery delivery with unique pick-up and drop-off locations, TaskRabbit and Amazon Mechanical Turk with unique ad-hoc jobs, Turo and Boatsetter for individual car and boat rentals, Airbnb with unique one-of-a-kind accommodations, and Rover for dog care.
Each of these businesses has successfully created a marketplace that matches customers with a wide variety of sellers offering differentiated products or services, rather than standardized items. This creates a more complex system than traditional retail as it presents a complex optimization problem where we must balance the multiple needs across a diverse set of users - times/dates, locations, qualifications / features / amenities, availability, regional regulations, and so forth. Additionally, the rules and functioning of the marketplace need to be considered carefully to prevent gaming and ensure a fair and transparent marketplace for all parties.
In this 8-part e-book, we will design a multi-sided online marketplace encompassing multiple domains, subsystems, and applications, with principles which can be applied to a wide variety of marketplace and gig-economy use cases from taxi services (e.g. Uber, Lyft), to restaurant delivery (e.g. DoorDash, Postmates), to third-party deliveries (e.g. Instacart, Shipt, Convoy). We’ll focus on a complex three-sided marketplace use-case involving three distinct sets of users: customers making purchases, third-party vendors, and gig-economy drivers. By the end we will have designed a global transportation platform with multi-sided marketplace where (i) consumers can shop through a variety of vendors (3rd-party merchants or taxi services), (ii) have their goods or themselves delivered quickly – as quick as same-hour, (iii) by gig-economy drivers, (iv) either scheduled-ahead or on-demand, (v) all without merchants or taxi companies managing any of the logistical complexity.
We must balance: speed, low-cost, and accurate-ETA’s for customers; consistent, highly-available taxi & delivery services for third-party merchants and taxi companies; and fairness, transparency, and consistency for gig-economy drivers. The platform will support a wide range of transport speeds starting as quick as same-hour with low latency APIs to optimize the checkout flow for maximum conversion. We will support multiple pick-up and drop-off locations, given products and customers will be distributed. Finally, we will support multiple mechanisms for gig-economy drivers to obtain work, either scheduling work ahead to guarantee sufficient working hours or working on-demand with maximal flexibility, obtaining work in real time.
- Part 1: Introduction, Requirements, Mobile and Web Applications
- Part 2: Backend Infrastructure and Service Architecture
- Part 3: Vendor Management and 3rd Party Customer Shopping & Checkout
- Part 4: Transport Supply & Demand Management and Forecasting with Machine Learning
- Part 5: Route Planning, ETAs, and Dynamic Pricing with Machine Learning
- Part 6: Driver Onboarding, Preferences, Standings, Rewards, and Payments
- Part 7: Driver-Route Targeting, Pushed On-Demand Routes, and Precomputed Eligibility
- Part 8: Gig-Economy Route Marketplace for Schedule-Ahead Routes with Deferred Route Matching
Part 5: Route Planning, ETAs, and Dynamic Pricing with Machine Learning
Contents:
- Introduction
- Geospatial
- Geocoding
- Regions and Locations
- Route Planning
- Shortest-Path Routing
- Multi-Stop Route Planning
- Grouping Orders
- Replanning Routes
- Route Management
- Transport Times
- Initializing Route Timings
- Real-Time Traffic
- Dynamic Route Pricing for Drivers
- Forecasting the Route Supply-Demand Price Curve
- Vending Prices
- Conclusion
Introduction
In Part 1, we envisioned a global transportation software platform enabling third-party vendors to rapidly transport goods to customers – or customers themselves – within an hour, covering requirements, web/mobile apps, and overall flows. In Part 2, we explored the backend infrastructure and service architecture. In Parts 3-8, we are diving into the domains, subsystems, and services required. Here in Part 5, we discuss the Geospatial, Route Planning, Transport Times, and Route Pricing domains.
To plan routes we need to be able to: (1) convert an address into a latitude and longitude coordinates, (2) evaluate the shortest path between two sets of coordinates, and (3) generate an optimal combination of multi stop driving routes across orders. To provide customers with a set of time window options and ETAs we also need to be able to evaluate the estimated transportation time to complete a single or multi-stop route.
Also see - Software Architecture - Mapping, Navigation, and ETA System.
Let’s dive into the first requirement - converting a text-based address into geocoordinates.
Geospatial
The Geospatial domain includes services for geocoding and managing geographical data.
Geocoding
Geocoding is the process of converting a text-based address into latitude and longitude geographic coordinates. This will be required each time a customer begins to checkout and the vendor sends their order details to our platform to check for available order time window options, as well as when submitting the order. All the rest of our transportation platform will then rely on the order’s geo coordinates rather than the text-based address.
The Geocoding Service takes the address, matches it to a street in the database, and a specific segment of that street, such as a block. It then interpolates the position of the address within the range of the segment. If this data is not available for an address, such as when first launched to new regions, it will leverage a third-party API (e.g. Google Maps Geocoding API), while persisting each result so subsequent queries do not need to perform the same external API lookup. Data is stored in a geocoding key-value database, including the street, city, state, country, postal code, lat/lng coordinates, and a geohash ID. The geohash ID is based on a common geocoding system for encoding a geographic location into a hierarchical data structure which subdivides the globe into a grid using a space-filling curve (Z-order curve). It is quick to encode and decode (O(1) time complexity) and will help in a multitude of lookup and proximity queries.
Given the high reads and low writes, this data is very readily cacheable, and therefore the data is also cached in an in-memory cache (e.g. Redis) with an LRU eviction policy. Over time the service will be able to solely rely on the stored mappings of geocodes.
{ id: “44c08c9e-c8fe-4211-855b-f9db108f4bc2”, loc: “9q8yx12”, lat: 37.4267, lng: -122.0792, postal: 11211, street: “121 6th Avenue”, city: “New York”, state: “NY”, country: “US” }
Regions and Locations
The transportation platform requires a system to store information about various points of interest, as well as to manage regional information and configuration. The Geolocation Service stores all the metadata about specific locations such as their name, location, and hours of operation and metadata about regions such as their postal codes, geofencing, and configured order options.
This data will be accessed frequently by key lookups and is suitable to a key-value database as well. It is also very readily cacheable with low writes and high reads.
Services:
- Geocoding - converts a text address into latitude and longitude geographic coordinates
- Geolocation - manages metadata and configuration on locations and regions
Route Planning
Shortest-Path Routing
Before the platform can plan routes or provide order ETAs it first needs the ability to evaluate the shortest path between two geographic points. The Route Planning Service shortest path API receives two sets of latitude and longitude coordinates, one for the origin and one for the destination, and returns a list of the shortest paths from origin to destination in ascending order without considering real-time signals like traffic.
The remainder of this chapter is available by purchasing the e-book.
Sign up for free chapters of my book
or
buy it today