# US 2020/0263999 A1 · Geographic routing engine

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0263999 A1
- Document ID: US20200263999A1
- Status: Published application
- Kind: A1
- Application number: 16/727,658
- Filed: 2019-12-26
- Published: 2020-08-20
- Earliest claimed: 2018-08-02
- Assignees: Mapanything, Inc.
- Applicants: MapAnything, Inc.
- Inventors: John Brian Stewart; Dinesh Premalal Weerapurage; Timothy Alan Carnes; Christopher Sebastian Groer; Lahiru Sandakith Pileththuwasan Gallege; Chenlu Lou
- Web page: https://patentgrep.com/patent/US20200263999A1

## CPC

- G01C 21/3461: {Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries}
- G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)}
- G01C 21/3438: {Rendezvous; Ride sharing}
- G01C 21/3605: {Destination input or retrieval}
- G06F 16/29: Geographical information databases
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A server within an on-demand computing services environment may receive a request to determine a route that involves a set of geographic locations. The server may identify pre-computed path information suitable for responding to the request. A route may be determined based on the identified information, and route information may be transmitted in response to the request.

## Claims

### Claim 1

A method comprising:
receiving a route optimization request message at a server within an on-demand computing services environment, the route optimization request message identifying a first plurality of geographic locations associated with a routing request from a client entity;
identifying via a processor one of a plurality of geographic zones based on the route optimization request message, the identified geographic zone including the first plurality of geographic locations and a second plurality of geographic locations;
retrieving route optimization information from a designated one of a plurality of zone servers, the designated zone server being associated with the identified geographic zone, the route optimization information identifying transit information between each of a plurality of pairs of the second plurality of geographic locations;
determining a route to traverse the first plurality of geographic locations based on the retrieved route optimization information; and
transmitting, via a communication interface, a response message identifying the route to a client machine associated with the client entity.

### Claim 2 (depends on 1)

The method recited in claim 1, wherein a designated geographic area is included in two or more of the geographic zones.

### Claim 3 (depends on 1)

The method recited in claim 1, wherein the identified geographic zone is the smallest of the plurality of zones that includes the first plurality of geographic locations.

### Claim 4 (depends on 1)

The method recited in claim 1, wherein the transit information identifies a first plurality of transit time values, each transit time value identifying a respective transit time between two or more of the second plurality of geographic locations.

### Claim 5 (depends on 4)

The method recited in claim 4, wherein determining the route to traverse the first plurality of geographic locations involves determining a second plurality of transit time values by interpolating from two or more of the first plurality of transit time values.

### Claim 6 (depends on 5)

The method recited in claim 5, wherein one or more of the first plurality of transit time values are determined by the designated zone server based on one or more observed travel time values.

### Claim 7 (depends on 5)

The method recited in claim 5, wherein each of the first plurality of transit time values is stored in a shortest path matrix computed by the designated zone server.

### Claim 8 (depends on 1)

The method recited in claim 1, wherein the server is included within an on-demand computing services environment configured to provide computing services to a plurality of clients via a network, the plurality of clients including the client entity.

### Claim 9

A computing device configured to perform a method, the method comprising:
receiving a route optimization request message at a server within an on-demand computing services environment, the route optimization request message identifying a first plurality of geographic locations associated with a routing request from a client entity;
identifying via a processor one of a plurality of geographic zones based on the route optimization request message, the identified geographic zone including the first plurality of geographic locations and a second plurality of geographic locations;
retrieving route optimization information from a designated one of a plurality of zone servers, the designated zone server being associated with the identified geographic zone, the route optimization information identifying transit information between each of a plurality of pairs of the second plurality of geographic locations;
determining a route to traverse the first plurality of geographic locations based on the retrieved route optimization information; and
transmitting, via a communication interface, a response message identifying the route to a client machine associated with the client entity.

### Claim 10 (depends on 9)

The computing device recited in claim 9, wherein a designated geographic area is included in two or more of the geographic zones.

### Claim 11 (depends on 9)

The computing device recited in claim 9, wherein the identified geographic zone is the smallest of the plurality of zones that includes the first plurality of geographic locations.

### Claim 12 (depends on 9)

The computing device recited in claim 9, wherein the transit information identifies a first plurality of transit time values, each transit time value identifying a respective transit time between two or more of the second plurality of geographic locations.

### Claim 13 (depends on 9)

The computing device recited in claim 9, wherein determining the route to traverse the first plurality of geographic locations involves determining a second plurality of transit time values by interpolating from two or more of the first plurality of transit time values.

### Claim 14 (depends on 9)

The computing device recited in claim 9, wherein one or more of the first plurality of transit time values are determined by the designated zone server based on one or more observed travel time values.

### Claim 15

One or more non-transitory machine-readable media having instructions stored thereon for performing a method, the method comprising:
receiving a route optimization request message at a server within an on-demand computing services environment, the route optimization request message identifying a first plurality of geographic locations associated with a routing request from a client entity;
identifying via a processor one of a plurality of geographic zones based on the route optimization request message, the identified geographic zone including the first plurality of geographic locations and a second plurality of geographic locations;
retrieving route optimization information from a designated one of a plurality of zone servers, the designated zone server being associated with the identified geographic zone, the route optimization information identifying transit information between each of a plurality of pairs of the second plurality of geographic locations;
determining a route to traverse the first plurality of geographic locations based on the retrieved route optimization information; and
transmitting, via a communication interface, a response message identifying the route to a client machine associated with the client entity.

### Claim 16 (depends on 15)

The one or more non-transitory machine-readable media recited in claim 15, wherein a designated geographic area is included in two or more of the geographic zones.

### Claim 17 (depends on 15)

The one or more non-transitory machine-readable media recited in claim 15, wherein the identified geographic zone is the smallest of the plurality of zones that includes the first plurality of geographic locations.

### Claim 18 (depends on 15)

The one or more non-transitory machine-readable media recited in claim 15, wherein the transit information identifies a first plurality of transit time values, each transit time value identifying a respective transit time between two or more of the second plurality of geographic locations.

### Claim 19 (depends on 15)

The one or more non-transitory machine-readable media recited in claim 15, wherein determining the route to traverse the first plurality of geographic locations involves determining a second plurality of transit time values by interpolating from two or more of the first plurality of transit time values.

### Claim 20 (depends on 15)

The one or more non-transitory machine-readable media recited in claim 15, wherein one or more of the first plurality of transit time values are determined by the designated zone server based on one or more observed travel time values.
